Questions tagged [garbled-circuits]

Garbled Circuits are used in Secure Multiparty Computation

Filter by
Sorted by
Tagged with
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 ...
alexander's user avatar
  • 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 ...
Mahdi Mahdavi's user avatar
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 ...
Mahdi Mahdavi's user avatar
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).
user110027's user avatar
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 ...
Al A's user avatar
  • 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 ...
Paritosh007's user avatar
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 ...
Emison Lu's user avatar
  • 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 ...
Lt. Commander. Data's user avatar
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 ...
taserghar's user avatar
  • 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 ...
Mumon's user avatar
  • 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 ...
sinu's user avatar
  • 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 ...
alexander's user avatar
  • 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 ...
HATİCE MELİSA ERYILMAZ's user avatar
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$ ...
tur11ng's user avatar
  • 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 ...
Shuangyi Chen's user avatar
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 ...
nnsk's user avatar
  • 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(...
louis5544's user avatar
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 ...
js wang's user avatar
  • 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 ...
js wang's user avatar
  • 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 ...
walter7x's user avatar
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 ...
walter7x's user avatar
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 ...
walter7x's user avatar
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 ...
YGrade's user avatar
  • 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 ...
rzxh's user avatar
  • 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 ...
satya's user avatar
  • 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 ...
X. G.'s user avatar
  • 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 ...
ckamath's user avatar
  • 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 ...
ct2048's user avatar
  • 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 ...
QuestionEverything's user avatar
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 ...
John's user avatar
  • 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.
fraiser's user avatar
  • 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 ...
Wang Linger's user avatar
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 ...
andy's user avatar
  • 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 ...
David Ma's user avatar
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 ...
mallea's user avatar
  • 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:...
user3132457's user avatar
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 ...
mallea's user avatar
  • 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. ...
alexander's user avatar
  • 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)?
savx2's user avatar
  • 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 ...
Mayank's user avatar
  • 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$ ...
Joseph Van Name's user avatar
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 ...
ellio0ott's user avatar
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 ...
mallea's user avatar
  • 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. ...
michaelsnowden's user avatar
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 ...
Username Unknown's user avatar
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: "...
user79126's user avatar
  • 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?
mallea's user avatar
  • 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?
mallea's user avatar
  • 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 ...
Spock's user avatar
  • 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 ...
Ragnar's user avatar
  • 11