2
$\begingroup$

Imagine the case where you have a sufficiently large finite field (or any multiplicative field for that matter) $\mathbb{Z}_{p}$ where p is some large prime.

Now, I have a number $g \in \mathbb{Z}_{p}$ (for this example let us say some RSA cipher text) and a secret shared key $k\in \mathbb{Z}_{p}$ (using shamir secret sharing).

My objective would be to use some threshold decryption techniques to do so. Mainly having each party holding a share of the key calculating $g^{\alpha \cdot k_{n}}$ and then multiplying them.

Given that when we operate on the exponent, we are working on $\mathbb{Z}_{p-1}$ instead of ${\mathbb{Z}_{p}}$… would that be a problem? If so, how can we avoid it?

An example of what I mean:

The base and the exponent in this case are on $Z_p$. When the reconstruction happens, each party does base to the power of its share \times $\alpha$ but exponent operations are base $p-1$. E.g. Base $7$.. $3^6$ is $1$ if I secret share the $6$ and get $\alpha \times s : 6,6,1$ that added are $13 \pmod 7 = 6$. But if I do $3^6 \times 3^6 \times 3^1= 3$ which is $3^{13 \pmod 6}$.

$\endgroup$
  • $\begingroup$ What is $\alpha$? Also, the example you show is NOT RSA since it works in $Z_{pq}$ which is NOT a field. In RSA the base is the message, you use $g$ suggesting a generator is the base. None of this makes any sense to me but maybe it does to others. $\endgroup$ – kodlu Jun 21 '17 at 21:58
  • $\begingroup$ So $\alpha$ are in this case the interpolation coefficients of for instance Shamir, or any other secret sharing scheme, is just a way to generalize it. Then for the example is irrelevant if it's pq or p.. the field is bounded by some prime or an RSA modulus. I just use $g$ to relate with pk notation but that is also irrelevant to the question.. which is how does the fact that the exponent and the base work modulo p and p-1 respectively does affect the schemes when threshold decryption in the way expressed here, is used: $\endgroup$ – DaWNFoRCe Jun 21 '17 at 22:45
  • $\begingroup$ It's not irrelevant those are different algebraic structures. In general if you operate in the multiplicative group of integers modulo $n$ then the exponent operations are modulo $\varphi(n)$ modulo Euler's Totient. And Shamir would need a field for uniqueness of polynomial operations. But the exponent operations are always in a direct product of cyclic groups, so maybe a subgroup is needed? You need to provide proper math details or a link. $\endgroup$ – kodlu Jun 21 '17 at 23:03
  • $\begingroup$ Hi, Imagine a sufficiently large $Z_{p}$ that is much larger than your encrypted and message domain. Is simple $\endgroup$ – DaWNFoRCe Jun 22 '17 at 16:22
  • $\begingroup$ I am sorry but in the exponent, the operations are modulo $\varphi(p-1)$ which is not a field, which doesn't support unique interpolation. This is my last comment on this. $\endgroup$ – kodlu Jun 22 '17 at 21:18

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.