Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Attacks on cryptographic protocols are usually modeled by allowing an adversary to query an oracle that represents the primitive he attacks, for instance the adversary specifies a message he wants to have signed, a challenge he wants a prover to answer, or a subset of players he wants to corrupt Security is then defined by requiring that as long as the queries satisfy some constraint, there is some problem the adversary cannot solve, such as compute a certain piece of information.

Several previous works consider what happens to security of classical protocols if we allow the adversary to be quantum. The model usually considered is that the adversary is now a quantum machine, but otherwise plays exactly the same game as in a normal attack, i.e., he still communicates classically with the protocol he attacks. One example of this is the work of Watrous [Wat06], showing that a large class of zero-knowledge protocols are also zero-knowledge against a quantum verifier.

In this paper, we introduce a new model of quantum attacks on classical as well as quantum cryptographic protocols, where the adversary is allowed to ask several classical queries to the oracle in quantum superposition. In more concrete terms, we ask, for multiparty protocols: what happens if the adversary can be in superposition of having corrupted several different subsets? or, for zero-knowledge protocols: what happens if a quantum verifier can be in superposition of having issued several different challenges to the prover, and receive the responses in superposition? As we will argue below, we believe such superposition attacks to be a valid physical concern, but they also form a very natural generalization from a theory point of view: in the literature on black-box quantum computing, quantum black-box access to a function is usually defined by extending classical black-box access such that queries are allowed to contain several inputs in superposition. Our superposition attacks extend conventional attacks in the same way.

There is recent work [BDF+11, Zha12b] that considers the random oracle model and shows security of various schemes even if the adversary has quantum access to the random oracle. These result are quite different from ours in that they are concerned with allowing everything “in the adversary’s brain” to be quantum, rather than considering his communication with the rest of the world as we do. To the best of our knowledge our work is the first to consider adversaries that have quantum access to the cryptographic primitive or protocol under attackFootnote 1 but we emphasize that in independent work [BZ12, Zha12a] superposition attacks are also considered, on pseudorandom functions and message authentication codes.

At first sight, superposition attacks may seem rather exotic. However, it is not hard to see that in several scenarios, it is very natural to consider these attacks:

Consider first protocols that handle quantum data, such as in several previous works on quantum secret sharing and multiparty computation (e.g., Ben-Or et al. [BCG+05]). Such a protocol requires players to communicate quantum information and keep throughout the game a joint entangled quantum state that involves all the players. If the players can do this, we should assume that the adversary can do something of similar technological difficulty. It therefore seems fair to allow the adversary to be in superposition of having interacted with different subsets of players. Note here that “interacting with a player” does not have to be a macroscopic process: the adversary could attempt to communicate with the player in a way that is physically different from what the implementation of the protocol expected, and in this way get more information about the private state of the player than he was supposed to. For instance, the effect of sending on a different frequency or a different number of particles than expected may be hard to predict and may depend heavily on the way the protocol is implemented. Several known attacks on quantum key distribution work in this way. Now, if the communication defined by the protocol is quantum in the first place, we see no reason why such an attack cannot be performed in superposition against different players.

Second, what about classical protocols? One might think that here, superposition attacks cannot be mounted. The argument would be that since honest players are classical, they would “automatically” do a measurement of anything they receive, thus forcing a collapse of any quantum state they are given. However, this may be a dangerous assumption in the future, considering the fact that classical computing equipment becomes smaller and approaches the quantum limit. If an adversary captures such a device containing a secret key, he may be able to cool it down, for instance, and get some quantum effects to happen during communication. On top of this, even honest players may in the future use quantum computing and communication, but may sometimes need to execute a classical protocol. Having to always do this on separate classical hardware would be an unpleasant limitation.

So if we cannot be sure that hardware always behaves classically, perhaps an easy solution would be to require explicitly in the protocol that every incoming message is measured? However, such an idea seems problematic from a practical point of view: an instruction to measure an incoming message makes little sense to someone implementing the protocol on a classical machine, so we have to trust that someone else responsible for the physical implementation will put equipment in place to do the measurement. Moreover, making sure the measurement is actually done is not as straightforward as one might think: most physicists today subscribe to an interpretation of quantum mechanics where the belief is that the wave function never actually collapses even when a measurement is done. Instead, information is transferred to (a part of) the environment and this is experienced as a collapse to a party who does not have access to the environment. In our case, this means that if the adversary were to get access to this environment, then from his point of view no measurement took place. Hence, equipment that seeks to enforce that a measurement is done from the adversary’s point of view must in some sense keep information away from the adversary, and this may be non-trivial if we are dealing with microscopic equipment.

In the face of these problems, we believe the most natural and elegant solution is to ask for protocols that are secure regardless of whether any measurement is performed on incoming messages, which exactly means we need security even if the adversary has quantum access to the primitive.

Contributions of the paper. We first show that any classical secret-sharing scheme that is perfectly secure with threshold \(t\) in the standard model is perfectly secure against superposition attacks if and only if the adversary’s superposition is constrained to contain subsets of size at most \(t/2\). If this condition is not satisfied, not only does perfect security fail, we show examples where the adversary may even learn the secret with certainty. We also consider quantum secret sharing schemes and show that the same results hold for a large class of schemes derived from classical linear secret sharing, this includes essentially all known schemes.

We then consider (classical) zero-knowledge protocols and first give strong evidence that known protocols are not, in general, secure against superposition attacks. We give such an attack on the well-known graph isomorphism protocol, showing how to extract from the prover the number of fixed points of the prover’s secret permutation. A simple reduction shows that if this attack could be simulated, then there is an efficient quantum algorithm computing the isomorphism between two graphs, as long as the isomorphism is unique. Thus the protocol can only be zero-knowledge if graph isomorphism in most cases is easy on a quantum computer.

We then use our result on classical secret-sharing to construct zero-knowledge proofs for all of NP in the common reference string (CRS) model. While our protocol is classical, it is sound against a cheating unbounded quantum prover and computational zero-knowledge against a quantum verifier, even if the verifier is allowed a superposition attackFootnote 2. Since our simulation is straight-line, the protocol is also secure under concurrent composition. We stress that our construction does not make assumptions beyond what we need to protect against standard attacks, nor is it less efficient than known constructions. Therefore this construction is an affirmative answer to our question above: we can indeed have protocols that are secure, regardless of whether incoming messages are measured or not.

Finally, we consider classical multiparty computation and we define a UC-style model for static and passive superposition attacks on classical MPC protocols. Given our result on secret-sharing schemes, it is natural to speculate that classical MPC protocols that are secure against \(t\) corruptions, are secure against superposition attacks corrupting \(t/2\) players. The situation turns out to be more complicated, however: We show that for the model that gives the adversary the most power (and hence is the most hostile to the simulator), simulation based security is not possible at all. However, putting a natural constraint on the adversary, we are able to give a characterization of a class of protocols that can be shown secure, though not necessarily with efficient simulation. We show that this class contains non-trivial protocols, where by non-trivial, we mean that although the protocol is secure against a classical attack, we can show that it cannot be proved secure against a superposition attack by simply running the classical simulator in superposition. The simulator that does exist is in some sense “more quantum”.

Whether more general positive results hold in this constrained model remains an open question. Likewise, the very natural question of security of quantum multiparty computation protocols against superposition attacks remains open. Note, however, that existing work on quantum multiparty computation is typically based on quantum secret sharing, where the adversary’s choice of subset to corrupt is classical. The negative part of our result on secret sharing described above shows that such protocol are not necessarily secure against superposition attacks as they stand.

