Glossary

Covert »

An adversary that is disincentivized to get caught in the act of cheating. A protocol that provides covert security intuitively gives an adversary two options: play honestly, or else get caught by the honest party with a certain probability that is part of the protocol's security guarantee. See AL10. Some protocols (like MR13) provide further guarantees to the honest parties even in the event that an adversary is caught cheating.

Cut-and-choose »

A high-level technique for enforcing correct behavior in a protocol. Roughly speaking, Alice sends ⚠ {$n$} items (e.g., garbled circuits), Bob asks for some number of them to be "opened", so they can be checked for correctness. If all of the opened items are deemed valid, then Bob has a statistical guarantee about the number of unopened items which are correct. Hence, the unopened items can be used in some way for the remainder of the protocol.

Free XOR »

An optimization for garbled circuits in which XOR gates cost nothing: they contribute nothing to the size of the garbled circuit, and they involve no cryptographic operations for garbling/evaluation. Introduced in KS08.

Functionality »

A functionality is a trusted third party that is used as the basis of security in the real-ideal paradigm for security definitions. In most contexts here, it refers to the function that the parties wish to evaluate.

Garbled circuit »

Originally a technique for achieving semi-honest-secure 2PC, garbled circuits are now recognized as a useful primitive in their own right (see BHR12). Yao's foundational paper Y86 is credited with introducing the technique. Roughly, the idea is to associate two bitstrings called wire labels to each wire in a boolean circuit. These wire labels abstractly represent true and false for that wire. Then a garbled circuit contains for each gate an encrypted truth table. For each of the four possible inputs to the gate, we encrypt an output wire label using the corresponding input wires as keys. Intuitively, an evaluator will only know one wire label on each of the input wires, and hence only be able to open one ciphertext and learn one wire label on the output wire.

Garbled row reduction »

A method for reducing the size of a garbled truth table in constructions of garbled circuits. The basic concept was first introduced by Philip Rogaway. Consider the "first" ciphertext ⚠ {$\mathsf{Enc}_{A,B}(C)$} of a garbled gate, where ⚠ {$A,B$} are wire labels of input wires and ⚠ {$C$} is a wire label of the output wire. In a "textbook" garbled circuit, ⚠ {$C$} is chosen randomly. Garbled row reduction suggests to choose ⚠ {$C$} indirectly as the value that causes ⚠ {$\mathsf{Enc}_{A,B}(C) = 0^k$} (this can be made possible when using the point and permute optimization, where the ⚠ {$\mathsf{Enc}$} can be a simple cipher rather than a full-fledge encryption scheme). As such, the first ciphertext does not need to be sent (it will always be the all-zeroes string), reducing the size of the garbled gate by 25%. A more sophisticated technique that reduces the size by 50% was described in PSSW09.

Garbling scheme »

Abstraction of garbled circuits as a cryptographic primitive. See definition in BHR12.

Gate-level cipher »

Scheme used to generate the garbled gate.

Input consistency »

When applying the cut-and-choose approach to Yao's protocol, typically several garbled circuits are evaluated. Input consistency refers to the problem of ensuring that all parties use the same inputs to all garbled circuits.

Malicious »

An adversary that may deviate arbitrarily from the prescribed protocol, in order to learn information, disrupt the other parties, etc. Contrast with semi-honest.

Oblivious transfer (OT) »

A functionality in which a sender provides 2 inputs ⚠ {$m_0, m_1$} (typically strings or single bits), and a receiver provides an input ⚠ {$b \in \{0,1\}$}. The sender receives no output (hence does not learn ⚠ {$b$}), while the receiver learns ⚠ {$m_b$} (hence does not learn ⚠ {$m_{1-b}$}).

Output authenticity »

In Yao's protocol, the receiver evalutes the circuit to learn the output of the function. When adapting Yao's protocol for the case of malicious security, and when the sender must also receive output, output authenticity refers to the problem of ensuring that the receiver does not falsify the output that is reported to the sender.

Point-and-permute »

A method to reduce evaluation time for a garbled circuit. In early "textbook" constructions of garbled circuits, the sender randomly permutes the 4 ciphertexts that comprise each garbled gate, and the evaulator would have to decrypt all 4 ciphertexts (with only one ciphertext decrypting properly). This is done so that the ordering of the garbled gate does not leak the truth values of the wire labels. Using point-and-permute, the wire labels for each wire are randomly given select bits 0 and 1. Since the assignment of select bits is independent of the wire labels' association with true and false, the select bits can be safely revealed to the evaluator, typically as the least significant bit of the wire labels. Then the ciphertexts of the garbled gate can be ordered according to the select bits of the input wires. That way, the evaluator can simply use the select bits he sees as pointers to index the appropriate ciphertext rather than performing trial decryption on all 4. [TODO: acknowledge first instance of point-permute]

Secure computation »

definition here

Selective failure »

Refers to a type of attack in which the sender Alice misbehaves in a way that the receiver Bob will only notice if he has a certain input. Hence, Alice learns partial information about Bob's input by observing whether he aborts. In Yao's protocol and its derivatives, Bob picks up his input for a particular wire using oblivious transfer. Alice can provide one incorrect and one correct wire label to this oblivious transfer, so that Bob picks up an invalid wire label (and eventually aborts) if and only if he has a certain input bit.

Semi-honest »

An adversary that must follow the protocol as prescribed, but may attempt to learn as much as possible about others' inputs from the messages it receives in the protocol.

Universal circuit »

A circuit ⚠ {$U$} that takes two inputs ⚠ {$f$} and ⚠ {$x$} -- where ⚠ {$f$} is itself a description of a circuit! -- and outputs ⚠ {$f(x)$}. Introduced in V76. Can be used to perform 2PC that hides the choice of function being evaluated.