0
$\begingroup$

all,

I have a very fundamental question on Secret Sharing schemes such as SPDZ families.

As far as I can see for now, SS schemes always assume a certain variable range. For example, suppose the bit length of the variable is $k=32$ and its underlying operational domain is in $p$ ($p$'s bit length is $l=128$), then, all secret values $x$ are shared within $[-2^{31},2^{31}-1]$.

But, when it comes to generate random numbers, I am a little confused. Say, I am trying to generate a Beaver's Triple, should I have $c=a\cdot b$, where all these numbers are shared within $[-2^{31},2^{31}-1]$, or should I have all these numbers shared under $p$. From the original paper itself, I cannot find the answer. Therefore, I want to ask here for some help and the insight why it should be this case. And should it be with the same case as ABY or any other frameworks?

Thanks for help and suggestions!

$\endgroup$
2
  • 1
    $\begingroup$ SPDZ, ABY, please define for readability of question. $\endgroup$ – kodlu Oct 4 '20 at 20:34
  • 1
    $\begingroup$ @kodlu, This SPDZ and ABY are two typical protocols that implement SS schemes. So, by name itself in the MPC domain, it should be clear enough. $\endgroup$ – alexander Oct 5 '20 at 4:43
3
$\begingroup$

A secret-sharing scheme allows you to distribute a secret message among multiple parties. However, a fundamental question is how this message is represented. In many SS schemes, this message is an integer between $0$ and some maximum value $M-1$ (for unsigned values), and whenever you add secret-shared values, the addition happens modulo $M$.

Addition modulo a number is not very useful in applications, so one typically considers secret to be much smaller than the modulus in the scheme so that wrap-arounds do not occur. This is what happens in your example when you propose a large prime modulus and a much smaller size for the actual data.

However, what you have to understand here is that this difference in the sizes of the data and the modulus exists only to enable some applications, but the actual MPC protocol doesn't care about the sizes of the underlying data: It just assumes it is smaller than the modulus. This is very similar to programming: If you use data types that are 64-bits long, any wrap-around modulo $2^{64}$ when adding variables is the programmer's fault, since the program doesn't really care about this.

Given this, and to answer your concrete question, protocols usually consider the computation to be defined over certain domain, like integers modulo a prime $p$, and they don't really care about what data is fed to them. In particular, whenever you see something like "sample a random value", it typically means random in the whole domain, that is, random between $0$ and $p-1$ (for unsigned, although this is irrelevant). For the case of triples, this has to be the case, since these random values are used to mask the inputs to the multiplication gates, so they have to be chosen uniformly at random in the whole domain so that the reconstructed value leaks nothing about the sensitive inputs.

$\endgroup$
1
  • $\begingroup$ Well, this explanation sounds good, thanks for your help! $\endgroup$ – alexander Oct 7 '20 at 13:02

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.