2 Preliminaries

We will model players in protocols in two different ways: when we are not interested in computational limitations on parties, a player will be specified by a series of unitary transforms where the \(i\)th transform is done on all qubits available to the party, after the \(i\)th message has been received (in the form of a quantum register), and then some designated part of the storage is sent as the next outgoing message. We are limiting ourselves to perfect unitary transformation of the party’s register because we are exactly considering the situation where an attacker manages to prevent coupling between the party and the environment.

In cases where we want to bound the computational complexity of a player, we consider players to be an infinite family of interactive quantum circuits, as in the model from [FS09], and then the complexity is the circuit size.

2.1 Running Functions in Superposition

Consider any function, \(f: X \rightarrow Y\) and a register of qubits, \(|{\psi }\rangle = \sum \limits _{x} \alpha _x|{x}\rangle |{0}\rangle \in \mathcal {H}_{X}\otimes \mathcal {H}_Y\), where \(\dim (\mathcal {H}_{X}) = |X|\) and \(\dim (\mathcal {H}_{Y}) = |Y|\). To run \(f\) on \(|{\psi }\rangle \) means to apply the unitary transformation, \(U_f\), such that \( U_f \sum \limits _{x} \alpha _x|{x}\rangle |{0}\rangle = \sum \limits _{x} \alpha _x|{x}\rangle |{f(x)}\rangle \). In general the register in \(\mathcal {H}_{Y}\), called the response register, can contain any superposition of values, not just \(0\). In this case, we have that, \( U_f \sum \limits _{{x,a}} \alpha _{x,a}|{x}\rangle |{a}\rangle = \sum \limits _{{x,a}} \alpha _{x,a}|{x}\rangle |{f(x) \oplus a}\rangle \) where \(\oplus \) is the bitwise xor.

3 Secret Sharing

In (classical) secret sharing \(n\) parties are sharing some secret value \(s\in \mathbb S\) using randomness \(r\in \mathcal {R}\), where \(\mathbb S\) and \(\mathcal {R}\) are the sets of possible secrets and randomness. We name the parties \(P_1, \ldots , P_n\). Let \([n] = \{ 1, \ldots , n \}\). Each party, \(P_i\), receives a share \(v_i(s, r) \in \{ 0,1\}^k\), also called his private view . That is, \(v_i: \mathbb {S} \times \mathcal {R} \rightarrow \{0,1 \}^k\).

For \(A\subset [n]\), let \(v_{A}(s,r) = \{ v_i(s, r) \}_{i \in A}\) be the string containing the concatenation of views for parties \(P_i\) with \(i \in A\). For convenience in the following we assume that each such string is padded, so that they have the same length regardless of the size of \(A\). That is, \(v_A: \mathbb {S} \times \mathcal {R} \rightarrow \{0,1 \}^t\). An adversary structure \(G\) is a family of subsets \(G \subset 2^{[n]}\). A secret sharing scheme is perfectly secure against classical \(G\)-attacks if for any \(A\in G\), the distribution of \(v_{A}(s,r)\) does not depend on \(s\). The adversary structure of the secret sharing scheme is the maximal \(F \subseteq 2^{[n]}\) for which the scheme is perfectly secure against \(F\) attacks. We will only consider so-called perfect secret-sharing schemes, where it holds for all \(A \not \in G\) that \(v_{A}(s,r)\) uniquely determines the secret \(s\). I.e., in a perfectly secure, perfect secret-sharing scheme a set of shares either carry no information on the secret or fully determines the secret.

We will model any passive attack on the scheme as a one-time query to an corruption oracle. The corruption oracle for a specific run of a secret sharing scheme \(O(s,r,A) = v_A(s,r)\) is the function that for a specific choice of secret, randomness and set of parties, returns the private view of those parties. That is, \(O : \mathbb S \otimes \mathcal {R} \otimes F \rightarrow \{ 0,1 \}^t\).

3.1 Two-Party Bit Sharing Example

Before we present the full model for secret sharing we start with a small example. We consider the case of 2 parties sharing a single bit, \(b\in \{ 0,1\}\), using a random bit, \(r\in \{0,1\}\). Here \([n] = \{ 1, 2\}\), \(F = \{ (1), (2)\}\), \(v_1(b,r) = b \oplus r\), \(v_2(b,r) = r\).

This scheme is of course secure against a classical attack, which we can model by giving an adversary one-time access to an oracle that will return one share (\(r\) or \(r\oplus b\)) on request. However, it is well known from the Deutch-Jozsa algorithm that given quantum access to such an oracle, one can compute the xor of the two bits from only one query. Hence the scheme is not secure against a superposition attack. In the following we consider what happens in the general case.

3.2 Model for Secret Sharing

We will now give the full technical description of the model for superposition attacks on general secret sharing. To do this we first consider the state spaces needed to run the protocol and the attack on the protocol. First is the space that contains the shares for all the parties, \(\mathcal H_{\mathsf{parties }}\). The state in the register for this space is unchanged throughout the attack and is

$$\begin{aligned} |{parties}\rangle _\mathsf{p }= \sum _{s \in \mathbb {S},r \in \mathcal {R}} \sqrt{p_s} \sqrt{p_r} |{s,r, v_{[n]}(s,r)}\rangle _\mathsf{p }= \sum _{s \in \mathbb {S},r \in \mathcal {R}} \sqrt{p_s} \sqrt{p_r} |{s,r}\rangle \bigotimes ^n_{i=1} |{v_i(s,r)}\rangle \!, \end{aligned}$$

where \(|{s,r}\rangle \) is the purification of the secret and randomness choice. This is purely for technical reasons and does not matter for the adversary as he never sees it (and hence they might as well be considered measured). Secondly is the space for the environment, \(\mathcal {H}_\mathsf{env }\), which the adversary can use to choose his query and use as potential auxiliary register. The initial state for the environment is a general (pure) state,

$$\begin{aligned} |{\psi }\rangle _\mathsf{e }= \sum _{x}\alpha _x|{x}\rangle _\mathsf{e }\in \mathcal {H}_{\mathsf{env }}\ , \end{aligned}$$

where \(x\) is in some set of arbitrary, but finite size. We will omit this for readability.

Finally is the space holding the adversary’s query to the corruption oracle, \(\mathcal {H}_{\mathsf{query }}\). This is initially a ‘blank’ state,

$$\begin{aligned} |{\omega }\rangle _\mathsf{q }= |{0,0}\rangle _\mathsf{q }\in \mathcal {H}_{\mathsf{query }}. \end{aligned}$$

The space for the entire model is hence, \(\mathcal {H}_{\mathsf{total }} = \mathcal {H}_{\mathsf{parties }} \otimes \mathcal {H}_{\mathsf{env }} \otimes \mathcal {H}_{\mathsf{query }}\), and the initial state is,

$$\begin{aligned} |{init}\rangle _\mathsf{t }= \sum _{s \in \mathbb {S},r \in \mathcal {R}} \sqrt{p_s} \sqrt{p_r}|{s,r, v_{[n]}(s,r)}\rangle _\mathsf{p }\otimes \sum _{x}\alpha _x|{x}\rangle _\mathsf{e }\otimes |{0,0}\rangle _\mathsf{q }\in \mathcal {H}_{\mathsf{total }}\ . \end{aligned}$$

The attack will be defined by two operations and an adversary structure, \(F\). First the adversary needs to construct his query for the oracle. This includes choosing the superposition of subsets he will corrupt and associated values for the response registers. This is an arbitrary unitary operation. We will denote it, \(U^{{\textsc {adv}},F}_{{\textsc {query}}}\),

$$\begin{aligned} U^{{\textsc {adv}},F}_{{\textsc {query}}} : \mathcal {H}_{\mathsf{env }} \otimes \mathcal {H}_{\mathsf{query }} \rightarrow \mathcal {H}_{\mathsf{env }} \otimes \mathcal {H}_{\mathsf{query }}\ . \end{aligned}$$

After this unitary operation the state is

$$\begin{aligned} |{query}\rangle _\mathsf{t }&= U^{{\textsc {adv}},F}_{{\textsc {query}}} |{init}\rangle _\mathsf{t }\\&= \sum _{s \in \mathbb {S},r \in \mathcal {R}} \sqrt{p_s} \sqrt{p_r}|{s,r, v_{[n]}(s,r)}\rangle _\mathsf{p }\otimes \sum _{x,A\in F,a \in \{ 0,1 \}^t}\alpha _{x,A,a}|{x}\rangle _\mathsf{e }\otimes |{A,a}\rangle _\mathsf{q }\end{aligned}$$

where we assume it is the identity on \(\mathcal {H}_{\mathsf{parties }}\). Next the oracle, \(O(s,r,A)\), is run. Let

$$ U_O: \mathcal {H}_\mathsf{parties }\otimes \mathcal {H}_\mathsf{query }\rightarrow \mathcal {H}_\mathsf{parties }\otimes \mathcal {H}_\mathsf{query }$$

denote the unitary applying this function. The state afterwards is \(U_O |{query}\rangle _\mathsf{t }\), which equals

$$\begin{aligned} \sum _{s \in \mathbb {S},r \in \mathcal {R}} \sqrt{p_s} \sqrt{p_r}|{s,r, v_{[n]}(s,r)}\rangle _\mathsf{p }\otimes \sum _{x,A\in F,a \in \{ 0,1 \}^t}\alpha _{x,A,a}|{x}\rangle _\mathsf{e }\otimes |{A,a \oplus v_A(s,r)}\rangle _\mathsf{q }\end{aligned}$$

where we assume \(U_O\) is padded with appropriate identities. Consider the final state the adversary sees for a specific secret, \(s\),

$$\begin{aligned} \rho ^{{\textsc {adv}},F}_s = \sum \limits _{r \in \mathcal {R}} p_r \left|{\psi ^{{\textsc {adv}},F}_r}{\left\rangle \!\right\langle }{\psi ^{{\textsc {adv}},F}_r}\right|\ , \end{aligned}$$

where \(|{\psi ^{{\textsc {adv}},F}_r}\rangle = \sum \limits _{{x,A\in F,a \in \{ 0,1 \}^t}}\alpha _{x,A,a}|{x}\rangle _\mathsf{e }\otimes |{A,a \oplus v_A(s,r)}\rangle _\mathsf{q }\).

Definition 1

A secret sharing scheme \(\mathcal{S}\) is perfectly secure against superposition F-attacks if, and only if, for all unitary matrices, \(U^{{\textsc {adv}},F}_{{\textsc {query}}}: \mathcal {H}_{\mathsf{env }} \otimes \mathcal {H}_{\mathsf{query }} \rightarrow \mathcal {H}_{\mathsf{env }} \otimes \mathcal {H}_{\mathsf{query }}\) and all possible pairs of inputs, \( s,s'\in \mathbb S\) it holds that \(\rho ^{{\textsc {adv}},F}_s = \rho ^{{\textsc {adv}},F}_{s'}\).

3.3 (In)security Against Superposition Attacks on Classical Secret-Sharing

For an adversary structure \(F\), we define \(F^2= \{ A\,\vert \, \exists B,C\in F: A = B\cup C \}\).

Theorem 1

Let G be the classical adversary structure for \(\mathcal{S}\). \(\mathcal{S}\) is perfectly secure against superposition F-attacks if and only if \(F^2\subseteq G\).

Proof

For the forward direction, consider the adversary’s final state,

$$\begin{aligned} \rho ^{{\textsc {adv}}}_s = \sum _{r \in \mathcal {R}} p_r\left|{\psi ^{{\textsc {adv}}}_r}{\left\rangle \!\right\langle }{\psi ^{{\textsc {adv}}}_r}\right|, \end{aligned}$$

which equals

$$\begin{aligned} \sum _{r, x, x', A, A', a, a' }p_r\alpha _{x,A,a}\alpha ^ *_{x',A',a'}|{x}\rangle _\mathsf{e }\langle {x'}|_\mathsf{e }\otimes |{A,a \oplus v_A(s,r)}\rangle _\mathsf{q }\langle {A',a' \oplus v_{A'}(s,r)}|_\mathsf{q }\ . \end{aligned}$$

Now, for any fixed \(A\), \(A'\), \(a\), \(a'\) and \(s\), consider the matrix

