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.
