Questions tagged [garbled-circuits]

Garbled Circuits are used in Secure Multiparty Computation

Filter by
Sorted by
Tagged with
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 ...
user avatar
  • 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(...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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.
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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:...
user avatar
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 ...
user avatar
  • 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. ...
user avatar
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)?
user avatar
  • 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 ...
user avatar
  • 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$ ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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. ...
user avatar
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 ...
user avatar
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: "...
user avatar
  • 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?
user avatar
  • 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?
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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, ...
user avatar
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 ...
user avatar
  • 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'...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar