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
11 votes
2 answers
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 ...
user avatar
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
6 votes
2 answers
2k 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: ...
user avatar
  • 63
3 votes
2 answers
326 views

Algorithm Design for only Mutual Information Sharing

Bob and Alice each have a bit string they want to keep private. They each want to know what the bitwise AND of their two strings would be without telling the other or anyone else listening to their ...
user avatar
9 votes
2 answers
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 ...
user avatar
  • 5,944
20 votes
1 answer
971 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:...
user avatar
  • 201
12 votes
2 answers
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 ...
user avatar
  • 407
9 votes
3 answers
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 ...
user avatar
  • 1,274
4 votes
2 answers
1k views

Practical implementations of Multiparty computations [closed]

Are there any practical implementations and or software platforms to prototype applications based on MPC ?
user avatar
  • 5,944
2 votes
1 answer
141 views

Can anybody explain the proof of Rabin and Ben-or of secure multiparty computation?

Can anybody explain the proof of Rabin and Ben-or of secure multiparty computation? The idea is that every player $i$, of $N<+\infty$ players, holds a secret say $s_i$. All of them want to share ...
user avatar
12 votes
2 answers
913 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$ ...
user avatar
  • 799
5 votes
1 answer
953 views

Why can't garbled circuits be reused?

There are a bunch of papers do research on resizable garbled circuits. But I wonder why garbled circuits cannot be reused? For example, the constructor constructs a garbled circuit of "AND" like this:...
user avatar
  • 885
2 votes
1 answer
245 views

BGW Multiplication: How does it work?

I could not understand how multiplication is carried out in the BGW protocol for 3 parties. Reference: https://crypto.stanford.edu/pbc/notes/crypto/bgw.html I've understood that in multiplication, we ...
user avatar
2 votes
2 answers
914 views

SPDZ- How to do secure equality comparison

The SPDZ paper explains how the SPDZ protocol can be used to find the sum/product of secret values and find the sum/product of a secret and a non-secret value (page 6). The paper seems to say that ...
user avatar
2 votes
1 answer
536 views

Secure multi-party computation for digital signature

Is there any practical algorithm that will allow to use public key cryptography (RSA or ECC) in the following way There are N parties. Up to M are malicious adversaries (were trusted, but got taken ...
user avatar
  • 165
2 votes
1 answer
141 views

How can Alice enable Bob to look-up values in a private map

I think this problem is similar to private set intersection, yet distinct in a way where: Alice has an extensive Mapping of say id to name id1 -> John Doe id2 -> Jane Doe id3 -> Edgar Poe ...
user avatar
  • 581
7 votes
1 answer
2k 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: ...
user avatar
  • 775
4 votes
2 answers
3k views

Simulation based proofs: Simple examples

I am aware that,(in theory) in order to proof that a scheme is secure using simulation based proof we replace an adversary in real world with a simulator in ideal world. Then we try to show that their ...
user avatar
  • 775
4 votes
2 answers
665 views

Real life systems that use concepts of crypto computing [closed]

Are there any working cloud/internet solutions/products that operates on encrypted data such as systems using homomorphic encryption, secure multiparty computation, electronic voting, private ...
user avatar
  • 49
9 votes
1 answer
351 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 ...
user avatar
  • 199
6 votes
2 answers
327 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 ...
user avatar
  • 2,010
6 votes
2 answers
277 views

How many polynomials are used in Secure Multiparty Computation?

Secure Multiparty Computation based on Samir Secret sharing methods rely on Polynomials. Imagine corpus of data should be outsourced to bunch of untrusted servers for any computations. Now the data ...
user avatar
  • 5,944
4 votes
1 answer
1k views

Addition with Shamir secret sharing?

When performing Shamir secret sharing I'm trying to find $z_i$, such that $z = x + y$. Where $n = 6$ and $t = 3$. I believe this would be the correct solution (correct me if I'm wrong): Each party ...
user avatar
2 votes
0 answers
80 views

Secure multiparty scheme in key (splitting) distribution among the players

Suppose that we have a game with $I$ players and each of them has a private secret say $e_i$. Every player wants to share her secret with the rest of the players but in such a way that she will not be ...
user avatar
2 votes
2 answers
290 views

Statistical security parameter -> information theoretically secure

If a cryptographic protocol has a computational security parameter and a statistical security parameter, does this mean it is only computationally secure instead of information-theoretically secure? I ...
user avatar
0 votes
2 answers
104 views

How can I use a secret sharing scheme when the secret is not a number but a statement?

I want to use a secret sharing scheme, where every player $i\in N$ has to share a pair of secrets $(l_i,\nu_{l_i})$, where $l_i$ is a unique code (positive integer) for every player, but $\nu_{l_i}$ ...
user avatar
6 votes
1 answer
548 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 ...
user avatar
  • 35.3k
