Skip to main content

Questions tagged [garbled-circuits]

Garbled Circuits are used in Secure Multiparty Computation

Filter by
Sorted by
Tagged with
1 vote
0 answers
36 views

Understanding Half-Gates for Garbled Circuits

Currently I am reading though Two Halves Make a Whole and understand the basics of generator half-gate and evaluator half-gate. The generator half-gate can be used when the garbler knows the input to ...
CLox's user avatar
  • 151
0 votes
0 answers
23 views

Masking Bits in n-party Garbled Circuit

Let us consider the scenario where there are n-1 garblers and a single evaluator. The garblers together need to generate a garbled circuit. We use a distributed garbling protocol such as [BLO16] and ...
Crypto_researcher's user avatar
1 vote
1 answer
53 views

n-Party Garbled Circuit

Yao introduced a famous notion of securely computing any function between 2 users using a concept of Garbling circuit. How can this idea be extended for n-party case? That is there are n-1 garblers ...
Crypto_researcher's user avatar
1 vote
1 answer
112 views

Is it secure for A to allow B to run a garbled circuit twice with different inputs? [duplicate]

I was reviewing past exam questions and came across this one: Is it secure for A (the garbler) to allow B (the evaluator) to run a garbled circuit twice with different inputs? They aim to compute the ...
user1's user avatar
  • 35
2 votes
1 answer
70 views

Choosing $C_0$ to make second row zero for Garbled Row Reduction (GRR3)

In GRR3,we make the first row of the Garbled table to be zero by choosing a special value of $C_1$. Why don't we make the second row also zero by choosing a special value of $C_0$?
asasdasdsa's user avatar
3 votes
1 answer
259 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
70 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
40 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
28 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
67 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
  • 43
1 vote
0 answers
58 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
165 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
  • 112
4 votes
1 answer
176 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
156 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
282 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
64 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
48 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
125 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
140 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
  • 962
1 vote
0 answers
109 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
257 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
502 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
109 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
  • 361
2 votes
1 answer
92 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
  • 361
1 vote
1 answer
126 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
51 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
369 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
178 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
222 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
72 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,414
2 votes
2 answers
165 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
  • 424
6 votes
2 answers
121 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,378
2 votes
2 answers
436 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
367 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
102 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
112 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
518 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
264 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
100 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
236 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,645
2 votes
2 answers
379 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
119 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,645
4 votes
1 answer
127 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
92 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
  • 441
4 votes
0 answers
141 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
125 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
4 votes
1 answer
785 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
92 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,645
5 votes
1 answer
251 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
122 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