3
$\begingroup$

I have seen that in MPC multiple models in different dimensions can be envisioned, like asynchronous vs synchronous networks, access to broadcast channels, and so on. However, a particularly interesting dimension is whether point-wise private and authenticated channels are available. In this direction, I have seen papers using the terms plain model, CRS model, or PKI model. I would like to understand what these models actually mean.

My concrete questions are the following:

  • I understand that the CRS model refers to a setting where a common reference string is provided to all parties. How can this help in computation? (any pointer to a concrete protocol that uses such setup would be welcome).
  • I assume that the plain model is just the lack of any setup like a CRS. Does this mean that not even secure channels are assumed? I can't think of a protocol for more than 2 parties that works in this setting. Again, pointers would be welcome.
  • If a public-key infrastructure (PKI) is assumed, what is it used for? Establishing secure channels?
$\endgroup$
4
$\begingroup$

I understand that the CRS model refers to a setting where a common reference string is provided to all parties. How can this help in computation? (any pointer to a concrete protocol that uses such setup would be welcome).

One typical approach is that the parties will treat the CRS as the public key of an encryption scheme, and encrypt their inputs under this key. They can prove things about this ciphertext in zero-knowledge for the rest of the protocol. This overall approach is useful because the simulator can generate the CRS to be a public key for which it knows the corresponding secret key, and therefore decrypt the parties' encryptions of their inputs. An example of this approach is in Canetti et al.

Beyond this, CRS is a fundamental part of the syntax for non-interactive ZK (NIZK). If the simulator generates the CRS with a trapdoor, they can generate proofs of false statements. But without the trapdoor, only proofs of true statements can be generated.

Another cute and totally different approach for a CRS is from Peikert et al. They construct oblivious transfer protocols in the CRS model. The CRS can be of two different flavors. If the CRS is of one flavor (think of a Diffie-Hellman triple $g^a, g^b, g^{ab}$) then the protocol can be proven information-theoretically secure against the receiver. If the CRS is of the other flavor (think of a random triple $g^a, g^b, g^c$) then the protocol can be proven information-theoretically secure against the sender. The fact that the two CRS flavors are indistinguishable means that the protocol actually gives (computational) security against both parties.

I assume that the plain model is just the lack of any setup like a CRS. Does this mean that not even secure channels are assumed? I can't think of a protocol for more than 2 parties that works in this setting. Again, pointers would be welcome.

If you have authentic channels, then you can get secure channels using standard public-key encryption. So it is standard to just assume secure point-to-point channels. The bigger challenges are: (1) how to get broadcast from point-to-point channels; (2) what happens when you don't assume even authentic channels?

(1) is relatively standard. There is very little work on (2), but one paper I know of is Barak et al. Basically, without authentication it is inevitable that the adversary can partition the honest parties into disjoint and isolated groups, that each perform their own separate computation.

If a public-key infrastructure (PKI) is assumed, what is it used for? Establishing secure channels?

You can bootstrap privacy from nothing (using key agreement), but you can't bootstrap authenticity from nothing. PKI is the root of trust for authenticity.

$\endgroup$
3
  • 1
    $\begingroup$ Thanks a lot for the answer Mike, this definitely clears up a bunch of doubts! I encountered these terms in works about round-optimal MPC, now it makes sense: You can get everything from the plain model (which already has authentication in it), but you need more rounds for it, so protocols in the CRS or PKI model can have less rounds. Also, a quick side question: A CRS is not really comparable to correlated randomness right? Someone stated they are the same here crypto.stackexchange.com/a/76292/13843, but I don't think that's true (as I comment there). Thanks! $\endgroup$
    – Daniel
    Jun 8 '20 at 21:14
  • $\begingroup$ Correlated randomness means that Alice has X and Bob has Y where $(X,Y)$ comes from some joint distribution. A CRS is the simplest correlation where $X=Y$. Less trivial correlations let you do more interesting stuff directly (and information-theoretically). $\endgroup$
    – Mikero
    Jun 8 '20 at 21:24
  • $\begingroup$ Exactly, that makes sense: A CRS is a particular case of correlated randomness. All this cloud of concepts makes much more sense now, thanks a lot! $\endgroup$
    – Daniel
    Jun 8 '20 at 21:28

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.