I have been looking at the threshold (EC)DSA schemes for honest majority by Gennaro et al. https://www.sciencedirect.com/science/article/pii/S0890540100928815. In the scheme, there are steps where we wish to open the product of Shamir secret sharings. So for example [a],[k] are degree-t sharings of a,k respectively, each party i holds shares [a]_i, [k]_i, and we wish to reveal the value a*k to all parties. The paper explains that while parties can compute [a]*[k] locally, this does not yield a random degree 2t-sharing of a*k (in particular, the polynomial underlying the sharing can not be irreducible) and so revealing [a]_i*[k]_i could leak information about a and k. To get around this, parties additionally hold shares of a degree-2t sharing of 0, denoted here as [z], which they add to their shares of [a]_i*[k]_i to re-randomize it. All parties therefore reveal their shares of [a]_i*[k]_i + [z]_i, from which ak (and the polynomial it lies on) can be interpolated.

I understand that taken by itself [a]*[k] + [z] is a random degree-2t polynomial with constant term ak and so doesn't leak any information about a or k. However, here the attacker also knows shares of [a],[k], and [z] and what I'm struggling to understand is how to argue that [a]*[k] + [z] is a random sharing and doesn't leak anything conditioned on this knowledge. For example, working in a field of size q, if the attacker controls t replicas it can reduce the possibilities for the polynomials sharing [a],[k] to sets of q possibilities each, and [z] to a set of q^t possibilities (since they know t shares of [z] plus point at 0). So this gives q^(t+2) possibilities for the polynomial underling[a]*[k] + [z], which is less than the q^2t possibilities there would be for the polynomial underlying a random sharing of ak.

I know this is quite a standard trick that I've seen in other papers so I must be missing something, but I haven't been able to find a detailed proof of why this works. If anyone could help me understand the intuition behind this that would be much appreciated.

  • $\begingroup$ If I understand the question, my intuition is that if you're working in a field of size q, as long as the solution is constrained to a larger number of possibilities than q, and you're not revealing information that limits the options within q, there's no useful disclosure, as the most effective attack is still brute-force over q. $\endgroup$
    – Tim Dierks
    Feb 11 '21 at 19:02
  • $\begingroup$ Thanks for your answer. There are more than q choices for the polynomial underlying the product sharing, but couldn't there still be a bias on the constant term of these polynomials so some values of ak are more likely than others? $\endgroup$
    – HelenW
    Feb 12 '21 at 0:01

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.