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
6
votes
1answer
63 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 ...
1
vote
1answer
47 views

Securely computing functions over source code

I have been studying multi-party computation and want to start implementing it. I think it would be interesting to do this where one of the inputs (say party 1) is some source code, say a .py file. ...
0
votes
0answers
18 views

Secure Computation with TTP using Ring-LWE Homomorphic Encryption

I was working with secure outsourced computation for multi-party computation in which security is assured by ring-LWE based asymmetric homomorphic encryption in the semi-honest model. Is it feasible ...
1
vote
1answer
46 views

How can one prove correctness of shared secrets in secret sharing schemes?

Assume we are in a centralized secret sharing setting, where one party generates the shares, and distributes them to other parties. How can the distributor who creates the shares prove to the parties ...
0
votes
0answers
24 views

Commitment HIDING ⇒ Real≈Ideal in Multiple Coin Tossing Security

I'm reading /Multiple_Coin_Tossing_Security/P2_Corrupted/ ("Information Security and Cryptography" Theorem 6.7.4 starting from page 325) and after description of Simulator for P2, the author continues ...
2
votes
1answer
58 views

MPC and Secret Sharing in not Fully-Connected Network

I have an interest in applications of MPC and Secret Sharing. My point of view is from fields of distributed computing and Game Theory. I want to generalize some results to arbitrary network ...
8
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 ...
1
vote
1answer
43 views

Why do we use addition and multiplication in GMW protocol

So i'm reading about secure computation and the GMW protocol. I don't understand why the protocol evaluates the addition and the multiplication ? Why not just the multiplication ? I didn't find any ...
1
vote
1answer
26 views

OT extensions paper: Why is $G_{m+1} \nleq m \times AND_B$?

I am reading this paper, in which Beaver shows how to take a small number of Oblivious Transfers (OTs) and extend them into an arbitrary number of OTs by implementing a pseudo-random number generator ...
1
vote
0answers
23 views

Question about the BCP cryptosystem

