Questions tagged [garbled-circuits]
Garbled Circuits are used in Secure Multiparty Computation
81
questions
3
votes
1
answer
173
views
LPN Encryption Homomorphism
Trying to understand the LPN encryption in this paper: https://eprint.iacr.org/2021/120.pdf. From Definitions 4 and 5, ciphertext is $c=C\cdot s\oplus e\oplus G\cdot m$ and the paper says the LPN ...
- 149
0
votes
1
answer
29
views
2-PC vs Secure function evaluation vs private function evaluation
I'm currently confused about the distinctions between two-party computation (2-PC), secure function evaluation, and private function evaluation. Additionally, I came across the term secure circuit ...
- 472
1
vote
1
answer
35
views
The reference of external values in Garbled Circuit
Is anyone aware of the source for a technique that incorporates external wire values into Garbled Circuits? I have come across this technique, which can be found here. However, I was unable to locate ...
- 472
0
votes
1
answer
25
views
why the intermediate labed value should be encrypted in Garbled Circuits?
I do not know why the intermediate value (for example, W5, W6) should be encrypted??
I think the encryption (random value) only needs in the input process (e.g. w1, w2, w3, w4).
1
vote
0
answers
45
views
Understanding Garbled Circuit Design in Gazelle Protocol
I have been examining the Gazelle paper, which focuses on secure inference protocols. One section constructs a Garbled Circuit using inputs cx, sx, and sy to compute the ReLU function in neural ...
- 11
1
vote
0
answers
33
views
How is a message $\mu$ encrypted in a witness encryption scheme below? What does C(x) = 1 mean below?
I was reading this paper, where I came across the following statement on Pg 4 under the Homomorphic Commitments:
A witness encryption scheme, associated with a
NP language, consists of an encryption ...
- 41
3
votes
1
answer
115
views
Garbled circuit and secret sharing
Recently, I was reading the paper One Hot Garbling published on CCS 2021. I noticed a sentence in it:
In this work, we forgo the standard GC notation of garbled labels in
favor of garbled sharings of ...
- 102
4
votes
1
answer
111
views
How can Garbled Circuits be utilized to reduce the round complexity of GMW?
I've been reading this set of notes on some topics in MPC and am having difficulty understanding the transformation the authors make in order to reduce the round complexity of the GMW protocol through ...
0
votes
1
answer
111
views
Conditional Boolean circuits
I have two questions I couldn't find straightforward answers to after many searches.
(1) We can perform 2-party MPC over arbitrary functions using Garbled Circuit. To do that, we first need to convert ...
- 103
1
vote
1
answer
161
views
Binary Secret Sharing vs Garbled Circuits
In Privacy-preserving machine learning, GC is usually used for privacy operation such as ReLU(x) where sign(x) needs to know. However, binary secret sharing also supports such computation via ...
- 11
2
votes
0
answers
50
views
Reusing input labels in half-gate construction
In the half-gate construction of garbled circuits, is it possible to garble multiple instances of a circuit while re-using certain input labels?
Suppose Alice and Bob would like to compute a function ...
- 21
0
votes
0
answers
38
views
Multiple input AND/OR gate evaluation
In MPC, AND and XOR gates are two mostly used gates. However, most of the solutions (Garbled Circuit or Boolean Secret Sharing) considered these gates having 2 input wires and 1 output wire.
I am ...
- 149
1
vote
1
answer
93
views
How to encrypt in garbled circuits
I’ve read a lot of articles and a lot of questions here to understand how the encryption is done in garbled circuits. As I understand double encryption is to encrypt the gates and the truth table. The ...
4
votes
1
answer
117
views
How Cut-and-Choose can leak information?
I'm currently reading the book "A Pragmatic Introduction to Secure Multi-Party Computation". On pages 103-104 I came across the following related to the Cut-and-Choose technique:
If $P_2$ ...
- 848
1
vote
0
answers
63
views
Will two-party garbled-circuit based protocol have any security issue when inputs are from multiple parties?
If the inputs for a garbled circuit are from multiple parties, can parties (not garbler, not evaluator) obtain the labels corresponding to its input from the garbler via oblivious transfer then send ...
0
votes
0
answers
200
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 ...
- 3
1
vote
1
answer
262
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(...
- 45
1
vote
1
answer
72
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
...
- 173
2
votes
1
answer
82
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 ...
- 173
1
vote
1
answer
116
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
42
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
263
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
3
votes
1
answer
140
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 ...
- 33
1
vote
1
answer
142
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
55
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,384
2
votes
2
answers
134
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 ...
- 414
6
votes
2
answers
114
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 ...
- 5,113
2
votes
2
answers
334
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
284
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
84
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
104
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.
- 438
3
votes
1
answer
447
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 ...
- 41
4
votes
1
answer
229
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
89
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
207
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,585
2
votes
2
answers
363
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
107
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,585
4
votes
1
answer
125
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.
...
- 149
1
vote
0
answers
87
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)?
- 431
4
votes
0
answers
137
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
123
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$ ...
- 1,235
3
votes
1
answer
628
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
91
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,585
5
votes
1
answer
239
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
110
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
113
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
283
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,585
2
votes
0
answers
60
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,585
6
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 ...
- 163
1
vote
2
answers
468
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