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

learn more… | top users | synonyms (3)

17
votes
1answer
147 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: ...
12
votes
2answers
594 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 ...
10
votes
1answer
459 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 ...
6
votes
2answers
436 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 ...
6
votes
2answers
846 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 ...
6
votes
2answers
244 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 ...
6
votes
1answer
396 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 ...
6
votes
2answers
196 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 ...
5
votes
1answer
531 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
443 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 ...
5
votes
1answer
53 views

Is it possible for a simulator to always abort?

In this paper of J. Baron, et al. (PDF), simulator always aborts the ideal functionality before client outputs its pattern-matching result obtained from the ideal functionality. (See bottom of page ...
5
votes
1answer
70 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. ...
5
votes
1answer
117 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 ...
5
votes
2answers
76 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 ...
4
votes
1answer
190 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 ...
4
votes
1answer
69 views

Oblivious Transfer where neither party learns the index of the message

In a traditional Oblivious Transfer setting, the sender has a list $(x_1, x_2, ... , x_n) \in G$ where $G$ is the chosen group. The receiver has $b \in \mathbb{N}$, such that engaging in the protocol ...
4
votes
0answers
30 views

An MPC protocol from Elgamal is a good solution a homomorphic multiplication?

I want to compute a multiplication between many secret values and then distribute the result to everyone involved. For this, I thought about an MPC protocol built from Threshold Homomorphic Elgamal. ...
4
votes
0answers
55 views

How can I implement decryption for NTRU homomorphic encryption scheme?

I have come across this paper On-the-fly multiparty computation via on-the-cloud Multikey from Fully Homomorphic Encryption by Lopez-Alt et al., where authors describe a NTRU-based homomorphic ...
4
votes
0answers
51 views

How about a homomorphic integer sorting in a MPC context?

I want to implement the ATV-FHE scheme as described by Adriana López-Alt, Eran Tromer, Vinod Vaikuntanathan: On-the-Fly Multiparty Computation on the Cloud via Multikey Fully Homomorphic Encryption ...
3
votes
1answer
114 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 ...
3
votes
2answers
93 views

Why do the outputs of parties in an MPC protocol have to be indistinguishable from the ideal / real world (as opposed to inputs)?

In this paper at the bottom of pg. 1235 and beginning of pg. 1236 it says: An MPC protocol is said to be secure, if for every real world leakage adversary A there exists an ideal world ...
3
votes
1answer
77 views

What is the difference between “securely realizes” and “securely implements”?

In some security proofs it is stated that "a protocol securely realizes an ideal functionality" while in some others "a protocol securely implements an ideal functionality". Is there a meaningful ...
3
votes
2answers
268 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 ...
3
votes
1answer
130 views

Where can I find source code for ideal world simulation?

In many crypto papers I see they use a Real World / Ideal World Paradigm. However, I have never see the source code of such Simulators that try to simulate the adversary. Could somebody point me to ...
3
votes
1answer
296 views

What's efficient MPC protocol for determining if sum's bigger than y?

My secure multi-party computation (MPC) in need is simply to determine if a sum of two private variable is bigger than a given value $y$, as $f(x_0, x_1) = [(x_0 + x_1) > y]$ in which the value ...
3
votes
1answer
52 views

Multi-Party Encryption for a Shared Document

Is there an encryption algorithm/protocol where any of a pre-defined set of keys/passwords will succeed in decrypting a document? The number of keys can be fixed, say, 10 or 20 possible passwords. ...
3
votes
2answers
263 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 ...
3
votes
2answers
263 views

secure integer comparison

I have been going through a huge amount of papers to find a simple and a practical method to compare integer numbers without revealing their original values. I know that this falls within the area of ...
3
votes
1answer
356 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 ...
3
votes
2answers
433 views

secure multiparty computation for multiplication

Suppose there are $N$ parties $p_j$, each with a binary $b_j\in{\{0,1\}}$. The problem needs to compute the multiplication of number of ones times that of zeros, that is, ...
3
votes
1answer
59 views

Forcing participants to be honest in Secure Multiparty Communication

Alice and Bob engage to compute a secure function f(a,b) where a and b must be present in a ...
3
votes
1answer
462 views

Can I use Shamir's secret sharing scheme for multiplicative homomorphism for secure multiparty computation?

I would like to perform a dot product operation among $m$ parties using Shamir's $(m,m)$ secret sharing that is used for Secure Multiparty Computation. I am aware that Shamir's $(m,m)$ scheme is ...
3
votes
2answers
86 views

Group membership with unique anonymous claims

Is it possible to accomplish the following scheme? There is a Server (S) and many clients. Each client enrolls with S, exposing its real identity; S saves the real identity information in its ...
3
votes
0answers
79 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. ...
3
votes
0answers
58 views

Can you clarify the proof that secure LR-two party protocols do not exist?

In the paper “Multiparty Computation Secure Against Continual Memory Leakage” on pg. 1237, the footnote #1 discuss why it is not possible to construct a leakage resilient two-party protocol. But I'm ...
2
votes
2answers
150 views

What if OT breaks in Yao's garbled circuit?

Two semi-honest parties are computing F with Yao's garbled circuit. Sender garbles it with his inputs baked in then sends it to the receiver. At this point the receiver must use OT to get his keys. ...
2
votes
3answers
351 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 ...
2
votes
2answers
70 views

Are covert and rational adversaries same?

Aumann and Lindell defined covert adversaries in 2009 which is informally adversaries which have a epsilon-deterrence to cheat. Some authors (for ex. John R. Wallrabenstein) have defined similar ...
2
votes
2answers
72 views

regular expression matching on encrypted data using secure multiparty computation

Lets consider Secure Multiparty Computation based on Secret Sharing schemes (rather than Garbled Circuits approach). If we have to do regular expression matching on secret shares of words of texts. ...
2
votes
2answers
40 views

Correctness of ideal protocol of MPC in presence of malicious adversary

In presence of malicious adversaries in ideal protocol of Multi Party Computation, how can honest parties get the correct output? i.e., corrupted parties modify their inputs and give to the trusted ...
2
votes
1answer
142 views

What's the differences among Blind Computation, Secure Multi-Party Computation, Secure Circuit Evaluation and Homomorphic Encryption

We know that Blind Computation, Secure Multi-Party Computation, Secure Circuit Evaluation and Homomorphic Encryption all can process the encrypted data, but I am puzzled by them. What are their ...
2
votes
1answer
123 views

Computing youngest person among 3 while keeping ages private

I already found a protocol to find out who is richer (older) between two parties, but Is there any protocol to find the youngest person among 3 parties, without revealing actual ages?
2
votes
1answer
132 views

What is adaptive zero-knowledge?

In this paper on pg. 1241 the authors discuss bullet point on Adaptive Zero-Knowledge : I am new to Zero-Knowledge and I am having trouble understanding what they are saying. I think they are ...
2
votes
2answers
256 views

Practical implementations of Multiparty computations [closed]

Are there any practical implementations and or software platforms to prototype applications based on MPC ?
2
votes
1answer
34 views

Leakage in Secure Two party Computation

Am trying to understand Garbled Circuit based approach for Secure Two party Computation. There isn't much leakage in the classic millionaire's problem where the comparison circuit is used. But ...
2
votes
1answer
199 views

Shamir Secret Sharing Modular Reduction

Say players use Shamir's secret sharing to share a value $k$ such that each player now holds $k_i$, a share of $k$. How can they securely compute $k \bmod m$ for some $m$. Of course they can ...
2
votes
1answer
163 views

What does this step in this protocol for the Yao's Millionaire Problem mean?

I was reading “An Efficient Protocol for Yao’s Millionaires’ Problem” (Ioannidis and Grama 2003). In the proposed protocol in section three, it is written: (Step 4) For every $i$, $1 \le i \le d$, ...
2
votes
2answers
91 views

How to get the same calculation result on an untrusted computer, while withholding some information?

Consider this command on a trusted computer: result = function(public data, secret data) or shorter: r = f(p,s). How could a ...
2
votes
1answer
59 views

Equivalents to a physical hat+shaking?

I would like a multiparty protocol, secure in the honest-but-curious model at least, but hopefully other situations as well, that can do the following: every party among $\{P_1, P_2, \ldots P_n\}$ ...
2
votes
2answers
596 views

Is there an effective way for public key generation in homomorphic encryption schemes?

Is there any way to effectively generate valid distributed public key in schemes like ElGamal or Benaloh for a number of participants? There's no need in private keys since there's no intent to ...