Questions tagged [multiparty-computation]

Multi-party computation (MPC) allows a set of parties, each with a private input, to securely and jointly perform any computation over their inputs.

Filter by
Sorted by
Tagged with
20
votes
1answer
811 views

What are the roles of the simulator in simulation based proofs

I'm trying to better understand simulation based proofs in the UC model - but the guidelines to construct a simulator confuse me. To my understanding, the simulator is activated in two ways: Outbound:...
16
votes
3answers
2k views

Why can't the commitment schemes have both information theoretic hiding and binding properties?

The commitment schemes like Pedersen's or Hash based, either have information theoretic hiding and computational binding or computational hiding and information theoretic binding. So can we ever get ...
16
votes
1answer
842 views

Salary Negotiation Problem

Imagine Alice is applying for a new job. Alice has an idea of the minimum salary that she is willing to accept—let's call this value A. Bob, the hiring manager for ...
15
votes
4answers
6k views

Why is Shamir Secret Sharing not secure against active adversaries out-of-the-box?

This linear secret sharing scheme allows us to share a secret between n parties, such that only an honest majority can reconstruct it. I understand that – because I do not allow the user to certify ...
14
votes
2answers
2k views

Why use a 1-2 Oblivious Transfer instead of a 1 out of n Oblivious Transfer?

When initiating an oblivious transfer, why would someone use a 1-2 oblivious transfer rather than going for an 1 out of n oblivious transfer? Perhaps a slight time overhead for the extra message ...
12
votes
2answers
800 views

How can we distribute Shamir's secret sharing scheme shares without a dealer?

Let's say $k$ users have shares to a $(k,n)$ secret sharing scheme, and they want to issue new shares. How can they do this without collecting the shares together? In particular, no set of $k-1$ ...
11
votes
2answers
4k views

What does “circuits” mean in Cryptography?

I am not a hardcore cryptographer so this might be a really stupid question. I am looking through some papers in homomorphic encryption and discovered they describe computation as "circuits", why do ...
11
votes
2answers
1k views

Secure degree reduction for Shamir's secret sharing

I understand the basic Shamir Secret Sharing protocol, and when two shares are multiplied, the degree of the polynomial increases. I've seen in a number of papers a reference to a degree reduction ...
10
votes
2answers
1k views

Shared secret: Generating Random Permutation

-- or: How to Play Poker Without a Dealer I know this question is long but it's a really interesting theoretical problem about shared secrets and multi-party computation. General Problem: "Shared ...
9
votes
5answers
1k views

Is it possible to find the product of two numbers without knowing the two numbers?

I'm doing a thought experiment: Alice chooses a number $a$ and Bob $b$. They send $A(a)$ and $B(b)$ to Charlie. He performs $C(A(a), B(b))$ and gets $ab$. Do there exist not easily reversible ...
9
votes
3answers
2k views

Examples of protocols that are insecure when run concurrently

I was reading Canetti00 Universally Composable security paper. The first page of introduction says that there are some MPC protocols and Zero knowledge protocols that are insecure under concurrent ...
9
votes
2answers
3k views

Real world use cases of Multi-Party Computation

Most of the research papers give imaginary applications of multi-party computation. Either they talk about Yao's millionares' problem or two or more corporates willing to compute some intrustion ...
9
votes
1answer
289 views

Secure multiparty computation of conjunction

Suppose Alice and Bob each have bits a and b, respectively. How can Alice and Bob compute the function ...
9
votes
2answers
454 views

What math makes it safe to offer a stolen-password check service?

The database provider HIBP has 4 billion stolen passwords, and wishes to offer an API for websites to use during new-user signup (and password change) operations, so they can refuse to allow users to ...
8
votes
2answers
1k views

What is an example of a secure sigma proof?

I want to implement Threshold Elgamal as described in section 6.3.1 and in the decryption phase each party must broadcast a sigma proof to show that it actually has a valid secret share of the secret ...
8
votes
1answer
1k views

