Zero knowledge from privacy-free garbled circuits

2 Message order and the security it gives

What can be proved about the protocol of [ JKO13 ] depends less on the garbling scheme than on the order of the messages: when the prover’s witness bits become fixed, compared with the moment it sees the garbled circuit, and when the verifier opens its garbling, compared with the moment the prover discloses its output label. The literature fixes these choices in different places, often only in a figure or a footnote. This chapter collects them, says which kind of security each choice allows, and points to the statements of this library that cover it. The chapter is expository and is not itself formalized. It contains no new statement; every claim about the library refers to a theorem proved in a later chapter, and a phrase such as “soundness needs adaptive authenticity” describes what the proofs here use, not a proved necessity.

2.1 The protocol in order

In the protocol of Jawurek, Kerschbaum and Orlandi [ JKO13 , Sect. 1.1, Fig. 1 ] the messages are, in order:

  1. the prover runs the oblivious transfers as receiver, one per bit of its witness \(w\); the verifier, as sender, inputs the two labels of each input wire;

  2. the verifier sends the garbled circuit (with a two-round OT, together with its second message);

  3. the prover evaluates and commits to the output label it obtained;

  4. the verifier opens its garbling: the seed, and all its inputs to the oblivious transfers (“open-all”);

  5. the prover checks that the opened garbling is a garbling of the agreed circuit and agrees with the labels it received, and only then reveals its committed label;

  6. the verifier accepts if the label is the output label for the value \(1\).

Three choices determine the security: the position of step 2 with respect to the moment the witness bits are fixed in step 1; whether step 4 exists and comes after step 3; and how the commitment and the oblivious transfer are realized.

2.2 When the witness bits are fixed: static or adaptive authenticity

Witness fixed before the garbled circuit is seen. If the receiver’s message in the OT determines its choice bits, and the garbled circuit is sent only afterwards, the prover’s input does not depend on the garbling. Soundness then needs only the static authenticity of the garbling: the input is chosen first, and the adversary must forge the other output label. This is the order of [ JKO13 ] , who note that the garbled circuit may travel with the second message of a two-round OT [ JKO13 , Sect. 1.1 ] , and that sending it before the oblivious transfers would require a garbling secure against adaptive attacks [ JKO13 , Sect. 3, footnote 7 ] . In this library: soundness reduces exactly to the authenticity game (Theorem 4.8), bounded by \((q+1)/(|V|-1)\) in the random oracle model (Theorems 6.9 and 6.12). The PVW OT in messy mode is of this kind: the receiver’s key determines its choice, which a trapdoor extracts (Lemma 9.4, Theorem 9.9).

Witness fixed after the garbled circuit is seen. If the garbled circuit is sent before the oblivious transfers, or if the OT lets the receiver postpone its choice, the prover may choose its witness bits as a function of the garbled circuit. Soundness then needs adaptive authenticity, in which the adversary sees the garbled circuit and requests its input labels one at a time [ BHR12 , Sect. 4, Fig. 6 ] . The Chou–Orlandi OT is of this kind: the receiver’s message does not fix its choice, and a receiver can delay the decryption until after it has seen the garbled circuit ( [ BPRS17 , Sect. 3 ] , [ DKLs18 , App. A ] ; see also [ CO15 , Sect. 1.1 ] ). In this library: adaptive authenticity for the garbling formalized here, with bound \((q+1)/(|V|-1) + q/|V|\) for \(q\) actions (Theorem 10.17), and soundness with the Chou–Orlandi OT, by reduction to square Diffie–Hellman (Theorem 11.2).

2.3 When the garbling is opened: honest or malicious verifier

No opening. If the prover sends its output label directly and the verifier never opens the garbling, the protocol is zero knowledge only against an honest verifier [ JKO13 , Sect. 3 ] : a malicious verifier can garble a circuit other than the agreed one, or mount a selective-failure attack in the input phase [ JKO13 , Sect. 1 ] . In this library: honest-verifier zero knowledge (Theorem 4.9), and an explicit malicious verifier that learns a witness bit from the OT pairs alone (Proposition 4.10).

Commit, open, check, reveal. With steps 3 to 5 in this order the protocol is zero knowledge against a malicious verifier, with a single garbled circuit. The opening is possible because in zero knowledge the verifier has no secret input, unlike in general two-party computation [ JKO13 , Sect. 1 ] . The order matters: the prover must commit to its label before the opening, check the opening, and reveal the label only afterwards. The OT must allow this opening, so that the prover can check that the labels it received are those of the opened garbling [ JKO13 , Sect. 1.1 ] . In this library: perfect zero knowledge in the hybrid model (Theorem 4.5).

The garbling cannot be opened. When the garbler has inputs or keys that must stay secret, the garbling cannot be opened at the end, and a malicious garbler is handled by cut-and-choose: several garbled circuits, some opened and some evaluated. If one good evaluated circuit suffices, choosing each circuit with an independent fair coin gives error \(2^{-N}\) [ Lin13 ] . In this library: Theorems 13.3, 13.4 and 13.9.

2.4 How the commitment and the oblivious transfer are realized

Ideal functionalities. With ideal OT and ideal commitment, zero knowledge is perfect and soundness is exactly the authenticity game (Theorems 4.5 and 4.8).

Hash commitment in the random oracle model. Zero knowledge becomes statistical, with error at most \((q_1+q_2+q_3)/|R|\) for a verifier making \(q_1+q_2+q_3\) oracle queries; the simulator programs the oracle (Theorem 7.7). Soundness goes through an extractor that reads the prover’s queries, at an extra cost \((q_1^2+q_2+1)/|D|\) for \(q_1\) queries before the commitment and \(q_2\) after it (\(n_1\) and \(n_2\) in Theorem 7.15) (Theorems 7.11 and 7.15).

PVW OT with a common string. In messy mode the receiver’s choice is extractable, and soundness keeps the bound of the hybrid model (Theorem 9.9). Zero knowledge is computational: it is reduced to DDH by two explicit distinguishers between the modes (Theorems 9.16 and 9.20). The receiver key \((0, 0)\) sends the messages in the clear, and the sender in this library rejects every key whose first component is \(0\) (Lemma 9.4).

Chou–Orlandi OT in the random oracle model, without common string. Receiver privacy is perfect and zero knowledge holds with the real OT and the hash commitment (Theorem 8.7). Soundness needs adaptive authenticity, and costs \(k/q\) for a secret \(a_j = 0\) plus the advantages of explicit square Diffie–Hellman solvers (Theorem 11.2). Chou and Orlandi withdraw the claim of UC security of their protocol [ CO15 , Sect. 1.1 ] .

2.5 When parties are corrupted

The security theorems of this library assume static corruptions: the adversary decides at the start which party it controls. Chapter 12 proves some ingredients for adaptive corruptions, but no security statement against them. In the framework of universal composability (UC) party corruption is modelled by conventions on top of the basic model of execution [ Can20 , Sect. 7.1 ] . The formulation given there captures adaptive corruptions: the adversary corrupts parties as the computation proceeds, based on what it has seen, and receives the entire local state of a corrupted party. Static corruptions, where the corrupted parties are fixed before the computation starts, are a weaker threat model, and the setting where erasures are not trusted corresponds to protocols that write each data cell at most once [ Can20 , Sect. 7.1.1 ] . Against adaptive corruptions a simulator must produce the transcript without the witness and, when the prover is corrupted later, explain it: produce internal randomness consistent with the actual witness [ GKPS18 , Sect. 1.2 ] .

Why it matters with two parties. We add a remark of our own. In a single proof between two parties the verifier has no secret input, and a corrupted prover hands over its witness anyway. Adaptive security matters most when the proof is a component of a larger protocol, with many sessions or many parties, in which devices may be compromised at different times: the security proof of the larger protocol, through the composition theorem [ Can20 , Theorem 22 ] , then relies on every component being simulatable under late corruption. Ganesh, Kondi, Patra and Sarkar motivate adaptive security by adversaries that use their resources gradually, and by applications that use the protocol of [ JKO13 ] as a component [ GKPS18 , Sect. 1.3 ] .

What has to be explained, and when. In the protocol of [ JKO13 ] the verifier has no input, so its state never needs to be faked, and once the prover holds its output label nothing it does depends on the witness [ GKPS18 , Sect. 3.2 ] ; in this library the revealed label is the simulator’s output (Theorem 4.5). What must be explained therefore depends on the moment the prover is corrupted. The table is our reading of the protocol; [ GKPS18 ] prove the case of an ideal commitment, stated after it.

Prover corrupted

To be explained

Property used

before the oblivious transfers

nothing

