1
$\begingroup$

I'm working on understanding and implementing

Damgård, I., & Dupont, K. (2005). Efficient Threshold RSA Signatures with General Moduli and No Extra Assumptions. Public Key Cryptography-PKC 2005, 346–361. doi:10.1007/978-3-540-30580-4_24. Retrieved from http://www.iacr.org/cryptodb/data/paper.php?pubkey=3431

On page 7 (356), step 2 of the key share generation process is

$D$ chooses a random polynomial $f(x)$ of degree at most $t$ with integer coefficients, such that $f(0) = d$; $$ f(x) = d + c_1x + \ldots + c_tx^t$$ where the $c_i$'s are random independent integers chosen from the interval $[0\ldots\Delta{}n2^t2^L]$, where $L$ is a secondary security parameter. The secret share of the $i$'th server is $s_i = f(i)$. With the given choice of coefficients, it can be shown that, if we compare the distribution of any $t$ shares resulting from sharing $d$ with the one sharing resulting from sharing any other $d^\prime$, the statistical distance between the two is at most $2^{-L}$.

($n$ is the standard RSA modulus; $d$ the standard RSA secret exponent; $l$ is the number of secret shares/servers; $\Delta = l!$; $t$ is the maximum number of corrupted servers/shares we want to accept)

The given formula for secret shares makes them numerically rather larger than the original secret (by a factor of something like $l^t \cdot l! \cdot 2^{tL}$). I think I can reduce them $\text{mod } \phi(n)$, since the further calculation of partial signatures/decryptions uses the shares in a standard RSA operation (with some extra multipliers): $x^{2\Delta{}s_i} \text{ mod } n$.

Question 1a: Will this modulo operation break the functionality of the scheme? I did some experiments, and think it will work, but have no firm basis. From all the papers I've read I seem to understand that doing operations $\text{mod } \phi(n)$ in the exponents is always right, but I don't understand why and thus can't apply this understanding here.

Question 1b: Will this modulo operation break the security of the scheme? I have an intuition that one of the options might be bad, but can't tell which. Points I've considered:

  • Without modulo, it's standard Shamir secret sharing, so an attacker with up to $t$ shares shouldn't learn anything.
  • $\phi(n)$ is a secret, so applying it might give the attacker something he wouldn't otherwise have.

Question 2: The last sentence of the section I quoted leaves me at a loss. The authors cite "M. Koprowski: Threshold Integer Secret Sharing, manuscript, 2003", but I couldn't find a copy of that online. What is the "distribution of shares" and "statistical distance" and why is it important here? Shouldn't Shamir sharing unconditionally hide all information about $d$ ($=c_0$) if all $c_i$ are from the same number space? I assume that the last part of the quoted sentence means that I should set $L$ to something like 128 for 128 bit security?

$\endgroup$
  • $\begingroup$ If I am understanding the protocol, this isn't shamir secret sharing. In shamir secret sharing, the coefficients are drawn uniformly at random from a finite field and the evaluation of the polynomial is computed in the finite field too. In this, the coefficients are chosen from an interval and the shares are not computed within a field. $\endgroup$ – mikeazo Feb 3 '15 at 20:55
  • $\begingroup$ So, re 2, you aren't guaranteed to "unconditionally hide all information about d". So, proving that the statistical distance between the two distributions of shares resulting from a sharing of $d$ and any other $d'$ is important in proving security. $\endgroup$ – mikeazo Feb 3 '15 at 20:57

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.