$$ \sum _{r \in \mathcal {R}}p_r|{A,a \oplus v_A(s, r)}\rangle _\mathsf{q }\langle {A',a' \oplus v_{A'}(s,r)}|_\mathsf{q }. $$

The crucial observation now is that this matrix is in 1-1 correspondence with the joint distribution of \(v_A(s,r)\) and \(v_{A'}(s,r)\). Namely, its entries are indexed by pairs of strings \((\alpha ,\beta )\), where \(\alpha \), \(\beta \) are strings of the same length. And furthermore the \((\alpha ,\beta )\)’th entry is the probability that the events \(v_A(s,r) = \alpha \oplus a\) and \(v_{A'}(s,r) = \beta \oplus a'\) occur simultaneously, where the probability is taken over a random \(r\). Now, if \(F^2 \subseteq G\), we have that \(\mathcal{S}\) is perfectly secure against classical \(F^2\)-attacks. Therefore the joint distribution of \(v_A(s,r)\) and \(v_{A'}(s,r)\) does not depend on \(s\), consequently each matrix

$$ \sum _{r \in \mathcal {R}}p_r|{A,a \oplus v_A(r,s)}\rangle _\mathsf{q }\langle {A',a' \oplus v_{A'}(s,r)}|_\mathsf{q }$$

is independent of \(s\) as well. Hence \(\forall s,s'\in \mathbb S: \rho ^{{\textsc {adv}},F}_s = \rho ^{{\textsc {adv}},F}_{s'}\) as required.

For the only-if part, assume for contradiction that \(F^2\not \subseteq G\), i.e., there exist \(A_0,A_1\) such that \(A_0\cup A_1 \not \in G\). It follows that a secret shared using \(\mathcal{S}\) is uniquely determined from shares in \(A_0\cup A_1\). Then consider the query \(|{\omega _{{\alpha }}}\rangle = (|{A}\rangle |{0}\rangle + |{A'}\rangle |{0}\rangle )/\sqrt{2}\). By the same computation as above, we see that \(\rho ^{{\textsc {adv}}}_{s}\) contains a submatrix of form \(\sum _{r \in \mathcal {R}}|{a_A \oplus v_{A}({s},{r})}\rangle \langle {a_{A'}\oplus v_{A'}({s},{r})}|\), that corresponds to the joint distribution of shares in \(A\) and \(A'\). But since the secret is uniquely determined from these shares, it follows that this submatrix is different for different secrets, and hence we get that there exists a measurement with non-zero bias towards the secret, and so \(\mathcal{S}\) is not perfectly secure against superposition \(F\)-attacks. This is exactly the result we saw in the small example in Sect. 3.1.\(\square \)

Alternative models for secret sharing. Here we take a closer look at how the response register in handled during a superposition attack: When the adversary runs a classical component in superposition, and sends it a message, then the reply will in general be a superposition, nevertheless the reply might be computed in different ways. In general quantum information processing, the standard assumption is that the result is xor’ed into a response register \(a\) supplied along with the input, e.g., if the component computes a function \(f\), then on input \(|{x}\rangle |{a}\rangle \), the output is \(|{x}\rangle |{a \oplus f(x)}\rangle \). This ensures that the components acts unitarily when the input is quantum. We call this the supplied response register model.

When considering the case of an adversary attacking a protocol one may be able to argue that the adversary will not have enough control to be able to decide the a priori content of the response register. It may be more reasonable to assume that the component the adversary talks to will create the response register and return it to the adversary. We model this setting of created response registers by restricting the more general setting by allowing only \(a=0\), in which case the adversary will always receive \(|{x}\rangle |{f(x)}\rangle \). Note that Theorem 1 applies in this setting as well.

3.4 Attacks on Secret Sharing

Theorem 1, tells us that we cannot have perfect security if the condition \(F^2 \subseteq G\) is violated, but nothing about how much information the adversary can actually gain on the secret in this case. Of course, if \(F \not \subseteq G\), the adversary can trivially learn the secret. But if \(F \subseteq G\) one might hope that the adversary only learns a small amount of information, and even that this could become negligible by increasing the amount of randomness used to create the shares. However, in the lemma below we show that, under a simple assumption on the secret sharing scheme, an attacker can distinguish between two possible secrets with considerable bias. The attack works even in the restricted setting of created response registers. The proof is found in the full paper [DFNS11].

Lemma 1

Let G be the classical adversary structure for \(\mathcal{S}\). If there exist two subsets, \(A_0\), \(A_1 \in G\) such that (1) \(A_0 \cup A_1 \notin G\) and (2) any secret, \(s\in \mathbb {S}\), combined with the shares in \(A_0\) (\(A_1\)) uniquely determine the choice of randomness, \(r\in \mathcal {R}\), then the following holds.

For any two secrets \(s, s'\in \mathbb {S} : s \ne s'\), there exists a query (with \(a=0\)) that will allow an adversary to distinguish between \(s\) and \(s'\) with probability \(p_{guess}\), where \(p_{guess} \ge \frac{3}{4}\).

An example of such a scheme is a Shamir secret sharing scheme that is classically secure against \(t\) corrupted players. Here any subset of \(t\) players combined with the secret will give \(t+1\) points on a polynomial of degree at most \(t\) and hence uniquely determine the choice of randomness.

4 Quantum Secret Sharing

In this section we study the security of quantum secret sharing against superposition attacks. The situation turns out to be more complicated than for the classical case, and security depends on the exact model for what the adversary is allowed to do.

The model we will use for quantum secret sharing is that a secret is a quantum state \(|{sec}\rangle = \sum _{s\in \mathbb S} \alpha _s |{s}\rangle \), i.e., some superposition over the possible classical choices of secret. The secret sharing scheme is then a unitary transform that maps each basis state \(|{s}\rangle \) plus an ancilla of appropriate size to a state

$$ |{\varPhi _s}\rangle = \sum _{v_1, \ldots , v_n\in \{ 0,1\}^k} \alpha _{v_1, \ldots ,v_n} |{v_1}\rangle \cdots |{v_n}\rangle \ , $$

where we think of the content of the \(i\)’th register as the share of the \(i\)’th player. A quantum secret sharing scheme is secure against adversary structure \(F\), if any subset of shares corresponding to a subset \(A\in F\) contains no information on the secret state, but any subset of shares \(B\) where \(B\not \in F\) allows reconstruction of the secret. It follows from the no-cloning theorem that security can only hold if \(F\) has the property that for any \(B\not \in F\), the complement \(\bar{B}\) is in \(F\).

An example of quantum secret sharing can be derived from Shamir’s secret sharing scheme. Here we assume that \(n= 2t+1\), and the adversary structure contains all subsets of size at most \(t\), and \({\mathbb S} = {\mathbb F}_p\) for the finite field \({\mathbb F}_p\). We then define \(|{\varPhi _s}\rangle = \frac{1}{\sqrt{M}} \sum _{f \in P_s} |{f(1)}\rangle \cdots |{f(n)}\rangle ,\) where \(P_s\) is the set of polynomials of degree at most \(t\) with \(f(0)=s\), and \(M\) the number of such polynomials.

There are several ways to define what it means that an adversary gets access to some of the shares. The simplest form of attack we consider is called a share capture attack, where the adversary essentially steals a subset of the shares (or subsets of shares in superposition). Since it seems natural to assume that some evidence of the absence of shares would be left after this, we assume that the players whose shares are captured are left with erasure symbols \(\bot \) instead of shares. Some notation to describe this more formally: we will let \(\mathbf{v}= v_1,\ldots ,v_n\) in the following, and \(|{\mathbf{v}_A}\rangle \) will stand for the basis state \(|{\mathbf{v}_A}\rangle = |{w_1}\rangle \cdots |{w_n}\rangle \), where \(w_i= v_i\) if \(i\in A\) and \(w_i= \bot \) otherwise. Likewise, for the Shamir based example, we let \(|{f(A)}\rangle = |{u_1}\rangle \cdots |{u_n}\rangle \) where \(u_i= f(i)\) if \(i\in A\) and \(u_i=\bot \) otherwise.

In an \(F\)-share capture attack, a query \(\sum _{A\in F} \alpha _A|{A}\rangle |{\bot }\rangle \cdots |{\bot }\rangle \) is prepared, where the last part of the register will contain the captured shares. Then a unitary transform \(U\) is executed on the shares and the adversary’s query. \(U\) is specified by the following action on basis states for shares and player subsets:

$$ U(|{v_1}\rangle \cdots |{v_n}\rangle |{A}\rangle |{\bot }\rangle \cdots |{\bot }\rangle ) = |{\mathbf{v}_{\bar{A}}}\rangle |{A}\rangle |{\mathbf{v}_A}\rangle \ . $$

We define \(U\) to act as the identity on all basis vectors not involved in the above expression. This clearly makes \(U\) be unitary. In the actual attack,

$$ U(|{\varPhi _s}\rangle \sum _{A\in F} \alpha _A|{A}\rangle |{\bot }\rangle \cdots |{\bot }\rangle ) $$

is computed and the adversary is given the last two registers, containing the corrupted set(s) and the captured shares. We say that the scheme is secure against \(F\)-share capture attacks if it always holds that the state the adversary gets is independent of \(|{s}\rangle \). By linearity, security trivially extends to superpositions over different \(|{s}\rangle \)’s.

Proposition 1

Any quantum secret sharing scheme that is secure for adversary structure \(F\) is also secure against \(F\)-share capture attacks.

The proof is straightforward and is found in the full paper [DFNS11].

A more interesting result emerges if we allow the adversary slightly more power. We will consider what we call a capture-and-replace attack. Here, the adversary prepares a query as before and \(U\) is executed. Now, the adversary does some local computation. For convenience and without loss of generality for our result, we assume that a unitary transform \(V\) is applied by the adversary to the shares captured \(|{{\mathbf {v}}_{A}}\rangle _{\mathsf{a }}\) (where \(\mathsf{a }\) denotes the registers held by the corrupted players) together with an ancilla in state \(|{0}\rangle _{\mathsf{z }}\): \(V|{{\mathbf {v}}_A}\rangle _{\mathsf{a }}|{0}\rangle _{\mathsf{z }} = |{\phi _A}\rangle _{\mathsf{a }\mathsf{z }}\). Finally, the adversary keeps register \(Z\) before \(U\) is executed again on the remaining registers. Note that \(U=U^{\dagger }\), so the second transformation puts the shares back in place. It seems hard to argue that the adversary would be limited to only one application of \(U\), so there is good motivations to consider this attack. We talk about F-capture-and-replace attacks in the same way as above. It is easy to see that capture attacks are a special case of capture-and-replace attacks. In this more general case however, it turns out that superposition attacks help the adversary, and for the Shamir based scheme, we get a result similar to what we have for classical secret sharing.

Theorem 2

Let \(G\) be the adversary structure containing sets of at most \(t\), for which the Shamir based quantum secret sharing scheme is perfectly secure. Then, the scheme is perfectly secure against \(F\)-capture-and-replace attacks in superposition if and only if \(F^2 \subseteq G\).

The proof is similar to the proof of Theorem 1 and can be found in the full paper [DFNS11]. The theorem generalizes easily to any quantum secret sharing scheme derived from a classical linear scheme. We conjecture it generalizes to any quantum scheme. However, the only other quantum schemes we are aware of are schemes that use quantum shares for classical data. For instance, the 4 Bell-states can be used to share 2 classical bits among two players who receive only one qubit each. This scheme can also be broken under a superposition attack.

5 Zero-Knowledge

5.1 An Attack Against the Graph Isomorphism Protocol

Consider the well-known protocol for proving graph isomorphism: The common input is two graphs \((G_0, G_1)\) on \(n\) nodes, where the prover \(P\) knows a permutation \(\pi \) such that \(\pi (G_0) = G_1\). \(P\) will send to the verifier \(V\) a graph \(H= \sigma (G_0)\) where \(\sigma \) is a random permutation on \(n\) nodes. \(V\) sends a random bit \(b\), and \(P\) returns the permutation \(\rho = \pi ^b \sigma ^{-1}\). Finally \(V\) checks that \(\rho (H)= G_b\).

This protocol is perfect zero-knowledge against a classical as well as a quantum verifier, but in the quantum case the proof assumes that the verifier is limited to sending a classical bit \(b\) as challenge to the prover (see [Wat06] for a precise definition of zero-knowledge when the verifier is quantum). We consider what happens if a superposition attack is allowed, and we give a concrete attack that allows to extract non-trivial information from the prover. We will only consider input graphs for which the permutation \(\pi \) is uniquely defined from \(G_0, G_1\). This is mostly for simplicity, but note also that it is well-known that deciding whether the permutation is unique is equivalent to deciding graph isomorphism in the general case. Hence, assuming the latter is hard, algorithms trying to compute an isomorphism between \(G_0\) and \(G_1\) are unlikely to have an easier time when the permutation is unique.

To analyze what happens, we need to assume a concrete way in which \(P\) communicates his permutation to \(V\) in the final message. We will assume a natural method, namely to send \(\rho \), \(P\) sends \(\rho (0),\ldots ,\rho (n-1)\) in the classical case. We generalize this to the quantum case in the standard way: \(V\) supplies a register \(|{b}\rangle |{{i_{0}}}\rangle _0\cdots |{i_{n-1}}\rangle _{n-1}\) and \(|{b}\rangle |{i_0 + \rho _b(0) \,{\small {\mathrm{mod}}}\,n}\rangle _0 \cdots |{i_{n-1}+\rho _b(n-1) \,{\small {\mathrm{mod}}}\,n}\rangle _{n-1}\), in returned, where \(\rho _b\) is the correct answer to \(b\). By adding the answer into the response register, we ensure that the operation of \(P\) is unitary.

The proof of the theorem below works by first constructing a concrete attack that the verifier might execute and concluding that this attack would allow to decide if the prover’s secret permutation has a fixed point or not. Then, if a simulator existed for such a verifier, a simple reductionFootnote 3 allows us to get the full isomorphism between the graphs in all cases where the permutation in question is unique:

Theorem 3

If the graph isomorphism protocol is zero-knowledge against superposition attacks, then graph isomorphism can be computed efficiently by a quantum algorithm for all inputs where the permutation in question is uniquely defined by the input graphs.

Proof

We describe the attack a verifier might execute. We first specify the state we will send to \(P\):

$$ \frac{1}{\sqrt{2}}\ (|{0}\rangle +|{1}\rangle ) \ F_n(|{1+r\,{\small {\mathrm{mod}}}\,n}\rangle _0)\ F_n(|{1}\rangle _1) \cdots F_n(|{1}\rangle _{n-1})\ , $$

where \(F_n\) is the quantum Fourier transform over \(\mathbb {Z}_n\) and \(r\) is a random non-zero value in \(\mathbb {Z}_n\). The state can also be written as

$$\begin{aligned} \frac{1}{\sqrt{2}}\ (&|{0}\rangle F_n(|{1+r\,{\small {\mathrm{mod}}}\,n}\rangle _0)\ F_n(|{1}\rangle _1) \cdots F_n(|{1}\rangle _{n-1})\ + \\&|{1}\rangle F_n(|{1+r\,{\small {\mathrm{mod}}}\,n}\rangle _0)\ F_n(|{1}\rangle _1) \cdots F_n(|{1}\rangle _{n-1}))\ . \end{aligned}$$

To see what happens to this state under the operation done by \(P\), consider the \(k\)’th register of those where \(F_n\) is applied, in the summand corresponding to challenge bit \(b\). Before \(P\)’s operation, it is in state

$$ F_n(|{i_k}\rangle _k) = \sum _{j=0}^{n-1} \omega _n^{i_kj}|{j}\rangle _k\ , $$

where \(\omega _n\) is the principal \(n\)’th root of unity and \(i_0= 1+r\,{\small {\mathrm{mod}}}\,n\) and \(i_k=1\) otherwise. After the operation, we have the new state

$$\begin{aligned} \sum _{j=0}^{n-1} \omega _n^{i_kj}|{j+\rho _b(k)}\rangle _k&= \sum _{j'=0}^{n-1}\omega _n^{i_k(j'-\rho _b(k))}|{j'}\rangle _k \\&= \omega _n^{-i_k\rho _b(k)}\sum _{j'=0}^{n-1}\omega _n^{i_kj'}|{j'}\rangle _k = \omega _n^{-i_k\rho _b(k)} F_n(|{i_k}\rangle _k)\ , \end{aligned}$$

by a simple substitution of variables. Plugging this into the above overall state, we get that the state \(P\) returns can be written as

$$\begin{aligned} \frac{1}{\sqrt{2}}&\cdot \; (|{0}\rangle \ \omega _n^{-(1+r)\rho _0(0)} F_n(|{1+r\,{\small {\mathrm{mod}}}\,n}\rangle ) \omega _n^{-\rho _0(1)} F_n(|{1}\rangle ) \cdots \omega _n^{-\rho _0(n-1)} F_n(|{1}\rangle )\\&+ |{1}\rangle \ \omega _n^{-(1+r)\rho _1(0)} F_n(|{1+r\,{\small {\mathrm{mod}}}\,n}\rangle ) \omega _n^{-\rho _1(1)} F_n(|{1}\rangle ) \cdots \omega _n^{-\rho _1(n-1)} F_n(|{1}\rangle ))\ . \end{aligned}$$

Collecting some terms, we get

$$\begin{aligned} \frac{1}{\sqrt{2}}&\cdot \;(|{0}\rangle \ \omega _n^{-r\rho _0(0) - \sum _k \rho _0(k)} F_n(|{1+r\,{\small {\mathrm{mod}}}\,n}\rangle ) F_n(|{1}\rangle ) \cdots F_n(|{1}\rangle )\\&\quad + |{1}\rangle \ \omega _n^{-r\rho _1(0) - \sum _k\rho _1(k)} F_n(|{1+r\,{\small {\mathrm{mod}}}\,n}\rangle ) F_n(|{1}\rangle ) \cdots F_n(|{1}\rangle ))\ . \end{aligned}$$

Note that since \(\rho _0, \rho _1\) are permutations, we have

$$ \sum _k \rho _0(k)=\sum _k \rho _1(k) = n(n-1)/2. $$

Using this and the fact that \(\rho _0 = \sigma ^{-1}, \rho _1= \pi \sigma ^{-1}\), we get that our state is of form

$$\begin{aligned} \frac{1}{\sqrt{2}} \omega _n^{- n(n-1)/2 - r\sigma ^{-1}(0)} (|{0}\rangle + \omega _n^{r(\sigma ^{-1}(0)-\pi (\sigma ^{-1}(0)))}|{1}\rangle )\otimes \\ \quad \quad \quad \quad \quad F_n(|{1+r\,{\small {\mathrm{mod}}}\,n}\rangle ) F_n(|{1}\rangle ) \cdots F_n(|{1}\rangle )\ . \end{aligned}$$

In the final step, we measure the first bit of the state in the basis

$$ (|{0}\rangle +|{1}\rangle )/\sqrt{2}, (|{0}\rangle -|{1}\rangle )/\sqrt{2}. $$

Call the measurement results \(0\) respectively \(1\).

Let us consider the distribution we can expect of the measurement result: \(\sigma ^{-1}(0)\) is uniform in \(\mathbb {Z}_n\). Furthermore, it is clear that \(r(\sigma ^{-1}(0)-\pi (\sigma ^{-1}(0)))\) is 0 if \(\sigma ^{-1}(0)\) is a fixed point of \(\pi \) and uniform in \(\mathbb {Z}_n^*\) otherwise. It follows that the distribution of the final measurement result depends only on the number of fixed points of \(P\)’s secret \(\pi \).

Furthermore, if \(\sigma ^{-1}(0)\) is a fixed point of \(\pi \), we will measure \(0\) with probability \(1\), if not, we get result \(1\) with non-negligible probability. It follows by a Chernoff bound that in a polynomial number of queries we can decide except with negligible error probability whether \(\pi \) has a fixed point or not. In fact, it is not hard to see that the distribution of the measurement result for different numbers of fixed points have non-negligible statistical distance, so in a polynomial number of queries one can even get a reliable estimate of the number of fixed points of \(\pi \).

Now, if the protocol was zero-knowledge in our model, a simulator would exist that on input any two isomorphic graphs would create a state indistinguishable from the state our attack creates with the help of the prover. Thus, running the simulator a sufficient number of times followed by the measurements described above, we get an oracle that tells us whether the permutation that takes one graph to the other has a fixed point.

Using such an oracle, we can compute the permutation: let \(G'= \theta (G_1)\) for a random permutation \(\theta \) and ask the oracle if the permutation mapping \(G_0\) to \(G'\) has a fixed point. If the answer is no, we know that, e.g., \(\theta (\pi (0)) \ne 0\) or equivalently \(\pi (0) \ne \theta ^{-1}(0)\). Since we know \(\theta \), we can exclude one possibility for \(\pi (0)\). Repeating this, we eventually find \(\pi (0)\) and can compute other values of \(\pi \) in the same way. This terminates in polynomial time since a random permutation has no fixed points with constant probability (about \(1/e\)), and if this happens, the value we can exclude is uniform among the potential values. \(\square \)

5.2 A Superposition-Secure Zero-Knowledge Protocol

In this section, we present a zero-knowledge proof for any NP problem in the common reference string model. The proof is sound for an unbounded prover (quantum or not) and is computationally zero-knowledge for a polynomially bounded quantum verifier, even if superposition attacks are allowed.

For the protocol, we need a commitment scheme with special properties: we require a keyed commitment scheme \(\mathtt{Commit}_\mathtt{pk}\), where the corresponding public key \(\mathtt{pk}\) is generated by one of two possible key-generation algorithms: \(\mathcal{G}_\mathtt{H}\) or \(\mathcal{G}_\mathtt{B}\). For a key \(\mathtt{pkH}\) generated by \(\mathcal{G}_\mathtt{H}\), the commitment scheme \(\mathtt{Commit}_\mathtt{pkH}\) is perfectly hiding, whereas the other generator, \(\mathcal{G}_\mathtt{B}\), produces a key \(\mathtt{pkB}\), such that \(\mathtt{Commit}_\mathtt{pkB}\) is unconditionally binding. Furthermore, we require that keys \(\mathtt{pkH}\) and \(\mathtt{pkB}\) produced by the two generators are computationally indistinguishable, for any family of polynomial size quantum circuits. We call such a commitment scheme a dual-mode commitment scheme. As a candidate for implementing such a system, we can use a construction proposed in [DFS04]. That construction can be based on any decision problem for which there is a perfect honest-verifier zero-knowledge \(\varSigma \)-protocol, and where it is hard (for a quantum adversary) to distinguish yes-instances from no-instances. A plausible candidate for such a problem is the code equivalence problem (see [DFS04] for more details)Footnote 4.

5.3 The Model

We now describe the framework for our protocol: the proof system is specified w.r.t. a language \(L\), and we have a prover \(P\) and a verifier \(V\), both are assumed classical (when playing honestly). They get as input a common reference string \(CRS\) chosen with a prescribed distribution \(\sigma \) and a string \(x\). \(P\) and \(V\) interact and at the end \(V\) outputs \(accept\) or \(reject\). The first two properties we require are standard: Completeness: if \(x\in L\) and \(P,V\) follow the protocol, \(V\) outputs \(accept\) with probability 1. Soundness: if \(x\not \in L\) (but \(CRS\) is chosen according to \(\sigma \)) then for any prover \(P^*\), \(V\) outputs \(accept\) with probability negligible (in the length of \(x\)) when interacting with \(P^*\) on input \(x\) and \(CRS\).

For zero-knowledge, we extend the capabilities of a cheating verifier \(V^*\) so it may do a superposition attack. For simplicity, we give our definition of superposition zero-knowledge only for 3-move public-coin protocols, i.e., conversations are assumed to have the form \((a,e,z)\), where \(e\) is a random challenge issued by the verifier. It is not hard to extend the definition but the notation becomes more cumbersome. First, \(V^*\) is assumed to be a quantum machine, and the protocol is executed as follows: \(V^*\) receives \(x, CRS\) and \(P\)’s first message \(a\). Now, instead of sending a classical challenge \(e\), \(V^*\) is allowed to send a query \(\sum _{e,y}\alpha _{e,y} |{e}\rangle |{y}\rangle \). We assume the prover will process the query following his normal algorithm in superposition, so the verifier will get the same two registers back, in state \(\sum _{e,y}\alpha _{e,y} |{e}\rangle |{y+z(x,e,\rho )}\rangle \), where \(z(x,e,\rho )\) is \(P\)’s response to challenge \(e\) on input \(x\) and internal randomness \(\rho \). Finally, \(V^*\) outputs 0 or 1. Let \(p_{real}(x)\) be the probability that 1 is output. We say that the proof system is superposition zero-knowledge if there exists a polynomial time quantum machine, the simulator \(S\), such that the following holds for any cheating verifier \(V^*\) and \(x\in L\): \(S\) interacts with \(V^*\) on input \(x\), and we let \(p_{\textsc {sim}}(x)\) be the probability that \(V^*\) outputs 1. Then \(|p_{real}(x)- p_{\textsc {sim}}(x)|\) is negligible (in the length of \(x\)).

Note that, as usual in the CRS model, \(S\) only gets \(x\) as input and may therefore generate the reference string itself.

5.4 The Protocol

We now describe the basic ideas behind our protocol: we will let the CRS contain the following: \(\mathtt{pkB}, c= \mathtt{Commit}_{\mathtt{pkB}}(0), \mathtt{pkB}'\), where the public keys are both generated by \(\mathcal{G}_\mathtt{B}\). Then, using a standard trick, we will let \(P\) show that either \(x\in L\) or \(c\) contains a \(1\). Since of course the latter statement is false, \(P\) still needs to convince us that \(x\in L\). The simulator, on the other hand, can construct a reference string where \(c\) does contain 1 and simulate by following the protocol. The CRS will look the same to the verifier so we just need that the change of witness used is not visible in the proof, i.e., the proof should be so-called witness indistinguishable. In this way, we can simulate without rewinding, and this allows \(V^*\) to be quantum.

However, standard techniques for witness indistinguishability are not sufficient to handle a superposition attack. For this, we need to be more specific about the protocol: a first attempt (which does not give us soundness) is that \(P\) will secret-share his witness \(w\) (where for the honest prover, \(w\) will be a witness for \(x\in L\)), to create shares \(s_1,\ldots ,s_n\) where we assume the scheme has \(t\)-privacy. Then \(P\)’s first message is a set of commitments \(a= (\mathtt{Commit}_{\mathtt{pkB}'}(s_1, r_1),\ldots , \mathtt{Commit}_{\mathtt{pkB}'}(s_n, r_n))\). The verifier’s challenge \(e\) will point out a random subset of the commitments, of size \(t/2\), and the prover opens the commitments requested. Intuitively, this is zero-knowledge by Theorem 1: since we limit the number of shares the verifier can ask for to half the threshold of the secret sharing scheme, the state \(V^*\) gets back contains no information on the secret \(w\).

On the other hand, this protocol is of course not sound, the verifier cannot check that the prover commits to meaningful shares of anything. To solve this, we make use of the “MPC in the head” technique from [IKOS09]: Here, we make use of an \(n\)-party protocol in which the witness \(w\) is secret-shared among the players, and a multiparty computation is done to check whether \(w\) is correct with respect to the claim on the public input, namely in our case \(x\in L\) or the \(c\) from the \(CRS\) contains 1. Finally all players output \(accept\) or \(reject\) accordingly. It is assumed that the protocol is secure against active corruption of \(t\) players where \(t\) is \(\varTheta (n)\). We will call this protocol \(\pi _{L,CRS}\) in the following. Several examples of suitable protocols can be found in [IKOS09]. In their construction, the prover emulates an execution of \(\pi \) in his head, and we let \(v_{\pi _{L,CRS}}(i,\rho )\) denote the view of virtual player \(i\), where \(\rho \) is the randomness used. The prover then commits to \(v_{\pi _{L,CRS}}(i,\rho )\), for \(i=1,\ldots ,n\) and the verifier asks the prover to open \(t\) randomly chosen views that are checked for consistency and adherence to \(\pi _{L,CRS}\). It is shown in [IKOS09] that if no valid witness exists for the public input, then the verifier will detect an error with overwhelming probability.

Now, observe that the process of emulating \(\pi \) can be thought of as a secret sharing scheme, where the prover’s witness \(w\) is shared and each \(v_{\pi }(i,\rho )\) is a share: indeed any \(t\) shares contain no information on \(w\) by \(t\)-privacy of the protocol. Therefore combining this with our rudimentary idea from before gives us the solution.

Superposition-Secure Zero-Knowledge Proof for any \({\varvec{NP}}\) -Language \(L\).

The public input is \(x\), of length \(k\) bits. The distribution \(\sigma \) generates the common reference string as \(\mathtt{pkB}, c= \mathtt{Commit}_{\mathtt{pkB}}(0), \mathtt{pkB}'\), where the public keys are both generated by \(\mathcal{G}_\mathtt{B}\) on input \(1^k\).

  1. 1.

    The prover \(P\) emulates \(\pi _{L,CRS}\) to generate \(v_{\pi _{L,CRS}}(i,\rho )\) and sends to the verifier \(V\): \(\mathtt{Commit}_{\mathtt{pkB}'}(v_{\pi _{L,CRS}}(i,\rho ), r_i)\), for \(i=1,\ldots ,n\).

  2. 2.

    \(V\) sends a challenge \(e\) designating a random subset of the commitments of size \(t/2\).

  3. 3.

    \(P\) opens the commitments designated by \(e\), \(V\) checks the opened views according to the algorithm described in [IKOS09], and accepts or rejects according to the result.

Theorem 4

If \((\mathcal{G}_\mathtt{B}, \mathcal{G}_\mathtt{H}, \mathtt{Commit})\) form a secure dual-mode commitment scheme, then the above protocol is complete, sound and superposition zero-knowledge.

Proof

Completeness is trivial by inspection of the protocol. Soundness follows immediately from the soundness proof in [IKOS09], we just have to observe that the fact that the prover opens \(t/2\) and not \(t\) views makes no difference, in fact the proof holds as long as \(\varTheta (n)\) views are opened. For zero-knowledge, we describe a simulator \(S\): It will generate a common reference string as \(\mathtt{pkH}, c= \mathtt{Commit}_{\mathtt{pkH}}(1), \mathtt{pkH}'\) where both public keys are generated by \(\mathcal{G}_\mathtt{H}\) on inout \(1^k\). It then plays the protocol with \(V^*\), answering its quantum queries by following the protocol. This is possible since \(c\) now contains a 1, so \(S\) knows a valid witness. To show that \(V^*\) cannot distinguish the simulation from the protocol, we define series of games

Game 0 :

The protocol as described above, but where \(P\) talks to \(V^*\) doing a superposition attack.

Game 1 :

As Game 0, but the CRS is generated as \(\mathtt{pkH}, c= \mathtt{Commit}_{\mathtt{pkH}}(0), \mathtt{pkH}'\), where both public keys are generated by \(\mathcal{G}_\mathtt{H}\).

Game 2 :

As Game 1, but the CRS is generated as \(\mathtt{pkH}, c= \mathtt{Commit}_{\mathtt{pkH}}(1), \mathtt{pkH}'\).

Game 3 :

As Game 2, but \(P\) uses as witness the fact that \(c\) contains a 1.

Now, Game 0 and Game 1 are computationally indistinguishable by assumption on the dual-mode commitment scheme. Game 1 and Game 2 are perfectly indistinguishable by the fact that commitments done using \(\mathtt{pkH}\) are perfectly hiding. Game 2 and Game 3 are perfectly indistinguishable by Theorem 1 and the fact that commitments done using \(\mathtt{pkH}'\) are perfectly hiding. More concretely, note that if you take a secret-sharing scheme meeting the conditions of Theorem 1 and you augment each share with a commitment, under a perfectly hiding commitment scheme, to all the other shares, then you obtain a secret-sharing scheme that still meets the conditions of Theorem 1 Then you note that the protocol can be seen as using such an augmented secret-sharing scheme where the prover’s witness is the secret, so we can apply Theorem 1 to conclude that Games 2 and 3 cannot be distinguished. Finally, note that Game 3 is exactly the same game as the simulation.\(\square \)

6 Multiparty Computation

We give a short summary of our results on multiparty computation. The details can be found in the full paper [DFNS11]. To consider the security of multiparty computation under superposition attacks we define a UC-style model that captures security under static and passive attacks. We use a notion where the environment chooses inputs to and gets outputs from the parties, and also attacks the protocol, i.e., he may issue a query \(|{q}\rangle \) where he asks to corrupt a subset of players, possibly several in superposition. In the real process, he gets directly \(|{q}\rangle \) back where the views of the corrupted players have been added in, including their inputs and outputs, their randomness and all messages sent and received. In the ideal process, the query goes to a simulator, who sends it to an ideal functionality. The functionality only adds in the inputs and outputs of corrupt players and the simulator must patch in views that match. Finally the environment gets the patched view back, and we now demand that its final states in the real and the ideal process are indistinguishable. Again we can make a distinction between created response registers, where the views are returned in newly created registers, and supplied response registers, where the environment provides the registers in which the (patched) views should be returned. This gives rise to two distinct MPC models, which we call the CRR model and the SRR model below.

Our first result is that in the SRR model, one can construct settings where simulation seems to be impossible for purely technical reasons. Consider the dummy \(4\)-party function \(d(x_1, x_2, x_3, x_4) = (\lambda , \lambda , \lambda , \lambda )\), where \(\lambda \) is the empty string, i.e., the function which gives no outputs on any of its inputs. Consider protocol \(\delta \), where parties \(P_2, P_3, P_4\) runs as follows: On input \(x_i\), output \(\lambda \) and terminate, and where \(P_1\) runs as follows: On input \(x_1\), create a random secret sharing \((s_1, \ldots , s_4)\) of \(x_1\), send \(s_i\) to \(P_i\) and then output \(\lambda \) and terminate. If we pick a secret sharing scheme which classically tolerates \(2\) corrupted parties, then the secret sharing scheme is secure against corruption of \(1\) party under superposition attacks. We would therefore expect the protocol \(\delta \) to be a secure implementation of \(d\) against corruption of \(1\) party under superposition attacks. It turns out that \(\delta \) is not a secure implementation of \(d\) against \(1\) corruption in the SRR model. The reason is that the environment can put the supplied register in a uniform superposition over all values. Then when the inputs and outputs are added to the register by the ideal functionality it will have the same state regardless of \(x_1\). So the simulator gets no information on \(x_1\) when \(P_1\) is corrupted and hence cannot simulate the shares that \(P_1\) sends. The simulator could try to process the supplied register to get rid of the problem, but for every simulator there exists an environment that can anticipate what the simulator will do and can invert its operation. The details are in the full paper [DFNS11].

We then show that in the CRR model, \(\delta \) is indeed a secure evaluation of \(d\) against corruption of \(1\) player, as we would expect; The details are in the full paper [DFNS11]. Together, these results suggest that the “correct” model is the CRR model.

We then proceed to investigate general feasibility of secure function evaluation against superposition attacks in the CRR model. This problem, however, turns out to be far from trivial. As an example of this, suppose the protocol in question is classically secure against corruptions of sets of size \(t\). Now, since the protocol is a classical process that in our model is run in superposition over the inputs, one could expect that we could get a simulator for a superposition attack with \(t/2\) corruptions by running the classical simulator in superposition. This turns out to be false. Specifically, we show that even though the above protocol \(\delta \) is a classical secure implementation of \(d\) against \(t=2\) corruptions, it cannot be proven superposition attack secure against \(t/2=1\) corruptions using a simulator which consists of running a classical simulator in superposition. The problem seems to come from the fact that in the MPC model, also the dealer, \(P_1\), may be corruptedFootnote 5, which can be used to force the way to simulate the shares of different corrupt subsets to be inter-consistent, which in turn is the same as being able to simultaneously simulate a corruption of all other players than the dealer. But this is impossible, as they have three shares, which is sufficient to determine \(x_1\). The details are in the full paper [DFNS11].

Not all hope is lost, however. The fact that simple classical simulation in superposition is insufficient to prove superposition attack security does not rule out simulators which are “more quantum” than this. And, indeed, we can show that a large class of protocols can in fact be proven superposition attack secure, although the simulator may not always be efficient. For deterministic functions \(f\) we give, in classical terms, a complete characterization of the class of classical MPC protocols which securely evaluate \(f\) under superposition attack.

The characterization goes as follows. Let \(f\) be a deterministic function, let \(\pi \) be a protocol, let \(A \subseteq \{1, \ldots , n\}\) denote a subset of corrupted parties, let \(s = (s_1, \ldots , s_n)\) denote a vector of inputs for \(\pi \) and let \(\mathbb S\) denote the set of possible input vectors. For two input vectors \(s\) and \(s'\) let \(F_{s,s'} = \{ A \in F | s_A = s'_A \wedge f_A(s) = f_A(s')\}\) be the subset of allowed corruptions where the corrupted parties have the same inputs and outputs in \(f\). Finally, let \(r = (r_1, \ldots , r_n)\) denote a vector of random inputs for \(\pi \) and let \(\mathcal R\) denote the space of such vectors. Then it holds that the protocol \(\pi \) is a perfectly secure evaluation of \(f\) against superposition \(F\)-attacks in the CRR model iff it is correct and there exist a family of permutations, \(\{\pi _{s,s',A}: \mathcal R \rightarrow \mathcal R \}_{s,s' \in \mathbb S,A\in F_{s,s'}}\) with the following two properties,

  1. 1.

    \(\forall s,s' \in \mathbb S, \forall A\in F_{s,s'}, \forall r \in \mathcal {R} : |{v_{A}(s,\pi _{s,s', A}(r))}\rangle = |{v_{A}(s',\pi _{s',s, A}(r))}\rangle \).

  2. 2.

    \(\forall s,s',s'' \in \mathbb S, \forall A\in F_{s,s'}, A' \in F_{s,s''}:\)

    \(\quad \sum \limits _{{r\in \mathcal {R}}} |{v_{A}(s,r)}\rangle \langle {v_{A'}(s,r)}| = \sum \limits _{{r \in \mathcal {R}}} |{v_{A}(s,\pi _{s,s', A}(r))}\rangle \langle {v_{A'}(s,\pi _{s,s'', A'}(r))}|\).

(The proof is in the full paper [DFNS11]) Note that property (1) is exactly the statement that a (not necessarily efficient) simulator exists in the classical model.