none

after the oblivious transfers, before the commitment

its OT messages, for the actual witness

receiver-equivocal OT

after the commitment, before the opening

its OT messages and its commitment

also an equivocal commitment

after the label is revealed

its OT messages; the commitment is already opened

receiver-equivocal OT; the label does not depend on the witness

A receiver-equivocal OT is a secure OT whose receiver message can be produced, from the trapdoor of the setup, without the choice bit and later opened to either bit [ GKPS18 , Sect. 3, Definition 3.1 ] ; the PVW OT in decryption mode is one, assuming DDH [ GKPS18 , Sect. 3.3, Theorem 3.2 ] . DDH is used for the security of the OT; the equivocation itself is exact (Theorem 12.2). With an ideal commitment there is nothing to explain. A hash commitment in the programmable random oracle model can be equivocated by setting the oracle at the committed point after the fact, a technique recalled in [ GKPS18 , Sect. 1.2 ] . With a receiver-equivocal OT and an ideal commitment, the protocol of [ JKO13 ] is secure against adaptive corruptions [ GKPS18 , Sect. 3 ] ; after the execution, the only work is to equivocate the prover’s view of the OT [ GKPS18 , Sect. 3.2 ] .

The other choices. The order of the messages interacts with the corruption time. For the Chou–Orlandi OT we note the following, which follows from the form of the messages: the receiver message \(B = b \cdot g + wA\), with \(A = a \cdot g\), is also \((b + (2w - 1) a) \cdot g + (1 - w) A\), so explaining it for the other choice bit requires the sender’s secret \(a\). The simulator knows \(a\) when the verifier is honest, and otherwise learns it only at the open-all step, so a corruption of the prover before the opening is the delicate case. If the garbler has an input of its own, as in general two-party computation, the garbled circuit itself must be equivocated, which requires much heavier tools [ GKPS18 , Sect. 3.2 ] . Without erasures there is more to explain, and adaptively secure oblivious transfer is harder to build [ BPRS17 ] .

In this library. Adaptive security itself is not formalized: neither the UC framework, nor a model of execution with corruptions. Chapter 12 proves the protocol-specific facts behind the table: the receiver of the PVW OT in decryption mode, with the trapdoor of the setup, and the receiver of the Chou–Orlandi OT, with the sender’s secret, satisfy the equivocation condition on messages and randomness (Theorem 12.2, Proposition 12.4); under that condition the prover’s OT messages, and the verifier’s view of the prover, can be explained for any witness (Theorem 12.5); the hash commitment can be equivocated by programming the oracle (Theorem 12.6); and soundness holds with the PVW OT in decryption mode, up to the DDH advantage (Theorem 12.7). These are ingredients only; they are not composed into a simulation. A somewhat restricted variant of the UC framework has been mechanized in EasyCrypt by Canetti, Stoughton and Varia, with a worked example [ CSV19 ] . The README of the public core of CatCrypt lists machinery for universal composability in Lean, and says that the universal-composability theory itself is in separate distributions [ CCcore ] .

2.6 Summary

Choice

Security that can be expected

In this library

Witness fixed, then garbled circuit

Soundness from static authenticity

Theorems 4.8, 6.12, 7.15, 9.9

Garbled circuit first, or OT with late choice

Soundness needs adaptive authenticity

Theorems 10.17, 11.2

No opening

Honest-verifier zero knowledge only

Theorem 4.9, Proposition 4.10

Commit, open, check, reveal

Zero knowledge against a malicious verifier, one circuit

Theorems 4.5, 7.7, 8.7, 9.20

Garbling cannot be opened

Cut-and-choose, error \(2^{-N}\)

Theorems 13.4, 13.9

Ideal OT and commitment

Perfect zero knowledge

Theorem 4.5

Hash commitment (random oracle)

Statistical zero knowledge, programmable oracle

Theorem 7.7

PVW OT, messy mode

Computational zero knowledge (DDH)

Theorem 9.20

Chou–Orlandi OT

Soundness by reduction to square Diffie–Hellman

Theorem 11.2

Adaptive corruptions

A receiver-equivocal OT with an ideal commitment suffices [ GKPS18 ]

Some ingredients: Theorems 12.2, 12.5, 12.6, 12.7; adaptive security itself is not formalized (Section 2.5)

Security against adaptive corruptions, a different axis, is discussed in Section 2.5.