# Questions tagged [garbled-circuits]

Garbled Circuits are used in Secure Multiparty Computation

51 questions
Filter by
Sorted by
Tagged with
59 views

### Do garbled circuits run in constant time?

It seems like garbled circuits should not be input dependent, and hence should always run in constant time. Just wanted to clarify if this is true.
57 views

### half-gates in garble circuit

Recently I've been reading papers about MPC protocol, but when I read the paper by Zahur, S., M. Rosulek, and D. Evans. 2015 Two Halves Make a Whole- Reducing Data Transfer in Garbled Circuits Using ...
122 views

### Induction is problematic in computational cryptography - Why?

In Dr. Lindell's lecture The Yao Construction and its Proof Of Security, in briefly explaining the hybrid argument, he makes the statement that mathematical induction is a problem in computational ...
55 views

### What does universal look like? What is the complexity(size/depth) of universal circuit

I was reading a paper about attribute based encryption. The authors showed that ciphertext-policy ABE can be constructed from key-policy ABE using universal circuit. But the universal circuit should ...
93 views

### Secret shared input for garbled circuit?

I’m curious about what the secret shared input for a garbled circuit is. Essentially, a garbled circuit is a two party computation framework where each of two players has each input as bit string. In ...
246 views

### How to encrypt the truth table in garbled circuits?

I'm learning about garbled circuits, and I'm using the following tutorial: Yao's Protocol. I have a questions regarding to construction (encryption) of truth table in garbled circuits. Slide 14 says:...
60 views

### What is shared-input for Multi Party Computation?

I heard shared input. For example, original values $x,y \in M$ are divided into pairs of shares $(x_1,x_2)$ and $(y_1, y_2)$ such that $x_1 + x_2 = x \text{ and } y_1 + y_2 = y$. Each share is ...
70 views

### Optimized Garbled Circuit Algorithmic Description

The Garbled Circuit (GC) is now over thirty years old, and many optimization methodologies have been proposed, including point-and-permute, row-reduction, free-XOR, fixed-key blockcipher, half-and. ...
72 views

### Are software solutions such as FHE, PHE, Garbled Circuits used in practice?

