Questions tagged [garbled-circuits]
Garbled Circuits are used in Secure Multiparty Computation
66
questions
0
votes
0
answers
48
views
Can a circuit in a zk-SNARK be reversed-engineered?
The definition of zk-SNARK involves not leaking any information from the prover-verifier interaction, but what about leaking information from the circuit itself? e.g., could there be a circuit to ...
- 1
1
vote
1
answer
69
views
What is the essential difference between Garbled Circuit and Oblivious Transfer?
According to the literature (https://en.wikipedia.org/wiki/Garbled_circuit), Oblivious Transfer allows a party A holding a function $f$ and a party B holding a index i to jointly compute the value $f(...
- 35
1
vote
1
answer
39
views
Question about round complexity of secure multiple party computation based on secret sharing
I am reading Fast and Secure Three-party Computation:
The Garbled Circuit Approach
And in the introduction section it said that:
the round complexity of these protocols is proportional to the
...
- 99
2
votes
1
answer
40
views
Leaking information for giving the yao's garbled circuit's garbled output
I am currently reading the paper: Efficiency Tradeoffs for Malicious Two-Party
Computation. The paper describes a $k$-leak model and gives an example that leaking 1 bit could turn Yao's garbled ...
- 99
1
vote
1
answer
85
views
How to securely set constant values inside garbled circuits?
Suppose there are some constant values which must be set inside the circuit. The naive way is to simply pass the needed constants as inputs to the circuit. But this seems wasteful.
What it the proper ...
- 60
0
votes
0
answers
34
views
Can a garbler "open" a circuit by "opening" only her input labels and AND tables?
I'm using the word "open" as in chapter 6 "Malicious Security" of Pragmatic MPC, i.e. to "open" the circuit is for the garbler to provide all the randomness used to ...
- 60
3
votes
1
answer
111
views
How can malicious garbling compromise evaluator's input in Yao's garbled circuit
Suppose, we have a circuit which outputs a sha256 hash of a concatenation of Alice's input and Bob's input (where Alice is the garbler and Bob is the evaluator).
I am trying to understand what methods ...
- 60
1
vote
0
answers
55
views
What security does the BMR protocol offer against corruption?
I've been conducting some research into general-purpose MPC protocols and have been unable to pinpoint the exact security offered by the BMR protocol. The reference I've been using for the majority of ...
- 13
1
vote
1
answer
93
views
SS/HE/GC/OT secure integer comparison
I have been reading some papers to find a 'faster' way to compare two integers without revealing their real values. But I think I'm a bit lost in those papers due to my limited knowledge in ...
- 73
1
vote
0
answers
40
views
Multiparty computation on circuits that perform group operations
I see that a lot of multiparty computation and garbling protocols are implemented for circuits like AES or SHA256.
For my project, I would like to garble a circuit that performs some group operations ...
- 1,274
2
votes
2
answers
97
views
Boolean circuit: can the output wire of a gate be used by many different gates in the next layer?
There are two typical secure multiparty computation paradigms using boolean circuits, namely garbled circuit and secret-sharing-based boolean computation. It is well-known that garbled circuits can be ...
- 187
6
votes
2
answers
104
views
Garbling in the wild (soft question)
I am curious to know whether (Yao's) garbled circuits are actually deployed in practice. There has a lot of works on optimising garbled circuits (e.g., here and here) and I am interested in whether ...
- 4,463
2
votes
2
answers
157
views
Does Cut-Choose technique for yao garbled circuit provide statistical security?
Yao Garbled circuit is 2 parties secure computation protocol between Semi honest adversaries. However, the cut-and-choose mechanism complies semi-honest garbled circuits into the one secure against ...
- 23
2
votes
2
answers
170
views
Concrete Example of AND Gate Using Garbled Circuit
Most of the resources online like the wiki presents the beautiful idea of Garbled circuit in a rather unnecessarily abstract manner. This is the screenshot of Wiki's protocol:
What would be an ...
1
vote
0
answers
68
views
Encrypting text with AES and MPC
I'm thinking of implementing text encryption and decryption in my program using AES using key sharing thanks to MPC (the point is that the key should never be provided in full), however, all public ...
- 11
2
votes
1
answer
85
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.
- 408
3
votes
1
answer
295
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 ...
- 31
4
votes
1
answer
167
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 ...
- 85
1
vote
1
answer
76
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 ...
- 31
0
votes
1
answer
167
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 ...
- 1,495
2
votes
2
answers
318
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:...
- 123
2
votes
1
answer
84
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 ...
- 1,495
4
votes
1
answer
109
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.
...
- 75
1
vote
0
answers
82
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)?
- 411
4
votes
0
answers
127
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 ...
- 447
3
votes
0
answers
121
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$ ...
- 708
3
votes
1
answer
410
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 ...
- 33
1
vote
1
answer
87
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 ...
- 1,495
5
votes
1
answer
196
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. ...
- 155
1
vote
0
answers
101
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 ...
- 207
3
votes
1
answer
100
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: "...
- 153
1
vote
1
answer
228
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,495
2
votes
0
answers
58
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?
- 1,495
5
votes
1
answer
2k
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 ...
- 153
1
vote
2
answers
420
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 ...
- 11
4
votes
1
answer
400
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 ...
- 43
9
votes
0
answers
326
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 ...
- 812
2
votes
1
answer
434
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 ...
- 131
-1
votes
1
answer
127
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 ...
- 131
7
votes
1
answer
941
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 ...
- 369
5
votes
1
answer
150
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
0
answers
68
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, ...
- 445
1
vote
0
answers
238
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 ...
- 369
3
votes
1
answer
601
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'...
- 1,274
5
votes
1
answer
648
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 ...
- 565
6
votes
1
answer
774
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 ...
- 565
0
votes
1
answer
627
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 ...
- 565
2
votes
2
answers
233
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 ...
- 565
14
votes
1
answer
1k
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 ...
- 1,274
4
votes
1
answer
207
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 ...
- 862