I reviewed the paper "Secret sharing homomorphisms: keeping shares of a secret secret" by J.C. Benaloh yesterday and I had some difficulty understanding his version of verifiable secret sharing to address " k-consistency."

We say that a set of n shares $s_1$, . . . , $s_n$ is k-consistent if every subset of k of the n shares defines the same secret.

The literature goes on to state that

It is easy to see that in Shamir's scheme, the shares $s_1$, . . . , $s_n$ are k-consistent if and only if the interpolation of the points (1, $s_1$), . . , (n, $s_n$) yields a polynomial of degree at most d = k - 1.

My first question is that I can clearly see that the polynomial of degree at most (k-1) will imply that any subset of the k parties will be able to recover a number (secret) but I don't see how this guarantees that they will be able to recover exactly the original secret.

In a later paragraph, the following statement is made

For each polynomial P' not in A, the (point-wise) sum P + P' is opened by releasing $S_i$ + $S'_i$ (mod r) and $x_i$ * $x'_i$ * $(y_{i})^{\lfloor{(S_i + S'_i)/r}\rfloor}$ where the ith point of P' is given by E($s_i, x_i, Y_i, N_i$)

I understand that we are using a homomorphic encryption scheme here and the reason to do so is that we cannot release values from the chosen polynomial P (which evaluated at 0 gives us our secret.) Hence, we need to perform computations on the encrypted points and function values.

I am unable to understand the why the point-wise polynomial addition is so complicated - I would have imagine it just involved adding the function values modulo r?

For reference, here is the encryption scheme described in the paper -

Before beginning, a prime number r is fixed such that r $\geq$ $\vert$ S $\vert$ the size of the secret domain. To develop an encryption function E, one selects primes p and q such that r $\mid$ (p - 1) and r $\nmid$ (q - 1). Let N be the product N = p*q. The developer releases the pair (N, y) where y is relatively prime to N and y is not an rth residue modulo N. To use E to encrypt a value s, one randomly selects an z and forms E(s, x, y, N) = $y^s * x^r$ (mod N)

Apologies for a rather long question - thanks in advance!

  • 1
    $\begingroup$ 1. If the $deg>k-1$ than no secret is revealed. Since we cannot define the polynomial. $\endgroup$ – kelalaka Oct 25 '18 at 7:20
  • $\begingroup$ @kelalaka that is very true - I agree. However, I struggle to explain to myself how being able to recover the polynomial guarantees the exact secret shared originally will be revealed. Unless this is extremely naive on my part! $\endgroup$ – Rahul Mathur Oct 25 '18 at 8:39
  • 1
    $\begingroup$ It is the basics of Shamir's sheme. if the number of points is less than the degree of the polynomials, the polynomials cannot be determined. To see that look at the Lagrange polynomial, and see that if the given points are less than $deg+1 < k$ than there is no unique solution. $\endgroup$ – kelalaka Oct 25 '18 at 8:44
  • $\begingroup$ @kelalaka ah yes of course - apologies for not realizing this earlier! $\endgroup$ – Rahul Mathur Oct 25 '18 at 9:21
  • 1
    $\begingroup$ What do you mean by complicated? $\endgroup$ – kelalaka Oct 25 '18 at 11:50

Your Answer

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

Browse other questions tagged or ask your own question.