Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.
36

A circuit is just a way to represent a computation. There is nothing specifically cryptographic about a circuit. It just means a straight-line computation (no looping or flow-control constructs) consisting of just operations on bits, like AND, OR, NOT. A garbled circuit is a way to "encrypt a computation" that reveals only the output of the computation, but ...


16

Complexity leveraging is a type of reduction where the "reduction algorithm" runs in a complexity class that is greater than the adversary. For example, one may construct a simulator that runs in time $n^{\log n}$ although the adversary is only polynomial time. When considering the simulation paradigm, this is not very satisfactory. For example, in zero ...


15

In order to answer this, you need to be sure to understand how garbled circuits actually work. I'll try to explain this from top to bottom: The protocol Let Alice and Bob be willing to compute securely a function $f(x,y)$ (in your example, it would be $f(x,y)=\min(x,y)$) while keeping their respective inputs $x$ and $y$ secret. In order to do so, they ...


9

A universal circuit is one that can compute any circuit. Specifically, it receives as input the description of another circuit and an input, and it outputs the computation of the given circuit on the given input. In cases where you want to hide the structure of the circuit being computed, a universal circuit can achieve this for you.


8

You will find similar terminology interchanged a lot in this field. So, secure multiparty computation can take the acronym MPC, SFE, SMC and so on. In general, you should look at each paper closely to see what they mean in their definition. However, pretty much secure function evaluation is just another term for secure computation. In contrast private ...


8

One of the security guarantees of garbled circuits is that the evaluator doesn't learn anything about the circuit beyond the output on the given input. Executing more than one input string will break this property. For instance, if you allow him to evaluate two inputs, $0^n$ and $1^n$, then he can "mix and match" bits on each gate to determine what kind of ...


7

Unfortunately, the answer to your question is yes. You have made glaring mistakes. In particular, Yao's garbled circuits are suited for two-party computation only, and here you wish to carry out a multiparty computation. One huge problem that arises with your entire approach is that if the server colludes with one of the voters, then they can learn the ...


7

There has been work on using garbled circuits while also hiding the function. This can be done via implementing a universal circuit inside the garbled circuit. However, the standard garbled circuit does reveal the topology of the circuit. Also, when considering malicious security, the most efficient method is cut-and-choose, and this reveals the actual ...


7

Yes, standard GC are not re-usable, thus by means of GC you may outsource the computation of a single function on a single input (i.e. you delegate a function described by a Boolean circuit and later you may ask the evaluation of the function on a single input not fixed in advance). Indeed this is the approach to Verifiable Computation proposed in a paper ...


7

The problem with induction is what it typically hides. I'll give an example. Assume that I want to prove that $n$ samples of $X$ is indistinguishable to $n$ samples of $Y$, assuming that a single sample is indistinguishable. Instead of doing a hybrid argument, I prove by induction. The base case is immediate, since a single sample is indistinguishable by ...


5

