# 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.

45 questions
Filter by
Sorted by
Tagged with
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 ...
• 133
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 ...
• 153
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: ...
• 63
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 ...
• 181
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 ...
• 5,944
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:...
• 201
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 ...
• 407
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 ...
• 1,274
1k views

### Practical implementations of Multiparty computations [closed]

Are there any practical implementations and or software platforms to prototype applications based on MPC ?
• 5,944
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 ...
• 271
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$ ...
• 799
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:...
• 885
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 ...
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 ...
• 613
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 ...
• 165
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 ...
• 581
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: ...
• 775
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 ...
• 775
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 ...
• 49
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 ...
• 199
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 ...
• 2,010
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 ...
• 5,944
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 ...
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 ...
• 271
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 ...
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}$ ...
• 271
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 ...
• 35.3k
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. ...
• 439
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 ...
• 325
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 ...
• 10.2k
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 ...
• 415
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 ...
• 613
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 ...
• 1,495
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 ...
• 3,697
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 ...
• 21
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 ...
• 1,533
1 vote
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 ...
• 540
1 vote
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). ...
• 199
1 vote
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 ...
1 vote
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 ...
• 523
47 views

• 59
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?
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-...
• 1,495