Is it possible to have a multiparty untrusted generation of the public parameters for the BCP cryptosystem (https://www.iacr.org/archive/asiacrypt2003/01_Session01/03_106/28940037.pdf), so that a ...
0
votes
0answers
74 views

Split TOTP/HOTP secret and generate pin without trusted dealer

Many site use time-based one time password (totp) as second factor auth method, such as aws. So we can split the totp secret and distribute each part to different party to achieve threshold login ( ...
-1
votes
1answer
40 views

Ensuring correctness property in multi-party protocols

Can you suggest mechanisms to ensure the correctness of the protocol output, against Active Adversaries in multi-party protocols. Specifically for a dishonest majority setting? I would like to have ...
4
votes
2answers
140 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 ...
2
votes
1answer
70 views

Is it possible to represent max{a,b} as a binary polynomial?

For privacy-preserving comparison, is it possible to represent the function of $f(a,b)=\max\{a,b\}$ as a binary polynomial $p(a,b)$?
0
votes
0answers
49 views

Decentralized / Distributed Private Key Generation between Untrusted Parties?

I found an interesting concept in this paper, page 13, (Link to the paper) called "Decentralized private key generation", as follows: "Decentralized private key generation – Multiple Enigma nodes ...
1
vote
1answer
249 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 ...
3
votes
1answer
85 views

Where can I find open source code for Encryption Switching Protocol?

The concept of Encryption Switching Protocols was introduced in CRYPTO. I was wondering if there is any pseudo-implementation of the protocol available or can I get some insights on how to implement ...
0
votes
1answer
68 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'...
0
votes
1answer
78 views

How to do division using Beaver Multiplication Triples

It is very straight-forward and intuitively to achieve addition, subtraction and even generalized polynomial using Beaver's Multiplication Triples. However division seems difficult to achieve on two ...
0
votes
0answers
49 views

Blinding factor SEAL

For a protocol, I need to blind a ciphertext. I am not sure how to choose the blinding factor. How should I choose the range? What should I consider to offer security? I am using CKKS scheme, the one ...
1
vote
1answer
58 views

Proving security for Secure Multiparty Computation with malicious adversaries

In the case of malicious adversaries, while creating a simulator for an attacker in the real world what are the algorithms that this simulator has access to and why? For eg. I've seen simulators that ...
2
votes
0answers
21 views

Strategies for fast integrity attestation over multi party computation for large messages

I am looking for ways to efficiently perform integrity attestation over large messages using multi party computation. While, hashing (SHA1, 256...) is one alternative but it's painfully slow and grows ...
2
votes
1answer
70 views

Secure multi-party random number generation

This question is actually continuation of my previous one. Secure multi-party computation for digital signature to implement solution there, I have to generate random data for padding (I will use ...
2
votes
1answer
109 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 ...
1
vote
0answers
68 views

Purpose of the ZKPoPK in the original SPDZ protocol

What is the purpose of ZKPoPK in the SPDZ paper? And will the following can detect the active adversaries in 2 party spdz excluding ZKPoPK step? Each party sends a commitment on his MAC key ∆_i ...
1
vote
1answer
43 views

Is computing majority element while doing secure two party computation for inner products ( input of the two parties ) an attack on the protocol?

This was told to be an attack. However, we can create a simulator in the ideal world which sends all 1s to the trusted party and receives the number of ones of the honest party. Is this simulation ...
0
votes
1answer
76 views

Two parties SPDZ Protocol Input sharing

Assume we have two computing parties for SPDZ protocol. The two parties are also the input parties. How can they share the MACs on their input shares assuming one party is the master who owns the MAC ...
0
votes
0answers
25 views

Time-locked deposit protocol?

I am designing a protocol where a user A sends a time-locked deposit to user that if the user B within time t provide a proof that he exists in a location x (this may be obtained by third party like ...
3
votes
1answer
68 views

BGV KeyGen— Can a maliciously-generated secret-shared key break security (e.g. SPDZ)?

I was (re)reading the paper "Practical Covertly Secure MPC for Dishonest Majority–or: Breaking the SPDZ Limits". One of the key points in this paper is that they present a covertly secure BGV key ...
3
votes
1answer
154 views

Security of Fast Two-Party ECDSA Signing

The paper "Fast Secure Two-Party ECDSA Signing" by Yehuda Lindell describes a system in which two parties, $P_1$ (with 1/2 of a share of a long-term ECDSA signing key $x_1$) and $P_2$ (with the other ...
0
votes
1answer
53 views

Oblivious transfer with trusted third party Trent

I am trying to solve this exercise. Assume an oblivious transfer protocol that uses a trusted third party Trent. Alice's messages $M_0$ and $M_1$ are binary values of length $k$. Bob's message ...
2
votes
3answers
108 views

Algorithm for binary less than in MPC

Given binary shares $[a_{l-1}]_p,...,[a_0]_p, [b_{l-1}]_p,...,[b_0]_p$ such that $a = \sum_{i=0}^{l-1} a_i2^i,b = \sum_{i=0}^{l-1} b_i2^i $ for $a,b \in Z_p$, how to compute $a \overset{?}{\lt} b$ in ...
1
vote
1answer
128 views

Interactive Homomorphic Encryption

Let's say that I have a plain computational process that consists of several divisions and I do not want to do it with non-interactive homomorphic encryption. I would like to ask how can I call this ...
2
votes
1answer
102 views

Blind Computation

Let's say that there are two parties. Party $A$ has ciphertexts $c_1, c_2$ encrypting data $m_1,m_2$ respectively. $A$ does not know the secret key to decrypt $c_1, c_2$. Party $B$ has the secret key. ...
6
votes
2answers
171 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 ...
6
votes
0answers
74 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\}$, ...
0
votes
2answers
266 views

Difference between Zero Knowledge Proofs and Multi Party Computation

I am struggling with understanding the difference between the two. From what I am putting together, they have different adversarial models, MPC adds the condition of collusion between parties i.e. ...
0
votes
1answer
84 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-...
4
votes
1answer
72 views

Under what conditions is broadcast possible? (Cryptographically, and in the model of Maurer 2006)

In this paper, Ueli Maurer uses a very cool model to generalize a number of results about broadcast, secret sharing and secure multiparty computation. Rather than talking about an adversary being ...
1
vote
2answers
92 views

Multi-secret sharing (Packed secret sharing) - Some questions

In the publication - "Communication complexity of secure computation", I have encountered a small problem - on page 5 of the literature under the heading "Theorem 1" they have described a $(c,d; k,n)$ ...
1
vote
1answer
106 views

Is the simulation-based proof difficult and needed? [closed]

What is the role for simulation-based proof under the semi-honest model without considering malicious adversaries? I agree with that a view of a some party is important to prove that a protocol is ...
0
votes
1answer
85 views

MPC on boolean circuits

I am reading about Yao's and GMW protocols and was wondering if there is any perfectly secure MPC protocol in the semi-honest setting, where the underlying circuit is a Boolean circuit (eg. n=3 and t=...
2
votes
1answer
61 views

Commitment in two party protocols

I have been reading Fast Secure Two-Party ECDSA Signing by Lindell, and I see that in key generating and signing (pages 9-10, especially visible from Figure 1), only the first party performs a ...
3
votes
1answer
91 views

Testing whether a secret value is zero without security bits (in SPDZ)

To test whether a secret value $[x]$ is zero, where $x \in [0,2^{k−1}]$, SPDZ uses the a based on the method of Catrina and de Hoogh [1]. This method requires to working on a field with modulus $p>...
0
votes
2answers
191 views

How to compute secure sum using secure multparty computation?

Suppose there are three voters $P$, $Q$ and $R$, and each will vote only on one candidate out of $X$, $Y$ or $Z$, with a 6 bit vote vector corresponding to $X $, $Y$ and $Z$ respectively (with 2 bits ...
7
votes
3answers
150 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 ...
1
vote
1answer
49 views

In Multi-party communication, how can I find that one encrypted value is negative or not?

I'm using Pailier Cryptosystem as an additive homomorphic system in my scenario. I have two parties: Alice and Bob. Alice has one pair of (SK, Pk) keys. She encryptes one value using her public key ...
2
votes
1answer
81 views

computing INV in boolean circuit for MPC

Is it feasible to generate an efficient MPC function that compute $a^{-1}$ for $a \in \mathbb{F_q}$, with Boolean circuit? The naive way seems impossible since the depth of the computation might ...
2
votes
1answer
52 views

What is shared-input for Multi Party Computation?

I heard shared input. For example, original values $x,y \in M$ are divided into pairs of shares $(x_1,x_2)$ and $(y_1, y_2)$ such that $x_1 + x_2 = x \text{ and } y_1 + y_2 = y$. Each share is ...
1
vote
0answers
170 views

Multi-Party Offline Key Exchange Using Public and Private Keys

I hope the title already explains the problem I have in mind; but let me lay out some more details. Given public-private key pairs $P_A, P_B, P_C, ... P_Z$, (first $3$ of which are owned by our usual ...