8
$\begingroup$

I was reading Canetti00 Universally Composable security paper. The first page of introduction says that there are some MPC protocols and Zero knowledge protocols that are insecure under concurrent composition. I don't see why protocols might break when concurrently composed together.

Please provide some examples of protocols that are insecure under concurrent composition.

Does the same type of attacks hold for parallel composition? What's the difference?

Does the same type of attacks hold if the protocols are run many times one after another (Let's say to improve soundness error)?

Edit: @Mikero gave a nice MPC protocol that is not secure under concurrent composition. Can anyone give an example of ZK protocol that is insecure under concurrent composition?

$\endgroup$
10
$\begingroup$

Consider the function $f : \{L,R\} \times \{ U,D \} \to \{0,1,2\}$ defined by the following table:

$$ \begin{array}{c|cc} f & L & R \\ \hline U & 0 & 0 \\ D & 1 & 2 \end{array} $$

Let's say Alice has input from $\{L,R\}$ (she chooses a column) and Bob has input from $\{U,D\}$ (he chooses a row).

A simple protocol for $f$ is as follows:

  1. Bob announces his input in the clear. If his input is $U$, then parties can halt, as they know the output must be 0.
  2. If Bob's input is $D$, then Alice announces her input in the clear. With both inputs known, the parties can compute the output.

This protocol is secure against active adversaries in a standalone security model, but it is insecure when three instances are executed concurrently.

Imagine the following scenario:

  • Bob is honest and chooses one of the instances to have input $U$ and the other two to have input $D$. There are three such combinations ($UDD, DUD, DDU$) and he chooses with uniform probability.

  • Alice is corrupt. She wins the game if she can cause the 3 instances to have all distinct outputs. It's not hard to see that she can only win by using different inputs in the two instances where Bob chooses input $D$.

If parties have access to 3 parallel instances of ideal $f$, then it is easy to see that Alice can only win with probability 1/3. In this setting, Alice's choice of input is independent of Bob's. There must be (at least) two $f$-instances where Alice uses the same input, and with probability 1/3 those will both be ones where Bob uses input $D$.

But in the presence of concurrent protocol instances, it is easy for Alice to win with probability 1. The protocols can be run in lockstep, and Alice just waits for the first protocol message in each instance. Then she can send appropriate (different) protocol messages in the instances that proceed to step #2.

Since Alice can influence the protocol in some way that she cannot influence ideal instances of $f$, the protocol is insecure in this setting.


This example is a bit simplified. I assumed that the ideal calls to $f$ were done in parallel. But it is not hard to adapt this kind of example to different requirements on the ideal world.

The big picture is that a standalone-secure protocol can leak some information early in the protocol, with the reasoning that this information is something that could be deduced from the output anyway (like Bob's input in this case). But in the presence of concurrent composition, and correlated inputs between different instances, this kind of leakage can be unsafe.

$\endgroup$
  • $\begingroup$ Excellent answer. For this functionality, is there a simple UC secure protocol? In general, how to make sure partial information about the output is not leaked in an intermediate step? $\endgroup$ – satya Jun 16 at 23:22
  • $\begingroup$ Without a trusted setup, there is no UC-secure protocol for this functionality. This follows from our characterization in ia.cr/2008/454 .. with a trusted setup you can UC-securely realize it with your favorite general-purpose MPC protocol. $\endgroup$ – Mikero Jun 17 at 2:31
  • $\begingroup$ That's interesting. I thought there is a UC secure MPC protocol for every functionality, just like the generic garbled circuits approach. $\endgroup$ – satya Jun 17 at 2:54
  • 2
    $\begingroup$ There is a UC-secure MPC protocol for every functionality in the CRS model only. In the plain model, where no access to a common reference string is assumed, it is known that many functionalities cannot be UC-securely implemented - this includes many natural and useful functionalities, not only "special" examples such as given by Mikero. $\endgroup$ – Geoffroy Couteau Jun 17 at 10:22
2
$\begingroup$

Theorem 3.2 of the following paper presents a constructive counterexample for ZK concurrent composition about the DL problem. It is a very interesting construction.

Uriel Feige, Adi Shamir. Witness Indistinguishable and Witness Hiding Protocols (STOC'90). https://www.isical.ac.in/~rcbose/internship/lectures2016/rt02feigeshamir.pdf

$\endgroup$
  • $\begingroup$ Nice example. In the standalone setting of the protocol, the verifier learns the witness with negligible probability. But in Remark 2, they mention that this violates the Zero Knowledge property. Why is it the case? $\endgroup$ – satya Jun 17 at 14:11
  • $\begingroup$ I read the paper again and feel that Remark 2 could have been stated more clearly. I think it refers to general-purpose proof systems (\bar{P}, \bar{V}) constructed using the same idea (not necessarily about discrete log): The verifier generates a proof of knowledge of a witness, and if the proof is valid (not necessarily using the witness that \bar{P} knows), then \bar{P} reveals the witness. $\endgroup$ – Weikeng Chen Jun 18 at 14:52
  • 1
    $\begingroup$ Consider that people know in public a list of hashed password $L$. People want to prove that "I know at least one of the preimages of hashed password in this list". The prover $P$ knows one of the original passwords (which is a witness of the proof of knowledge), and the verifier $V$ knows another one (which is a different, but valid witness). Now, $V$ can trick $P$ into revealing the password preimage that $P$ knows, and now $V$ knows two password preimages. $\endgroup$ – Weikeng Chen Jun 18 at 14:54
2
$\begingroup$

An additional example to complement the other answers: the classical zero-knowledge protocol of Goldwasser, Micali, and Rackoff, based on quadratic residuosity (here), is perfectly zero-knowledge (and its statistical soundness can be made negligibly small via sequential repetition). A long standing open problem has been to understand whether it remains zero-knowledge under parallel composition. It was recently shown in a sequence of papers, culminating with this paper and this paper, that under standard cryptographic assumption (here, LWE), it is provably not secure under parallel composition.

To complement the great answer of Mikero, I will also try to explain why the proof strategy used in the standalone setting will often break down in the concurrent setting. This provides an intuition of why the proofs must be refined, complementary to his pathological example.

Another way to understand the source of the difference between the standalone model and the UC model is the following: often, a proof of security will involve a simulator that interacts with the other parties, and manages to extract some specific value from this interaction, which he uses to simulate the protocol. In a real run of the protocol, however, this value can typically not be extracted, since it would break the security of the protocol. Hence, the simulator must, in some sense, be given some "additional power" over a normal player to be able to simulate the protocol (think about zero-knowledge proof: clearly, if the prover could simulate the proof without knowing the witness, which the simulator must do, then this prover would break the soundness of the proof).

So, what is this additional power the simulator is given? It's the following: unlike a normal player, the simulator is given the code of its opponent. Hence, it can interact with this code as he like; in particular, he can uses what is known as a rewinding strategy: running the code with breakpoints and forking it at difference steps, to force some correlations to appear between the values computed by the opponent, from which the simulator extract some value (I'm being purposely vague here, but see for example my walkthrough here of such a strategy to prove soundness on an example zero-knowledge proof).

Rewinding is fine in a standalone setting: you can rerun (polynomially)many times the code to extract some value. However, imagine now the same protocol is ran many times concurrently. Now, you need to analyze the security of the full protocol. But the rewinding strategy might now fail: if the composed protocol has a nested structure, rewinding it might require recursive rewinds of its components, which can cause a rewinding explosion: even if the protocol consists only of polynomially many components, rewinding it requires exponentially many rewinds of the internal components. Therefore, even though a simulator can extract the appropriate values for each standalone run of the internal components, it will fail to use the rewinding strategy to extract the appropriate value from the full composed protocol.

This argument explains why a security proof which is perfectly fine in a standalone model might completely break down when concurrent composition is used. Sometimes, this is just an issue of the security analysis - maybe there is a clever way to avoid the rewinding explosion, or a different proof strategy that does not use rewinding at all, but sometimes, as in the case of the pathological example presented by Mikero, this failure to prove security stems in fact from the actual insecurity of the composed protocols.

$\endgroup$
  • $\begingroup$ Great answer. I couldn't understand why rewinding explosion could occur when the (corrupt) verifier has only polynomially many nested components. If you don't mind, can you please give a concrete example of rewinding explosion? For any ZK proof system, we say that the original non-UC way of proving zero knowledge fails only if every possible simulator incurs rewinding explosion right? If only some cleverly crafted simulator incurs rewinding explosion, there could still be a way of proving zero knowledge property of the system. $\endgroup$ – satya Jun 17 at 13:01
  • $\begingroup$ I'll try to when I get some time :) intuitively, the explosion will come from the fact that the security analysis only assumes an adversary that succeeds with some non-negligible probability. But in the case of correlated executions of the protocol, you would need the adversary to succeed simultaneously in all correlated instances when you rewind it, which might only happen with negligible probability. $\endgroup$ – Geoffroy Couteau Jun 19 at 18:07

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.