Interpolation of Shamir secret in the Exponent

Question

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.

Answer 1

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)