Single Party Encryption, Multi Party Decryption

I am looking for an adequate protocol for public key decryption, which would allow $n$ parties to jointly decrypt a cipher text. The usage scenario for such a protocol would be a mixnet that wouldn't ...
8
votes
1answer
167 views

Relaxing Semi-Honest Security in Multiparty Computation

I am currently reading Lindell's tutorial on simulation-based proofs and I am trying to understand the reasoning why the security notions are they way the are. In simple words, in the case of semi-...
8
votes
1answer
136 views

BGW Theorem 2- Does this proof work?

I was reading the original BGW paper. Great paper. I'm confused about Theorem 2, though. The Theorem states, "There are functions for which there are no n/2-private protocols." The proof is simply ...
8
votes
0answers
293 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 ...
7
votes
1answer
1k views

Simulation Based Proof: What Can / Can not Simulator Do?

I have seen some examples in "Foundation of cryptography" and "Efficient two party computation", in which simulator can do some things that in the real world model the parties cannot do, for instance: ...
7
votes
1answer
167 views

Secure function evaluation for Boolean formulae

Under the assumption that "secure" encryption exists, secure evaluation of functions represented by Boolean circuits is possible by Yao's garbling scheme [Y1]. My question is whether secure ...
7
votes
1answer
454 views

Extractability for Simulator in Malicious Model

It is sometimes required while proving the security of a protocol in the malicious setting that the simulator is able to extract the witness set of the adversary, who tends to be the prover of ...
7
votes
1answer
798 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 ...
7
votes
2answers
314 views

Algorithm for computing modular inverse in MPC

Is there any known algorithm for calculating $a^{-1} \pmod{q}$, where $ q < p$ and $F_{p}$ is the prime field of the MPC, in a linear secret sharing scheme ? I have tried using the standard ...
7
votes
3answers
194 views

How to determine the layers of a circuit?

In many cryptographic applications like Multiparty Computation (MPC) or Fully Homomorphic Encryption (FHE), you consider a function $f$ described by a circuit over some algebraic structure, typically ...
7
votes
1answer
132 views

Definition of secure computation with more that two parties

In Definition of secure computation in m-party case with respect to semi-honest adversary (Definition 7.5.1 in Foundations of Cryptography: Volume 2, Basic Applications by Oded Goldriech) we say ...
7
votes
1answer
159 views

Limitations of boolean and arithmetic circuits

Much of modern cryptography is based around working with boolean or arithmetic circuits. For example in Multi-Party Computation the 'famous' results allow for the secure computation of any function ...
6
votes
2answers
292 views

Efficiency of oblivious algorithms vs non-oblivious algorithms?

Recently, plenty of researchers are looking at designing efficient data-oblivious algorithms. Roughly speaking, an algorithm is said to be data-oblivious if its data access patterns are independednt ...
6
votes
2answers
1k views

Paillier Homomorphic encryption to calculate the means

Paillier Homomorphic encryption supports addition and multiplication with plaintext value. Can I use these properties to calculate the means of cipher-text values? I try to use the following steps: ...
6
votes
1answer
2k views

What are the ways to generate Beaver triples for multiplication gate?

So to speed up the function evaluation we use beaver trick, to generate raw data in the offline phase and use them in the online phase to get the output share for the multiplication gate. So what are ...
6
votes
2answers
281 views

Are any of the practical implementations of ORAM being used in a real world system?

The concept of Oblivious RAM (ORAM) was first introduced by Oded Goldreich and Rafail Ostrovsky in 1996. However, in the past 5-10 years there has been a surge in the amount of research that looks ...
6
votes
2answers
590 views

Motivation for the definition of statistical distance

Statistical distance is a widely used measure in cryptography for comparing two distributions. One can define various other measures for capturing the differences between two distributions, but why do ...
6
votes
1answer
789 views