Is Fully Homomorphic Encryption or Partially Homomorphic Encryption or Garbled Circuits used in practice? Or is an alternative used instead (I don't mean encryption just for storage here)?
83 views

### Optimized Random-OT Security in Standard Model

I was going through the paper - " Efficient Oblivious Transfer and Extensions for Faster Secure Computation" by Asharov et al. where the authors propose an optimized OT protocol along with a Random-OT ...
113 views

### Can “nothing-up-my-sleeve” computations be obtained from other cryptosystems?

So, in cryptography, it is sometimes the case that in order to set up a cryptosystem, one needs some output $f(x)$ for randomly generated $x$ where $f$ is a one-way function but where the input $x$ ...
207 views

### Explanation of correlated randomness for garbled circuits

While studying Yao's garbled circuits I was mentioned that correlated randomness played some part in MPC. I looked for online documentation but everything I've found is far too complicated for me to ...
68 views

### Which party have to be online during garbled circuit-based MPC protocol?

Suppose that Alice, Bob and Charlie want to compute some functions without revealing each input to the function one another. We can construct the protocols using garbled circuits by multiple ...
143 views

### How to know when decryption fails in Yao's Garbled Circuits

I'm reading A Gentle Introduction to Yao's Garbled Circuits, and I came across this passage: Note that in order for this to work, Evan needs to know when decryption succeeds, and when it doesn’t. ...
93 views

### Suppose that Alice is malicious, but Bob behaves honestly during the execution of the protocol.

Suppose that Alice has a secret bit $a$ and Bob has a secret bits $b_1,b_2$ and that Alice and Bob want to compute the function $h(a,b_1,b_2)=b_1 \wedge (b_2 \oplus a)$ using Yao's Garbled Circuit ...
89 views

### Sign a plaintext accepted by a secure function without revealing private key

Imagine the following scenario: Alice is a well-respected chef. She is famous for reviewing recipes. Anyone can send her a recipe. If she likes it she'll add her famous line of approval to the end: "...
161 views

### Is garbled circuit a post-quantum primitive?

I understood garbled circuit can hide some function $f$ jointly by multi parties. With quantum computer, can we see the circuit inside it?
56 views

### What does “hard-coded” mean in the context of garbled-circuit?

What does "hard-coded" mean in the context of garbled-circuit? Is it not encryption?
1k views

### Constructing Garbled Circuits

I have been recently working on garbled circuits for a course and I think I don't have the the proper background for understanding them. I don't know how to approach such problems. Here is an ...
357 views

### Yao's Garbled Circuit with different outputs

In a lecture I was told of a a possibility to modify Yao's Garbled Circuit Protocol so that both parties in the end get each a part of the output but not the other part. This may be achieved by ...
287 views

### Garbled circuits: How can the sender safely retrieve the output?

I've read a few papers about how Yao's Garbled Circuit protocol can be made secure against malicious adversaries, but I haven't seen any mentioning how the sender safely retrieves the output of the ...
235 views

### Share Conversion between Different Finite Fields

Let us have any linear secret sharing scheme (LSSS) that works on some field $Z_{p}$, where p is some prime or a power of a prime e.g., Shamir Secret Sharing, Additive secret Sharing. The problem at ...
308 views

### What is difference between Yao's “Garbled Circuit” and ther “Garbling Scheme” given by Bellare et al?

What is difference between Yao's "Garbled Circuit" and the "Garbling Scheme" given by Mihir Bellare, Viet Tung Hoang and Phillip Rogaway in "Foundations of garbled circuits"? I also want to know is ...
109 views

### Explain Garbled circuit having function and single input?

I came across below Image of garbled circuit and want to know what exactly is garbled circuit and if we consider two party computation then how can we differentiate between f and x as Alice and Bob's ...
638 views

### Why XOR and NOT is free in garbled circuit

I am having trouble understanding the term "free" in V.Kolesnikov et al's paper. 1. Why NOT is free In page 4, section 3.1, they said that NOT gate is free by simply eliminating them and ...
115 views

### How OR gates are garbled in recent optimizations techniques like free XOR, Half Gates?

I am a research student and I have been studying garbled circuits, specifically its optimization techniques. However, in every research paper i have encountered, the researchers have only shown how to ...
57 views

### Performing DFS search with garbled boolean circuit

Given $G=(V,E)$ How can i implement a DFS search in the Boolean circuit? ( The output should be to assign each node it's DFS value from a root node) I assume the complexity should be exponential, ...
200 views

### How to implement division using Garbled Circuit

Implementing Addition, Subtraction and even N-bit Multiplication can be done fairly quickly and intuitively using garbled circuit, since no looping, control unit nor state machine is needed. One just ...
365 views

### Why is garbled circuit a randomized encoding?

In Garbled Circuit, a circuit C is encoded to C' and input x is encoded to x' such that only C(x) can be computed given C' and x'. Randomized encoding of a function f is another randomized function f'...
517 views

### Difference between secure function evaluation and private function evaluation?

Yao's garbled circuit is used to compute multiparty computation. I know that secure function evaluation is used to hide users input and circuit from each other. Can any body tell me what is private ...
459 views

### What is Universal Circuit $U_{e}$

I was reading research Paper. In which writer talks about universal circuit. I want to know how is universal circuit $U_{e}$ different from simple circuit. What properties they have. Is they hide ...
411 views

### What is p.p.t simulator?

I was reading research paper Reusable Garbled circuit in which i read the term "p.p.t Simulator" and p.p.t Algorithm. I know about Probablistic Polynomial Time(p.p.t) Algorithm. Kindly someone tell me ...
207 views

### Garbled Circuit

In Garbled Circuits party $P_1$ garbles the original truth table by arbitrary choosing or by some other method values. Table (b) represents the garbled values corresponding to each entry in the ...
813 views

### What is complexity leveraging

Complexity leveraging is a technique that is generally used to prove adaptive security of a selectively secure scheme. Eg: We can prove adaptive security of Yao's garbling scheme using complexity ...
171 views

### Offline Complexity of the garbling scheme

The offline complexity of the garbling scheme means the time complexity of the circuit encoding algorithm, that is, $\textrm{GC.Circ}(1^\lambda, C)$, where $C$ is the circuit to be garbled. It's ...
58 views

### How to compute the output length of randomized encoding (or garbling)?

We consider randomized encoding for circuits as a equivalent primitive as the circuit garbling scheme. However, I have a question arised from their syntax, that is, how to compute the output length of ...
506 views

### What's the definition of the width of a circuit

We consider the size and depth of a circuit under most situations, but recently I read some papers which consider the “width” of a circuit, so I wonder what's the definition of the width of a circuit? ...
7k views

### What exactly is a “garbled circuit”?

There are plenty of questions here about the details and how-to's of "garbled circuits", but I have not seen anything that defines what garbled circuits are. What exactly is a garbled circuit? What ...
76 views

### The Encode algorithm of Garbling scheme is probabilistic or deterministic?

In general the garbling scheme works as follows: $\textrm{Garb}(1^\lambda, C)$: on input the security parameter $\lambda$ in unary and the circuit $C$, it outputs a garbled circuit $\widehat{C}$ and ...
75 views

### Secure Communication Protocol Design using oblivious transfer?

I have a problem I need to solve with the following scenario and I hope someone can help me find an approach or direction to start tackling it. Consider Alice as a sender who has $n$ strings which ...
261 views

### Difference between FleXOR and Free-XOR

I would like to know the differences between FleXOR and Free-XOR. I searched in the web but I couldn’t understand the information I found. I understand that there are both cryptographic methods as ...
582 views

### Yao's Garbled circuit: Does Bob ever see the circuit?

I asked a question about whether the circuit structure for Yao's garbled circuit needs to be rearranged. I understand from Yehuda Lindell's response that the circuit structure itself does not need to ...
524 views

### Yao's Garbled Circuit- Why does Alice need to rearrange the circuit?

My understanding of Yao's Garbled Circuit (based mostly on this summary) is as follows: Alice creates a garbled circuit based on the function f to be computed. She then hard-codes her input into the ...
299 views

### Have I made any glaring mistakes in my use of Yao's garbled circuits?

I would like to use garbled circuits to provide a service that allows people to vote where they do not need to reveal their votes to my server or to anyone else. Let's assume that I have secure ways ...
602 views

### Homomorphic Encryption vs. Garbled circuits

I'm currently trying to understand all the differences between homomorphic encryption and garbeled circuits. As I understood the use of homomorphic encryption hides either the data or the computation ...
214 views

### A secure function evaluation problem and an alternative of 1 out of n oblivious transfer?

I am considering a "secure function evaluation" problem: Consider two parties: A and B. A has a one-to-one mapping function $f(x)=k$. Basically, the function $f(x)$ can be regarded as a table of two ...
96 views

### Leakage in Secure Two party Computation

Am trying to understand Garbled Circuit based approach for Secure Two party Computation. There isn't much leakage in the classic millionaire's problem where the comparison circuit is used. But ...
280 views

### What if OT breaks in Yao's garbled circuit?

Two semi-honest parties are computing F with Yao's garbled circuit. Sender garbles it with his inputs baked in then sends it to the receiver. At this point the receiver must use OT to get his keys. ...
I was just reading these notes on garbled (Yao) circuits and I just stuck trying to figure out how an implementation of Table 1 would work using RSA encryption. In RSA the public key is $(n,e)$. So ...