0
$\begingroup$

If I have number $2$, which is additively shared into $3+4 \bmod 5$. Now I need to change the filed to a large one, like $500$.

How to convert the shares, so that I can have a new number or shares $a+b \bmod 500 = 3+4 \bmod 5$.

$\endgroup$
  • 2
    $\begingroup$ Welcome to crypto.SE! Observe that $3+4 \bmod 5$ is $2$, not $7$, and/thus it is unclear what we are starting from. Also, "point conversion" is unclear. Is it that it is wanted to convert the existing secret shares so that the original secret is unchanged? Does something change in the number of participants to the shares, and the threshold for recovery, if any? Nitpick: a field with $500$ elements is larger than one with $5$, but that's generally not considered a large finite field in a cryptographic context, where often fields have $>2^{512}$ elements. $\endgroup$ – fgrieu Jun 25 at 10:09
  • $\begingroup$ Thanks for pointing out the problem. I've edited it again. So my question is how to convert the old share to new share in the larger field. Except the field, everything remains unchanged. $\endgroup$ – jiajie zhang Jun 25 at 11:37
  • $\begingroup$ What is the intention? Why don't you just create new shares with a secure field? $\endgroup$ – kelalaka Jun 25 at 11:37
  • $\begingroup$ yeah, I know it might be a little bit weird. But I need to do some multiplication later, it will be computed in a large field. Hence, I want to make sure the reconstruction of the two shares shouldn't be changed because of the field changing. $\endgroup$ – jiajie zhang Jun 25 at 11:41
  • 1
    $\begingroup$ If you really need a field (e.g. so you can add and multiply and so nonzero elements are always invertible), note that a finite field always has a size (order) that is a prime power, that is, is of the form $p^k$, for some prime $p$ and some integer $k \ge 1$. 500 cannot be represented in this form, hence there is no finite field of that size. If you're asking "how to map elements from a field of order $p$ to a field of order $p^k$ (e.g. 5 -> 625)", that's easy; however I suspect there's more to your question... $\endgroup$ – poncho Jun 25 at 12:14
2
$\begingroup$

I think that what the OP is thinking about is a $(2,2)$ additive secret-sharing scheme in which a secret $S$ is split into two shares $X\neq 0$ and $S-X\neq S$. Here, $X$ is an arbitrarily chosen nonzero integer. Neither share holder can determine the value of $S$, but when both shares are submitted to the trusted reconstructor, the reconstructor can recover $S$ as the sum of the two shares. In the OP's scheme, $S=2$ is split into shares $3$ and $4$ where right-handed folks can assume that $X=3, S-X=4$ while left-handed folks can assume that $X=4, S-X=3$ and all of these elements are assumed to be elements of $\mathbb F_5$. Thus, the secret $S = (X) + (S-X)$ (which has value $7$ in ordinary integer arithmetic) is also an element of $\mathbb F_5$ and works out to be the correct value $2 \in \mathbb F_5$.

The OP then wonders

Assuming that the secret $S$ continues to have value $2$, what should the share values $a$ and $b$ be so that $a+b = 2\bmod 500$?

Note that we do not necessarily have to have a field of order $500$ (as the OP mistakenly assumes exists) for this simple additive secret-sharing scheme; the additive group $\mathbb Z_{500}$ will work just fine. So, the answer to the OP's query is that the share values can be any two integers whose sum is $2$ modulo $500$. For example, the shares could be $(a,b) = (3,499)$ or $(a,b) = (498,4)$ if we choose to keep one of the two share values the "same" as before; with quotation marks around same to remind folks that $3,4,498, 499$ are elements of $\mathbb Z_{500}$, not $\mathbb F_5$. It is, of course, an added bonus that $a+b\mod 500 = a+b \mod 5$. But other choices would work equally well; $(a,b) = (251,251)$ will stop juvenile bragging rights arguments among share holders ("neh, neh, ni, neh, neh, my share is bigger than yours!").

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Actually, I believe that it is computationally infeasible to stop all juvenile arguments (for proof, see your favorite social media site :-) $\endgroup$ – poncho Jun 26 at 14:57
  • $\begingroup$ The exclusion $x \ne 0$ is a fallacy. If you exclude 0, then it's not information theoretically secure any more. $\endgroup$ – tylo Jun 26 at 17:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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