Can anyone please explain to me why we have such equations below in part b) and c)? They are the solutions to the questions, but I can't really understand why and how to get that. Many thanks. ==== QUESTION ==== In the Shamir secret sharing scheme, we distribute a secret among q different users as follows. If our secret is a message (m1, . . . , mk) from V (k, q) then, we encode it as a codeword of the Reed-Solomon RSk(q) and give one coordinate to each user. In this problem, we will use q = 7, k = 4 and the parity check matrix H4 below for RS4(7). H4 = [1 1 1 1 1 1 1, 0 1 2 3 4 5 6, 0 1 4 2 2 4 1] a) Write a generator matrix for RS4(7) b) A new secret is selected and user #1 receives share value 0, user #2 receives share value 6 and user #3 receives share value 1 and are collaborating to discover the new secret. Explain why they can’t recover the secret with only this information. c) Now, suppose users #1, #2 and #3 (as in the previous item) discover, in addition to the values of their own shares, that users #4 and #5 have identical shares (but they don’t necessarily know what the common value is). Using this information, first explain how they can collaborate to recover the secret and then find the secret. ====ANSWER==== a. The generator matrix is: H3 = [1 1 1 1 1 1 1, 0 1 2 3 4 5 6, 0 1 4 2 2 4 1, 0 1 1 6 1 6 6] I totally get (a), just put it here for context. b) If the secret is (x1, x2, x3, x4), the given conditions produce the equations: x1 = 0, x1 + x2 + x3 + x4 = 6, x1 + 2x2 + 4x3 + x4 = 1 and there are many solutions to this equation, as you can choose e.g. x2 arbitrarily and solve for x1, x3, x4. c) In addition to the equations x1 = 0, x1 + x2 + x3 + x4 = 6, x1 + 2x2 + 4x3 + x4 = 1 from the previous item, we also have the equation x1 + 3x2 + 2x3 + 6x4 = x1 + 4x2 + 2x3 + x4 which gets simplified to x2 + 2x4 = 0 and now we have 4 equations in 4 unknowns and we can check they have full rank and solve it to get that the secret is (0, 4, 4, 5).
Can anyone please explain to me why we have such equations below in part b) and c)? They are the solutions to the questions, but I can't really understand why and how to get that. Many thanks.
==== QUESTION ====
In the Shamir secret sharing scheme, we distribute a secret among q different users as follows. If our secret is a message (m1, . . . , mk) from V (k, q) then, we encode it as a codeword of the Reed-Solomon RSk(q) and give one coordinate to each user. In this problem, we will use q = 7, k = 4 and the parity check matrix H4 below for RS4(7). H4 = [1 1 1 1 1 1 1, 0 1 2 3 4 5 6, 0 1 4 2 2 4 1]
a) Write a generator matrix for RS4(7)
b) A new secret is selected and user #1 receives share value 0, user #2 receives share value 6 and user #3 receives share value 1 and are collaborating to discover the new secret. Explain why they can’t recover the secret with only this information.
c) Now, suppose users #1, #2 and #3 (as in the previous item) discover, in addition to the values of their own shares, that users #4 and #5 have identical shares (but they don’t necessarily know what the common value is). Using this information, first explain how they can collaborate to recover the secret and then find the secret.
====ANSWER====
a. The generator matrix is: H3 = [1 1 1 1 1 1 1, 0 1 2 3 4 5 6, 0 1 4 2 2 4 1, 0 1 1 6 1 6 6]
I totally get (a), just put it here for context.
b) If the secret is (x1, x2, x3, x4), the given conditions produce the equations: x1 = 0, x1 + x2 + x3 + x4 = 6, x1 + 2x2 + 4x3 + x4 = 1 and there are many solutions to this equation, as you can choose e.g. x2 arbitrarily and solve for x1, x3, x4.
c) In addition to the equations x1 = 0, x1 + x2 + x3 + x4 = 6, x1 + 2x2 + 4x3 + x4 = 1 from the previous item, we also have the equation x1 + 3x2 + 2x3 + 6x4 = x1 + 4x2 + 2x3 + x4 which gets simplified to x2 + 2x4 = 0 and now we have 4 equations in 4 unknowns and we can check they have full rank and solve it to get that the secret is (0, 4, 4, 5).
Step by step
Solved in 3 steps