Exact mathematical definition of simulation based security?

I've been trying to understand cryptographic protocols and how to define their security. The problem is that while I can understand what the intuitive definition says, I have trouble understanding how ...
6
votes
2answers
82 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 ...
6
votes
1answer
295 views

Background: Secret Sharing and Multiplication Triples

I know that a nearly identical question was asked in (Secret Sharing and Multiplication Triples), but I am a few points shy of asking follow up questions in the comments, so I understand if this is ...
6
votes
2answers
309 views

Hamiltonicity proof of knowledge

I'm learning the POK notion and definitions and as a self exercise I wante to prove the statement that the Hamiltonicity protocol is a POK system with knowledge error $1/2$. So the question will be ...
6
votes
1answer
461 views

Private set intersection, using a semi-trusted server

Alice has a set $S$ of words. Bob has a set $T$ of words. They want to compute the intersection $S \cap T$ of their words, with the help of a semi-trusted third party Trent. Trent runs a central ...
6
votes
1answer
216 views

Simulation-based proofs - advice tape of reduction algorithm

I am currently reading Yehuda Lindell's amazing tutorial on simulation proof technique and trying to write my own proof for the first time. In page 4 of this tutorial it is mentioned that [...] ...
6
votes
1answer
225 views

Designing Secure Multi-Party Computation Sub-Protocols Based on Homomorphic Encryption

When designing SMPC protocols using secret-sharing, it is a common approach to compose a protocol from several sub-protocols (each proven secure under the formal definition of security w.r.t. semi-...
6
votes
1answer
206 views

In coin flipping protocols, why aborting is allowed, and why the non-aborting party flips a coin at the end?

To convey how an adversary can bias the coin, most often a simple commitment-based two party coin-tossing protocol is given, as in [1]: Alice sends Bob the commitment $c = commit(x)$ Bob sends Alice ...
6
votes
1answer
126 views

Is a composition of clocked entities a clocked entity in the UC model?

In the book titled "Secure Multiparty Computation and Secret Sharing" the authors define an interactive agent and an interactive system. Further, the author defines a clocked entity for considering ...
6
votes
0answers
83 views

Distributed generation of random integers with prescribed sum

While reading this document I came across the following problem. Assume you have $n$ clients. The clients need to generate random integers in $\mathbb{Z}_p$, say $T_i$ for $i \in \{1, \ldots, n\}$, ...
5
votes
2answers
506 views

SPDZ for the 2-party case

There exist protocols for 2-party computation e.g., GMW that use Boolean circuits. I could also use Paillier and arithmetic circuits for a 2 party computation. However after reading about SPDZ is my ...
5
votes
2answers
4k views

The main differences between Sketch of Proof and Full proof

My question in general is: Question 1: What are the differences between sketch of proof and full proof? In simulation-based proof, in semi-honest model, we construct a view that is computationally ...
5
votes
3answers
3k views

homomorphic encryption special case of multi party computation?

I read that Fully Homomorphic Encryption schemes are special case of Secure MPC in page no 3. Especially , generalization of two party computation problems stated by Yao But is there any additional ...
5
votes
1answer
599 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 ...
5
votes
2answers
213 views

MPC protocols for high school kids

I was explaining MPC to a high school student. He was excited and asked me for some examples. The only ones that I could think of are by using garbled circuits. Are there some simple MPC protocols for ...
5
votes
1answer
2k views

SPDZ protocol: how expensive is it to generate the multiplicative triples?

I am currently reading the full version of the SPDZ protocol. I understand that the online phase does multiplication with computational and communication complexity $O(n)$ by using Beaver's ...
5
votes
1answer
836 views

What kind of multiparty computation is this?

The classic multiparty computation protocols are defined around " Untrusted parties trying to compute something together". But is there a cryptographic abstraction for, "Trusted parties trying to ...
5
votes
1answer
138 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 ...

1
2 3 4 5
7