0
$\begingroup$

I'm trying to interpolate a Shamir secret in the exponent based on Boneh's and Shoup's book, Section 22.1 and Corollary 22.2. I think I understand how the scheme works, but I'm stuck now with some computations in a toy example that I've come up with. I'm a beginner so likely this is a beginner's mistake, any help would be appreciated! (The notation in here is based on Boneh's and Shoup's).

Setup. In my example I'm working in $\mathbb{Z}_{127} = \{0,1,\ldots,126\}$ with $N=5$ shares and threshold $t=3$. The randomly generated polynomial is $\omega(x) = 84x^2 + 48x + 57$ with secret $\alpha=\omega(0)=57$. The $N=5$ key shares are $\alpha_1=\omega(1) = 62$, $\alpha_2=\omega(2) = 108$, $\alpha_3=\omega(3) = 68$, $\alpha_4=\omega(4) = 69$, and $\alpha_5=\omega(5) = 111$.

In this example, secret alpha $\alpha$ is recovered using the key shares of servers $J = \{2,4,5\}$. The corresponding Lagrange coefficients are:

  • $\lambda_2 = \frac{0-4}{2-4}\frac{0-5}{2-5} = 88$
  • $\lambda_4 = \frac{0-2}{4-2}\frac{0-5}{4-5} = 122$
  • $\lambda_5 = \frac{0-2}{5-2}\frac{0-4}{5-4} = 45$

Problem. I'd like to compute $h^\alpha$, where $h$ is a user provided (blinded) value, without actually recovering $\alpha$ at one server (though that's not relevant right now). Assuming $h=89$, the result should be $89^{57} = 125$, but based on my computation I end up with something different. I'm trying to understand why.

Based on Corollary 22.2 we can compute: $ h^\alpha = \Pi_{j \in J}(h^{\omega(j)})^{\lambda_j}$, where $\omega(j) = \alpha_j$.

  • $(h^{\alpha_2})^{\lambda_2} = (89^{108})^{88} = 32$
  • $(h^{\alpha_4})^{\lambda_4} = (89^{69})^{122} = 16$
  • $(h^{\alpha_5})^{\lambda_5} = (89^{111})^{45} = 111$

But, $32 \times 16 \times 111 = 63 \neq 125 = 89^{57}$.

I might be computing the exponentiation incorrectly, but don't know exactly where the problem is. Any help would be appreciated.

$\endgroup$
2
  • $\begingroup$ Are you sure about 89^(88*108) = 32? $\endgroup$ Jul 17 at 17:09
  • $\begingroup$ Oops. Forget about the previous comment, I made a mistake in my calculations as well. $\endgroup$ Jul 17 at 21:47

1 Answer 1

1
$\begingroup$

Here's your problem: you're computing the Lagrange coefficients modulo 127, however since you're computing the shared secret using operations in $\mathbb{Z}^*_{127}$, you have to compute them modulo the order of that group.

Now, the order of that group is 126, which is very much not a prime. Now, multiplicative finite field groups are rarely prime [1], and so that would appear to be an issue.

Now, we can make this "blinded shared secret recovery" work; here are two ways:

  • Use a "safe prime" modulus; that is, use a modulus $p$ such that $q = (p-1)/2$ is also prime. Then, we perform all the operations on "quadratic residues", that is, values $x$ such that there exist a value $y$ with $x = y^2 \pmod p$ (and there are $q$ such values). We require the blinded value to be a quadratic residue (and perform the shared secret operations modulo $q$).

  • Perform the operations on an elliptic curve with a prime number of points; unlike finite fields, there do exist elliptic curve groups with a prime number of points (and we can do the shared secret operations modulo that prime)


[1]: Exceptions would be $GF(3)$ (not interesting) and $GF(2^x)$ where $2^x-1$ is a Mersenne prime (which could be done, but $x$ would need to be quite large to make the known small characteristic discrete log algorithms infeasible, and in any case is probably not well suited for someone who is just learning)

$\endgroup$
4
  • $\begingroup$ Thank you! Quick follow-up, why is it 126 elements? I'll look into elliptic curves next, but I first wanted to try an example that I could easily do by hand. $\endgroup$
    – k13n
    Jul 17 at 17:04
  • $\begingroup$ @k13n: It has 126 elements because there are 126 values relatively prime to 127. If you want to try a toy safe-prime example, try 167 (which has 83 quadratic residues) $\endgroup$
    – poncho
    Jul 17 at 17:30
  • $\begingroup$ I tried to recompute this, and it seems the issues stemmed from a mistake in $(h^{\alpha_2})^{\lambda_2} = (89^{108})^{88} = 32$. Otherwise, the reconstruction works. $\endgroup$ Jul 17 at 21:08
  • $\begingroup$ Huh, what I wrote there doesn't make much sense. My sagemath computation was just wrong🙃 $\endgroup$ Jul 17 at 21:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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