4 votes
1 answer
123 views

How do you distribute secret shares without knowing who to first distribute them to?

Figure 1 on page 1249 of the “Multiparty Computation Secure Against Continual Memory Leakage” paper shows $m$ committees are elected in step 1 and then later in step 3 are each given a secret share. ...
user avatar
3 votes
1 answer
367 views

Shamir secret sharing with two types of parties

Consider the Shamir Secret Sharing scheme based on polynomial interpolation. In this scheme, every part has the same right: one piece of information of same value as the other ones. The idea is to ...
user avatar
  • 325
8 votes
1 answer
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 ...
user avatar
6 votes
1 answer
330 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 ...
user avatar
  • 415
5 votes
2 answers
657 views

Yao's Garbled Circuit- Why does Alice need to rearrange the circuit?

My understanding of Yao's Garbled Circuit (based mostly on this summary) is as follows: Alice creates a garbled circuit based on the function f to be computed. She then hard-codes her input into the ...
user avatar
4 votes
1 answer
144 views

Security of secure two-party computation with a trusted dealer during offline phase?

In the SecureML paper, one can assume that two non-colluding servers can run secure two-party computation protocol based on secret sharing with the help of a third party (client). The client would ...
user avatar
  • 1,495
3 votes
1 answer
217 views

MPC protocols in plain/CRS/PKI models

I have seen that in MPC multiple models in different dimensions can be envisioned, like asynchronous vs synchronous networks, access to broadcast channels, and so on. However, a particularly ...
user avatar
  • 3,697
2 votes
0 answers
54 views

For unequal set sizes in PSI: why should the party with fewer elements use cuckoo hash rather than simple hash?

Most PSI papers usually use hash-to-bin to improve the number of comparsons. For unequal set sizes in 2PSI, I have read CCS17, which designs a PSI protocol for unequal size. The party with fewer ...
user avatar
  • 21
2 votes
2 answers
453 views

Collision-resistant Pseudorandom function

Assume we have a pseudorandom function: PRF(.) We want the following property holds with a high probability: $\forall i, 0\leq i \leq n: PRF(k_1, i)\neq PRF(k_2,i)$ where $k_1$ and $k_2$ are two ...
user avatar
  • 1,533
1 vote
1 answer
101 views

Optimal threshold for passive and perfect security

The authors of the book titled "Secure Multiparty Computation and Secret Sharing" claim that there exist functions which cannot be computed with passive perfect security for $t \geq n/2$ corrupt ...
user avatar
  • 540
1 vote
0 answers
30 views

Information-theoretically secure computation of a conjunction (with a semi-honest third party)

Suppose Alice and Bob want to compute the conjunction of their private bits in an information-theoretically secure way (so this approach, which uses standard oblivious transfer, does not suffice). ...
user avatar
  • 199
1 vote
1 answer
519 views

Simulation based proofs, what am I missing?

In the example given by in the top answer of Simulation based proofs: Simple examples claims that this is insecure the semi-honest, and I need assistance in where I am failing to reason why that this ...
user avatar
1 vote
1 answer
724 views

AES encryption using MPC SPDZ protocol

I'm reading the article about SPDZ protocol for secure multiparty computation (and also improvements for offline phase like MASCOT). However I'm thinking about practical application of SPDZ for AES ...
user avatar
0 votes
0 answers
47 views

Secure multi-party computation made simple - questions

The scheme that I refer to is from this paper. A secret $s\in D$ is obtained by splitting s into a random sum. We have (actually linear) for any $k$ this $k$-out-of-$k$ secret-sharing scheme: Select $...
user avatar
0 votes
0 answers
123 views

What type of encryption scheme can prevent cheating in this coin flip protocol? [duplicate]

Consider the following protocol for two parties to flip a fair coin: Trusted party $T$ publishes her public key $p_k$ A chooses a random bit $b_A$, encrypts it under $p_k$, and announces the ...
user avatar
  • 59
0 votes
1 answer
144 views

Is there a system where multiple people can encrypt a message and then decrypt it in any order? [duplicate]

For example, A encrypts a message. B encrypts that. C encrypts that. Then B decrypts, followed by A then C. Are there systems that allow this? Does such a property have a name?
user avatar
0 votes
1 answer
159 views

What (Where) is the formal definition of Multiparty Computation? [closed]

I'm just curious where we can see a (original) formal definition of MPC. What (Where) is the formal definition of MPC? We have a bunch of tools to build a MPC protocol. Is oblivious transfer (or OT-...
user avatar
  • 1,495
0 votes
1 answer
132 views

Question on proof of coin-tossing in "how to simulate it"

I am reading Professor Lindell's "How To Simulate It - A Tutorial on the Simulation Proof Technique" paper, which is very enlightening. I am trying to follow through the proof of the security of Blum'...
user avatar
  • 101