# 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 ...
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 ...
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: ...
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 ...
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 ...
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:...
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 ...
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 ...
1k views

### Practical implementations of Multiparty computations [closed]

Are there any practical implementations and or software platforms to prototype applications based on MPC ?
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 ...
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$ ...
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:...
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 ...
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 ...
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 ...
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: ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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}$ ...
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 ...
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. ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 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 ...
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). ...
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 ...
47 views

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?