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
3
votes
1answer
130 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
287 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
107 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
150 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
151 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
148 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. ...
7
votes
2answers
301 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
83 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
663 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
115 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
86 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
310 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 ...
1
vote
1answer
193 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 ...
1
vote
1answer
135 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
77 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
105 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
394 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
191 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
57 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 ...
3
votes
1answer
103 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
66 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
264 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 ...
2
votes
1answer
57 views

complete functionality for fair multiparty computation

In this paper I found the statement "We reduce the fairness problem in MPC to the problem of fair decryption [...] Fair decryption was shown to be a complete functionality for fair MPC in [GIM+10]". ...
1
vote
1answer
87 views

Check if $a<b$ in a trustless scenario

Let's say Alice has access only to a value $a$ and Bob has access to both $a$ and $b$. I need ...
1
vote
0answers
83 views

Threshold Bitcoin signature scheme

Any advice would be appreciated: It seems to me that using an uncomplicated combination of a shamir scheme and schnorr it's fairly trivial to have a threshold signature scheme. I think it's also ...
3
votes
2answers
278 views

How to use Homomorphic encryption for secure computing Arctan() function?

In the multi-party communication(MPC), if partyA has the coordinate(x1 y1) and partyB has the coordiante(x2,y2), how two parties can securely compute Arctan((y1-y2)/(x1-x2)) without revealing their ...
4
votes
2answers
173 views

Atomic multi-party commitments

Alice and Bob publicly choose the messages $M_A$ and $M_B$ and independently sign them (Alice privately signs $M_A$, Bob signs $M_B$). Now Alice and Bob are looking for a protocol that allows them to:...
3
votes
3answers
102 views

communication efficient private lookup

I have a scenario where a client has a private set and the server has a large public set, we would like an estimate of the intersection size or more specifically the percent of the private set covered ...
1
vote
1answer
601 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 ...
3
votes
1answer
363 views

Can we convert a pseudorandom function (PRF) to an Oblivious PRF (OPRF) through an Oblivious Transfer (OT) protocol?

I'm a software engineer, so I generally think in building blocks. And I'm not so familiar with the Math notation in Crytography, so I'll stick with function calls and function blueprints (which I ...
2
votes
1answer
133 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 ...
5
votes
1answer
316 views

Secure Computation: Reactive Functionalities in the Hybrid Model for Standalone Security

A common approach to make (secure computation) protocol descriptions and proofs simpler is to describe them in a hybrid model, where the protocol in the real world has access to some auxiliary ideal ...
2
votes
2answers
102 views

Multiparty secret generation protocol

The goal is to create a secret S on a trusted server by having users A, B and C each send a private seed to the server, in such a way that any 2 of them can later recover S by resubmitting their ...
1
vote
1answer
120 views

Difference in the Powers of Simulator and Environment in Universal Composability

I know that in UC model, environment controls the real world adversaries but there is still a simulator wrapped around these real-world adversaries in the ideal world (which we sometimes collectively ...
7
votes
1answer
447 views

Extractability for Simulator in Malicious Model

It is sometimes required while proving the security of a protocol in the malicious setting that the simulator is able to extract the witness set of the adversary, who tends to be the prover of ...
0
votes
1answer
37 views

Private set supporting adding elements and proving elements exist

Is it possible to construct such a set that parties can Add elements to the set without revealing the elements or knowing the elements presently in the set. Proving to other parties that a certain ...
1
vote
1answer
99 views

Implementation of ECC operations in BMR

I want to implement computing ECC operations (i.e., multiplication) in a BMR scheme (secure multi-party computation) What is the best way to do it? I found Fairplay MPC - to allow BMR computation ...
0
votes
1answer
64 views

Enforcing Randomness in Malicious Setting

I was going through some lecture notes where it said that if we have a 2-party protocol that requires both the parties to generate random integers during the course of protocol, then if we migrate the ...
6
votes
1answer
206 views

In coin flipping protocols, why aborting is allowed, and why the non-aborting party flips a coin at the end?

To convey how an adversary can bias the coin, most often a simple commitment-based two party coin-tossing protocol is given, as in [1]: Alice sends Bob the commitment $c = commit(x)$ Bob sends Alice ...
2
votes
1answer
203 views

About DDH over cyclic group Z*p^2

To construct a secure multiparty computation function, we need to use the cyclic group G = Z*p^2 with p is a large prime. However, we are uncertain that DDH holds over this group. Can you show that ...
2
votes
0answers
61 views

Necessity of Randomness when Privately Computing a Sum

I want to show that no 1-private deterministic protocol exists for calculating a sum of $n \geq 3$ parties (within the realms of Perfect rather than Computational Security). I'm having trouble showing ...
2
votes
0answers
101 views

Optimized Random-OT Security in Standard Model

I was going through the paper - " Efficient Oblivious Transfer and Extensions for Faster Secure Computation" by Asharov et al. where the authors propose an optimized OT protocol along with a Random-OT ...
2
votes
0answers
27 views

Computationally secure ORAMs with O(lg n)-bit words: shouldn't they fail with $n^{-O(1)}$ probability?

Virtually all "hierarchical" Oblivious RAMs use "cryptographically secure" hash functions to determine the position of an item at a given level; and implicitly assume (as can be evinced from the cost ...
5
votes
1answer
167 views

Can Secure Multi-party Computation be used to reconstruct secret shares?

When using Shamir's Secret Sharing is it possible to use Secure Multi-Party Computation to reconstruct the original secret without revealing one's secret share? When searching I have found results ...
3
votes
1answer
119 views

Is it possible to carry out multiplication of BGW protocol without communication?

I read the following famous two papers related to multiparty computation and I have a question like title. [AL17] Gilad Asharov, and Yehuda Lindell. "A full proof of the BGW protocol for perfectly ...
1
vote
0answers
33 views

Secure multiparty computation connectivity bound

I read some papers which studied the relation between the fault tolerance in secure multiparty computation and the connectivity of the underlying communication graph. Here I consider information-...
1
vote
1answer
87 views

Discussion about the importance of communication complexity for MPC?

Communication complexity is generally discussed among many papers on secure multi-party computation (MPC). However, I do not still understand the importance of it. What communication complexity ...
1
vote
1answer
118 views

Does semi-honest adversary eavesdrop honest parties communication?

Assume we have a multi-party computation protocol and the protocol definition, where both of them consider a semi-honest adversary, without explicitly assuming the type of channel the parties want to ...
1
vote
0answers
170 views

Rewinding techniques with some examples

I'm aware of these posts: What is a "rewinding argument"? Random oracle model proofs and programmability But I think, some concrete examples are missing. I need to know how exactly ...
1
vote
0answers
196 views

Homomorphic encryption - addition for more than two parties

I have just found out about the homomorphic encryption and I was wondering how is it possible to perform an addition for more than two parties? More concretely, I want to have several parties $P_i$, ...

1 2
3
4 5
7