In the SecureML paper, one can assume that two non-colluding servers can run secure two-party computation protocol based on secret sharing with the help of a third party (client). The client would send correlated randomness to the servers in offline phase, which can accelerate the computation in online phase, e.g. multiplication using Beaver's multiplication triplet. I'm wondering how the security of this type of secure two-party computation is defined. Is it secure if one of the servers and client collude? Since the client knows the information about all the correlated randomness, does it incur some security flaw if that happens?


This is the so-called Common Reference String (CRS) model, or Correlated Randomness model. A good reference to it is the paper On the Power of Correlated Randomness in Secure Computation.

Secure multiparty computation (MPC) can be expensive (in terms of computational or communication complexity) when a trusted party (the one doing all the computation in secrecy) doesn't exist. Secure MPC is easy when a central trusted party can execute all in secrecy, but this is what everybody doesn't want.

With the CRS we have an interesting model: the creator of the randomness is usually a trusted party. But, this trusted party can be unaware of the computation the parties intend to execute. So the model separate who knows the joint randomness, and who execute the computation. And by supposing a CRS, we can reach secure MPC at a low price. Therefore, the belief that the CRS can't be compromised is a cornerstone of the model: it doesn't compute, but if it leaks the randomness, everything falls flat.

| improve this answer | |
  • $\begingroup$ How can the CRS and the Correlated Randomness model be the same? In the CRS there is a single string sent to all participants, but in the correlated randomness model, each participant should get a string and the other participants should not learn it $\endgroup$ – Daniel Jun 8 at 13:41
  • $\begingroup$ @Daniel, to be exact, you are correct. In fact, one is an particular case of the other. $\endgroup$ – McFly Jun 14 at 18:27

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.