Usually, only AND gates and XOR gates are considered in garbled circuit schemes, because they form a complete basis for boolean circuit - id est, any boolean circuit can be written only with XOR gates and AND gates. In particular, you can implement an OR gate with a single AND gate and only XOR gates, using the fact that $a \text{ OR } b = \text{not }((\text{...


5

The notation you are seeing is for symmetric crypto. Garbled circuits typically use symmetric crypto since it can and symmetric crypto is fast. You may be able to do garbled circuits with asymmetric crypto, but it is definitely non-standard and may have subtle issues.


5

Concerning some trade-offs between GC and FHE, some of these are described in the introductory chapter of Gentry’s PhD thesis available here http://crypto.stanford.edu/craig/. In essence, for a private information retrieval type of scenario where an encrypted data set is stored in the cloud, the communication complexity of a private query is potentially high ...


5

Secure multiparty computation guarantees the nothing whatsoever is revealed by the process of computation. It does not say anything about the function. As you correctly point out, there are some functions that reveal a lot and shouldn't be computed, but this analysis is quite out of the scope of secure computation. The question of whether it's "recommended" ...


5

Here is a concrete example of how the receiver could extract information about the senders input: Assume the circuit to be evaluated is the simple circuit computing $(x \oplus (y \wedge z)) = w$, where $x, y$ is the input of the sender and $z$ the input of the receiver. Note, that $w$ and $z$ alone does not reveal the value of $y$ (you can write down the ...


5

The problem is because sender has provided the receiver with a garbled circuit in which the sender's inputs are hard coded (or has provided keys for those inputs, which is morally the same). If the receiver has both keys for each input wire then it is trivial to narrow down the possible values of the sender's input. Consider a concrete example, the ...


5

I am an author on the FleXOR paper and can comment a bit. Let $A_0$ and $A_1$ are the false/true wire labels on some wire, and let $A_0 \oplus A_1$ denote the offset of that wire. The idea behind free-XOR is that when the 3 wires that touch an XOR gate have the same offset, then the XOR gate can be garbled for free. So you arrange for all wires in the ...


5

Suppose you want Alice to learn $f_A(x,y)$ and Bob to learn $f_B(x,y)$. Then have Alice choose random string $r_A$ and have Bob choose random string $r_B$. The parties should perform a secure computation where both parties learn $(f_A(x,y) \oplus r_A, f_B(x,y) \oplus r_B)$. Basically each party's designated output is masked by a one-time pad that only that ...


4

I don't know of any Yao-type garbling scheme where Encode is probabilistic. Think about Yao circuits - the encoding is providing the garbled key on the input wire for the associated bit. Note that the garbling is of course probabilistic and must be. However, once the garbling is fixed, the encoding is typically deterministic. Having said the above, as a ...


4

Alice does not need to hard-code her input and does not need to shuffle the gates (it is only necessary to shuffle the ciphertexts inside each gate). Bob needs to hold a key on every input wire. For the input wires associated with Alice's input, she can just send the appropriate key (this reveals nothing since both the 0 and 1 values are just random).


4

There are two separate issues here: Guaranteed output / fairness: how does the protocol prevent Bob from withholding Alice's output (guaranteed output), or at least prevent him from learning the output himself when he decides to withhold output from Alice (fairness)? The short answer is that garbled circuit protocols do not provide any such guarantees. The ...


4

Regarding the NOT gates in your example. Suppose the wire called $b$ has wire labels $B$ for false and $B \oplus R$ for true. Then you would garble gate "AND1" using these labels as normal, and you would garble gate "OR1" imagining that $B \oplus R$ means false and $B$ means true. There are two equivalent ways to think about this. One is to consider the ...


4

Your intuition is correct, the encryption is set up to indicate a failed decryption when an incorrect key is used with the ciphertext. A very simple way of doing so can be as follow: when encrypting the message $m$ with the key $K$, encrypt $m||0^{\lambda}$ ($\lambda$ is a security parameter, e.g. 80 or 128). When decrypting a ciphertext, check whether the ...


3

The first three columns in Table (b) are the random keys that $P_1$ has chosen to associate with the bit values on the two input wires and the output wire, respectively. The fourth column is the actual garbled gate information. I.e., the garbled values that $P_1$ sends to $P_2$, and $P_2$ uses to evaluate the garbled gate. Note, that if $P_2$ is given keys $...


3

The problem is known in the literature as private function evaluation (PFE). A sender has input (a function) $f$; a receiver has input $x$, and only the receiver learns $f(x)$. If you are willing to leak the topology of a circuit that computes $f$ (but not the identity of the gates), then using classical garbled circuits / Yao's protocol will work. These ...


3

That summary, on which you are basing your understanding, seems bogus to me. Clearly the same $K_i^b$ values are being used as one-time pad keys, but are being used more than once. This is a major red flag. Here's an even simpler attack: if you XOR together all 4 ciphertexts $X_s^{i,j}$ you will get $\Delta = K_k^0 \oplus K_k^1$. Since the functionality of ...


3

I don't understand why Alice needed to hard-code her input and rearrange the gates. Could she not have just given Bob the circuit as is and the keys to her inputs? Alice needs to hardcode her input because both parties must NOT learn each other's input values. The whole point of the Garbled Circuit is to devise a way where both parties will learn the wanted ...


3

The width of a circuit is in some sense related to concept of circuit depth which you appear to already be familiar with. To understand these concepts it is very helpful to think about the graphic representation of circuits in the form of circuit diagrams. I drew an example of such a diagram here: The depth of a circuit is loosely speaking the number of ...


2

From Adaptively Secure Garbled Circuits from One-Way Functions: Note that, if we think of the circuit as representing a Turing Machine or RAM computation, then the width w of the circuit corresponds to the maximum of the input size n, output size m, and space complexity s of the computation. The space complexity indicates how much space (memory, usually ...


2

First of all, having a precise definition of garbled circuit is a bit cumbersome - if you want to see a clear and nice (formal) definition, I suggest looking at page 2 of this article. The purpose of a randomized encoding is to create, from a function $f$ and an input $x$, an encoding $\phantom{i}\hat{f}(x;r)$ such that: Correctness: there is an algorithm $...


Only top voted, non community-wiki answers of a minimum length are eligible