Relativistic Zero-Knowledge — Part 2
This is part two of Relativistic Zero-Knowledge Proofs. Part one explained the basics of Zero-Knowledge, what it means for a property to be perfect or computationally bounded and how commitments are used to get either perfect zero-knowledge or perfect soundness. Here, I will present the results obtained by Claude Crépeau and his team; the first zero-knowledge protocol that both attains perfect zero-knowledge and is sound. In order to achieve this, we need to use a commitment that is binding and perfectly concealing. As we have seen, this is not possible for the protocols we have considered, but Claude managed to do it in a multi-prover environment.
Multi-Prover Interactive Protocol
In 1988, Ben-Or, Goldwasser, Kilian and Wigderson designed an interactive protocol with several provers (BRW88). In this protocol, the provers can exchange data before the start. In particular, they can exchange a large random string. However, when the protocol starts, the provers can communicate only with the verifier.
Besides the theoretical aspects of multi-prover protocols, one practical application has been proposed: an ATM with two card readers that cannot communicate with each other. It seems some researchers from MIT have presented this to banks, but so far without success. Fortunately, perhaps, or we would all need to carry twice as many credit cards!
Formally, the assumption of provers that cannot communicate is called locality. In the case of two provers, each party receives an input and returns an output from a deterministic computation, ignoring any other party. However, we allow parties to share a random string that they can use in their computation, which makes it a probabilistic computation.
It turns out that the requirement to have provers that cannot communicate is quite strong and, in practice, is almost impossible to enforce nowadays. Furthermore, quantum mechanics allows interactions without any communication between parties that classical physics cannot explain, as demonstrated by John Bell in 1964. This is called entanglement, and this property has been used by Claude Crépeau to invent quantum teleportation.
So if we model a multi-prover interactive protocol, it should at least be consistent with the laws of physics!
Non-locality
We consider now a 2-prover setting where provers cannot communicate classically. In practice, it is enforced by having the provers in separate locations and uses the speed of light as a lower bound regarding classical communication. The verifier will use two agents, one next to each prover, so they can communicate much faster with the provers that between themselves. We also allow the provers to use quantum communication (entanglement).
In order to properly model this setting, we provide the provers with a correlator:
A correlator is a way to allows the two parties to interact in a very controlled way. For instance, we can model the locality of BRW88 if we take the identity correlator, and we can model a full communication channel by taking the signalling correlator:
Between these two extreme cases, there is a whole world. As we have seen, locality assumptions are too restrictive, but full communication between provers is too permissive. If they can communicate as much as they want, it is the same as having only one prover, and we know this cannot work.
So let’s consider the right-signalling and left-signalling correlators:
Because doing right-signalling does not help you to do left-signalling, they define two different classes, and their union is different from the signalling class, which requires two-way communication.
The intersection of right and left distributions is called no-signalling. It is the set of all correlators that cannot be used as a communication channel.
It turns out that non-signalling can be modelised by the class of PR correlators:
PR correlators somehow randomize the outputs x and y; if you see them separately, you cannot learn anything about the other input. However, they have a strong relationship; the XOR of the outputs is the AND of the inputs.
Within the non-signalling class, we can define the |LOC> and COMOP class. We will only consider the |LOC> class, which represents what quantum physics can do.
The quantum magic square is an example belonging to the |LOC> class. It is a 3x3 binary grid (with values of only 0 or 1), where the sum of each line is even and the sum of each column is odd. Inputs are the indexes of a line and a column; one party answers with the content of the line and the other with the content of the column. The verifier should check that the sum of the line is even, the column sum is odd and the common cell (line and column intersect at one cell) has the same value.
The quantum magic cell can be achieved using quantum entanglement. Obviously, any local strategy will fail because the sums of all lines must be equal to the sum of all columns, and it cannot be odd and even at the same time.
Our goal is to be sound against entangled provers that are in the |LOC> class. The protocol will not have security against all no-signalling provers.
The Oblivious Protocol
In 2004, Richard Cleve, Benjamin Toner, Peter HØyer and John Watrous made a very simple protocol:
- The verifier asks one prover for the colour of a node,
- The verifier asks the other prover for the colour of another node.
To ensure that provers do not cheat by answering a different colour every time, the verifier does not always ask for nodes that form an edge but also sometimes asks for the same node. As before, by randomizing the colours, this protocol can be made Zero-Knowledge. However, this protocol supposes an honest verifier because if the verifier asks for nodes that are not part of an edge, he can mark them when they have the same colour and, at the end, come up with three sets of nodes of the same colour.
The final protocol, found recently by Claude Crépeau and his team, is using simple bit commitments modulo 3. The prover does the commitment w of a bit b using challenge c from the verifier and random r for hiding:
w = r.c+b
In order to reveal a commitment, normally the verifier asks the other prover for r. Since the other prover does not know c, he cannot cheat and reveal another b’. But rather than revealing by asking the other prover, Claude’s protocol uses a very nice property of this commitment:
Unveil via commit principle
- If you ask for the same node and same c, you should get the same value
- If you ask for the same node and different c, you can retrieve the colour
The verifier then asks the provers for edges, sometimes with the same challenge c in order to check that the provers do not cheat and sometimes with a different c in order to check that the edges have different colours. At the end, he learns nothing else because he only gets edge information about random colours. If he tries to cheat and does not follow the protocol, two cases can arise:
- If the verifier asks for two distinct edges, he will get commitments that he cannot unveil at all.
- If he asks for two edges that have one node in common, he will only be able to retrieve the colour of the common node, which is a random colour because colours are randomized at each step as before.
Since the verifier can basically learn only that edges have different colours, this protocol is perfect zero-knowledge as well as perfectly complete and sound.
Entanglement
We have not yet addressed the case of entangled provers. For this, we use a powerful theorem that can transform a protocol that is sound with 2 local provers into a 3-prover-entanglement-sound protocol by adding a third prover that does the same thing as either the first or the second prover. A similar case analysis to the one done in the 2-prover case shows that this protocol remains perfectly zero-knowledge.
In conclusion, the first perfect zero-knowledge and entanglement-sound protocol is surprisingly simple due to the elegant properties of the commitment scheme used. Even more secure protocols should follow from this work.
