0
$\begingroup$

Suppose implement the Shamir secret sharing as following: we select a degree $d$ polynomial $P$ with a zero coefficient of 0, and all other coefficents selected randomly from $Z_p$; and to this polynomial $P$, we add the secret as a constant term $Q = P + secret$. If we use $Q$ as the polynomial in our Secret Sharing scheme, this is precisely equivalent to Shamir's scheme.

Now my question is : what if we multiply instead of add? That is, what if we select $P$ as above, except with a random 0th coefficient as well, and compute $Q = P \times secret$? This makes the original polynomial recover harder, but my main concern is about the (semantically) security of the scheme.

$\endgroup$
  • $\begingroup$ Why do you want to use this? Is there any specific reason? In other words, what is your application scenario. $\endgroup$ – mikeazo Oct 1 '14 at 14:46
  • 2
    $\begingroup$ I tried to make your question more understandable; if I garbled it, or misinterpreted it, feel free to roll back my changes. $\endgroup$ – poncho Oct 1 '14 at 14:50
  • $\begingroup$ @poncho In terms of its application, A has a fixed polynomial multiplies it by a random polynomial to obtain P1 then evaluates the result (which is a polynomial) on some points, to obtain some Y’s. Then he outsources only Y’s to the server. The client B does the same as the client A except that he has different original polynomial and random polynomial). $\endgroup$ – user153465 Oct 1 '14 at 15:42
  • $\begingroup$ @poncho He evaluates on the same X’s to obtain another values say Z’s. He sends to the server too. The server can do computation and return to each client. I need to prove that each client’s polynomial P1 are semantically secure. So if we consider a share as a polynomial in the question I mentioned we can reduce it to the SSS. The polynomial recovery can be done by the one knows the inverse of two random polynomial (e.g. in multiplication) $\endgroup$ – user153465 Oct 1 '14 at 15:42
  • $\begingroup$ @user153465: if my edits to the question were inaccurate, please go ahead and reedit the question. $\endgroup$ – poncho Oct 1 '14 at 15:57
3
$\begingroup$

For security in Shamir secret sharing we need that the coefficients of the polynomial are independent and uniformly random in the field. Multiplying the polynomial by a constant from the field does not change this, so yes, you can do it and still be secure.

In fact, in multiparty computation, something akin to this is done when we want to privately multiply a secret shared value by a known, public constant. We multiply each share by that constant. The effect of this is multiplying the polynomial by the constant.

Obviously there are some corner cases to consider. The secret cannot be $0$. If the constant term of the polynomial is $0$, you might also run into problems (depending on the application).

It is important that the secret you multiply by is in fact a single element from the field and not a polynomial itself. If it is a polynomial, then two problems occur. The coefficients are no longer independent and the degree of the polynomial changes.

Without knowing your application, however, it it hard to say whether or not this is useful. Can you still recover the original secret? Only if you know the constant term of the original polynomial, right?

$\endgroup$
  • $\begingroup$ In the above model if an adversary picks 9 and 8 (as two secrets) sends them to the oracle and oracle picks (2x) as the polynomial, then he evaluate on 1,2 to obtain (1,18) and (2,36), and returns one of the shares e.g. (2,36) to the adversary. The adversary can figure out to which secret it belongs as it is a multiple of 9, however if the modulus N are small this can be addressed or we can pick some large x values. So it is somehow depends on the size of modulo N, but we do not have this problem with original SSS. I’ll explain later what the application of the proposed model is. $\endgroup$ – user153465 Oct 1 '14 at 15:04
  • $\begingroup$ @user153465 your example here assumes that the adversary knows that the constant term of the polynomial is $0$. Like I said in my answer, if the constant term of the polynomial is $0$ (or in this case, knows to be $0$ by the adversary) there is an issue. If the constant term is not necessarily $0$, the adversary does not know which secret the belongs to. $\endgroup$ – mikeazo Oct 1 '14 at 15:10
  • $\begingroup$ the problem still exists if he have (2x+3) where 2 and 3 are random values. $\endgroup$ – user153465 Oct 1 '14 at 15:13
  • $\begingroup$ @user153465 I think I see what you are saying. Since $2x+3$ becomes $18x+27$, all shares will be a multiple of $9$, so the adversary can figure that the secret is $9$. $\endgroup$ – mikeazo Oct 1 '14 at 15:18
  • $\begingroup$ Yes, would it make sense (in terms of security) that I say I pick any x values greater than equal to (N/2)+1 ? $\endgroup$ – user153465 Oct 1 '14 at 15:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.