Questions tagged [garbled-circuits]
Garbled Circuits are used in Secure Multiparty Computation
51
questions
1
vote
1answer
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.
2
votes
1answer
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 ...
3
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
2
votes
3answers
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:...
2
votes
1answer
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 ...
4
votes
1answer
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.
...
1
vote
0answers
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)?
1
vote
0answers
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 ...
3
votes
0answers
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$ ...
3
votes
1answer
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 ...
1
vote
1answer
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 ...
5
votes
1answer
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. ...
1
vote
0answers
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 ...
3
votes
1answer
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: "...
0
votes
1answer
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?
1
vote
0answers
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?
4
votes
1answer
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 ...
0
votes
2answers
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 ...
4
votes
1answer
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 ...
6
votes
0answers
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 ...
1
vote
1answer
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 ...
-2
votes
1answer
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 ...
7
votes
1answer
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 ...
5
votes
1answer
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 ...
4
votes
0answers
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, ...
1
vote
0answers
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 ...
2
votes
1answer
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'...
4
votes
1answer
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 ...
4
votes
1answer
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 ...
0
votes
1answer
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 ...
2
votes
2answers
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 ...
13
votes
1answer
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 ...
3
votes
1answer
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 ...
3
votes
1answer
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 ...
5
votes
2answers
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? ...
30
votes
1answer
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 ...
1
vote
1answer
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 ...
1
vote
0answers
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 ...
3
votes
1answer
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 ...
2
votes
1answer
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 ...
4
votes
2answers
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 ...
4
votes
1answer
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 ...
5
votes
2answers
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 ...
2
votes
1answer
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 ...
4
votes
1answer
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 ...
2
votes
2answers
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. ...
4
votes
1answer
739 views
Why can't garbled circuits be reused?
There are a bunch of papers do research on resizable garbled circuits. But I wonder why garbled circuits cannot be reused?
For example, the constructor constructs a garbled circuit of "AND" like this:...
3
votes
1answer
306 views
Implementation of garbled circuits using RSA
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 ...
