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
2 votes
1 answer
32 views

Pseudorandom correlation generators for many small tensor products

Pseudorandom correlation generators (PCG) exist for tensor products, this is described in Figure 1 of [1]. Basically we want party 1 to hold $(x_0, z_0)$ and party 2 to hold $(x_1, z_1)$ such that $...
  • 1,252
0 votes
0 answers
26 views

Multiple input AND/OR gate evaluation

In MPC, AND and XOR gates are two mostly used gates. However, most of the solutions (Garbled Circuit or Boolean Secret Sharing) considered these gates having 2 input wires and 1 output wire. I am ...
  • 107
1 vote
0 answers
22 views

How to do modulo operation in a MPC scheme like ABY?

In MPC schemes like ABY or MOTION, the modulo operation is based on a ring $Z_{2^l}$. So for arithmetic sharing, it is relatively easy to make addition operation in the ring. My question is, what if I ...
1 vote
0 answers
44 views

Is it possible to execute multi party computation over public ledger?

Let $F(x_1,…,x_n)\mapsto(y_1,…,y_n)$ be some arbitrary computable function. Suppose there are $n$ parties, where each party $i$ encrypt its message $m_i$ with a public key $\mathrm{pk}_i$ and obtain $...
  • 59
1 vote
1 answer
25 views

Is there any attack from a malicious adversary against semi-honest MPC protocol?

For semi honest MPC protocols, adding some errors can easily make the output wrong. I wonder beyond that, can malicious adversaries make some attacks against semi-honest protocols to obtain private ...
1 vote
2 answers
50 views

Reusing base Oblivious Transfers

I am new to Oblivious Transfer (OT) and am having trouble finding a definitive answer regarding if/when/how baseOTs can be reused in a computation when using OT-extension (for passive security only). ...
  • 21
0 votes
2 answers
73 views

In SPDZ, difference between protocol in $\mathbb F_p$ and in $\mathbb F_{2^k}$

I have read SPDZ family protocol, the domain of the spdz_1 in 2012 is $\mathbb F_{p^k}$. Later mascot'16 supports both $\mathbb F_p$ and $\mathbb F_{2^k}$, where $p=2^k+u$. I want to know the ...
  • 21
0 votes
0 answers
35 views

the difference between field $F_{2^k}$ and ring $Z_{2^k}$ in multi-party computation, especially in SPDZ family [duplicate]

I have seen different protocols in field or ring, I used to think ring is a special field when 2^k. But when I read the paper later, I doubted my understanding.
  • 21
2 votes
0 answers
36 views

A Question on the "rewinding" technique in secure computation

Consider secure two-party computation against malicious adversaries in the standalone model. I know that the "rewinding" technique can be used to extract the corrupt party's input, e.g., in $...
  • 404
2 votes
0 answers
16 views

How to prove the security of the MT-based multiplication protocol via the simulation paradigm

It is known that Multiplicaiton Triple (MT) can be used for secure online multiplication, which is defined by $\mathsf{Mul}(x, y)=(z_0, z_1)$, where $x\cdot y = z_0 + z_1$ $P_0$ sample random $a$, ...
  • 21
2 votes
0 answers
27 views

Question about Ligero protocol

I have a question for those that might be familiar with the ligero protocol: Ligero In this protocol to be using an MPC in the head paradigm: described here. However, in the description of their ...
0 votes
0 answers
21 views

How to select the top two highest (or smallest) value in Two/Three Party Computation?

I want to select the top two secret-shared values from a vector of secret-shared values among 2/3 parties. Formally, given secret-shared (assume using additive/replicated secret sharing) vector $<V&...
  • 63
0 votes
0 answers
34 views

MPC model used in Ligero and Limbo

Ligero (https://dl.acm.org/doi/10.1145/3133956.3134104) and Limbo (https://eprint.iacr.org/2021/215.pdf) use a somewhat unique MPC model for their zk-PCP where not all parties communicate with each ...
  • 1,252
1 vote
0 answers
31 views

How does Diogenes prove equivalence of discreet logs despite the candidates not being composed of safe primes

In the paper describing a protocol for distributed RSA modulus generation, Diogenes, "[they] employ a special-purpose $\Sigma$-protocol based on [Sho00] for proving correctness of exponentiations ...
  • 488
4 votes
0 answers
60 views

How to get started with Simulation and UC proofs?

I've been in my PhD program for a few months, and every time I try to understand the simulation and UC proof-paradigms I get so confused. I feel like what I really need is an easy set of (guided) ...
0 votes
0 answers
23 views

Understanding LSB extraction

I am not able to understand LSB extraction as explained in protocol 3.4 of this paper Improved Primitives for Secure Multiparty Integer Computation Specifically, the protocol samples random number $r'...
  • 239
0 votes
0 answers
20 views

secure 2pc bit extraction?

I want to solve following problem Give secret shared [x] I want to extract MSB of x, in other words I want to get sign(x). Just to ensure I do not want to sure Yao Garbled circuit. I found one ...
  • 239
0 votes
1 answer
42 views

Millionaire problem where one entry is public?

I want to evaluation following functionality: Parties have secret shares of private input [a] and public input b, they want to measure if a>b, additionally only one party should learn the output ...
  • 239
2 votes
0 answers
58 views

How Cut-and-Choose can leak information?

I'm currently reading the book "A Pragmatic Introduction to Secure Multi-Party Computation". On pages 103-104 I came across the following related to the Cut-and-Choose technique: If $P_2$ ...
  • 673
0 votes
0 answers
42 views

Converting a random OLE (oblivious linear function evaluation) to an OLE

It is known that by adding an extra round of communication, it is possible to convert a random OT (where the choice bits and the sender input are random) to a standard OT, see https://crypto....
  • 1,252
2 votes
1 answer
83 views

How to do division in secure multi-party computation (mpc)?

In the practical application of secure multi-party computation, the operation of division is inevitable. But I don't know how to construct a division? In order to make the problem more accurate and ...
  • 21
2 votes
1 answer
108 views

Is there three-party protocol for Secure Equality Test (a.k.a Socialist Millionaire problem)?

Secure Equality Test is an important building block in Secure Multi-Party Computation (MPC) with respect to Secure Comparison, also known as Socialist millionaire problem. A similar question was ...
  • 63
1 vote
0 answers
22 views

Will two-party garbled-circuit based protocol have any security issue when inputs are from multiple parties?

If the inputs for a garbled circuit are from multiple parties, can parties (not garbler, not evaluator) obtain the labels corresponding to its input from the garbler via oblivious transfer then send ...
1 vote
1 answer
57 views

Working with Paillier and ECDSA - Order issue

I'm trying to implement two party computation for ECDSA signing using Paillier cryptosystem. But my problem is that the order of Paillier is different from the order of the curve (secp256k1 in my case)...
  • 113
0 votes
0 answers
31 views

Correcting threshold in multi-party computation

I am currently reading the paper Graceful Degradation in Multi-Party Computation. The paper mentioned something about correct structure, denoted C = {C1, . . . , Cl}. On page 10 the paper reads: ...
  • 99
0 votes
0 answers
28 views

A question about masking input then share

I am confused about a simple input-sharing schema. The schema: a party that holds an input x, and generates a random variable r. That party secret share r as [r], then distribute it to other parties. ...
  • 99
1 vote
2 answers
98 views

"shared" variant of 1-out-of-N oblivious transfer

In the traditional 1-out-of-n OT, we suppose Alice has an array $A=\{x_1,{\cdots},x_n\}$ and ...
  • 63
0 votes
0 answers
32 views

How is there a $\frac{1}{poly(n)}$ bias in a multiple-round coin tossing protocol with commitment?

On p.2, Example 1.1 (in this paper), there is a description of a coin tossing protocol with bias 1/4. In the paragraph below the example, they note that for a protocol with $r$ rounds (assume for the ...
  • 311
0 votes
1 answer
63 views

Secure communication over insecure channel is based on the assumption of secure channel?

Consider a scenario:data owners $C$ sends a $l$ bits value $x$ to parties $P_0$ and $P_1$ via additively secret sharing scheme, for example, $C$ randomly selects $r \in_R \{0, 1\}^l$, and sends $r$ to ...
  • 40
1 vote
2 answers
143 views

Is there a winning strategy based on this coin-flipping protocol?

Given the coin flipping protocol: A chooses $a \in_R \{0,1\}$ and computes $commit(a,r)$. She sends $commit(a,r)$ to B. B chooses $b \in_R \{0,1\}$ and sends $b$ to A. A sends $open(a,r)$ and B ...
  • 311
2 votes
2 answers
149 views

Secretly compute multiplication of two numbers owned by two people

For example, Alice and Bob have two numbers $a$ and $b$, respectively. They want to calculate the multiplication $a\cdot b$ without Alice knowing $b$ or Bob knowing $a$ and send this multiplication $a\...
  • 69
1 vote
1 answer
76 views

Simulation based proof for Beaver's multiplication protocol

Setup Recently, I became interested in simulation based proofs in the context of secure two party computation. I read some book chapters (from Secure MPC and Secret Sharing and Foundations on ...
  • 13
0 votes
1 answer
57 views

Difference between Non-Interactive Secure Multiparty Computation (NISMPC) and Fully Homomorphic Encryption (FHE)

Until recently, I only knew about SMPC* and FHE, but now I just encountered the term NISMPC. I was wondering what is their difference and what is their difference in their use cases? Sometimes in ...
  • 673
0 votes
0 answers
19 views

Data encryption or Blockchain in data sharing between *multiple* sources?

imagine several parties that own data, and some of them need to use data of other parties, but have only limited access rights to it. An example: Party #1 (pharmacy store) needs confirmation from ...
1 vote
1 answer
113 views

What is the essential difference between Garbled Circuit and Oblivious Transfer?

According to the literature (https://en.wikipedia.org/wiki/Garbled_circuit), Oblivious Transfer allows a party A holding a function $f$ and a party B holding a index i to jointly compute the value $f(...
0 votes
0 answers
68 views

Tools/libraries to protect private keys using shamir secret sharing / multi-party computation?

here is the scenario. I want to use the concept of shamir secret sharing (or other multi-party computation methods) to store my private key in the public-key encryption. For example, I use RSA to ...
  • 69
1 vote
1 answer
78 views

Anonymous PAKE using two party computation

Let's say client side has a secret password $\pi$. The server has a series of indices $0..n-1$ and a salt associated value $s_i$ for all $i \in \{0,n-1\}$ call it set $S=\{s_i | i \in \{0,n-1\}\}$ ...
2 votes
1 answer
110 views

Does shared randomness between two cryptographic primitives complicate the hybrid argument for computational indistinguishability?

Let $(Enc, Dec)$ be an IND-CPA secure encryption scheme, where $Enc: \mathcal{K} \times \mathcal{M}_1 \rightarrow \mathcal{C}_1$, and $F: \mathcal{K} \times \mathcal{M}_2 \rightarrow \mathcal{C}_2$ be ...
  • 404
0 votes
0 answers
49 views

Tuples 2P secure multi-party computation against malicious adversaries algorithms

There are secure multi-party computation algorithms and implementations [1] for signing 2-party messages where the parties don't need to reveal their secrets. Can this algorithms be used for signing ...
  • 101
0 votes
1 answer
64 views

AES in binary-circuit-based 2PC

No matter AES with CBC or EBC etc, the inputs for AES i.e, plaintext, key, IV, are always provided by one party. In other words, there is no need for AES in a 2PC scenario since one party can already ...
  • 37
1 vote
1 answer
104 views

SHA-256 in binary-circuit-based MPC

For a binary-circuit-based MPC, the multiparty will provide its inputs to calculate the result, which indicated the function $f(x_1, x_2, \dots,x_n)$ needs to accept $2$ or more inputs. Why do there ...
  • 37
1 vote
0 answers
30 views

Why we need broadcast channel in the 3PC setting?

I am a MPC learner for privacy-preserving machine learning. Recently, I am reading this paper: FLASH: Fast and Robust Framework for Privacy-preserving Machine Learning. I am confused about the ...
  • 65
3 votes
1 answer
51 views

About simulating abort in multiple party computation

I am new to the simulated proof and am a little bit confused about the abort in the simulation. When the real-time protocol abort, I assume that the ideal process should also abort? Does this mean ...
  • 99
1 vote
1 answer
52 views

Securely sort lists of numbers from two parties

I am looking for ways to securely sort two lists of numbers. Yao's millionaire's problem considers each party with one secrete number and compare them securely. Are there papers on extension to this ...
2 votes
2 answers
82 views

Are all parties for an MPC protocol needed?

For a lot of cryptographic applications, multi-party protocols are used. The idea is to create shares of a key/secret and give them to multiple parties. My question is: Do all parties have to ...
  • 1,692
1 vote
1 answer
42 views

Question about round complexity of secure multiple party computation based on secret sharing

I am reading Fast and Secure Three-party Computation: The Garbled Circuit Approach And in the introduction section it said that: the round complexity of these protocols is proportional to the ...
  • 99
2 votes
1 answer
58 views

Leaking information for giving the yao's garbled circuit's garbled output

I am currently reading the paper: Efficiency Tradeoffs for Malicious Two-Party Computation. The paper describes a $k$-leak model and gives an example that leaking 1 bit could turn Yao's garbled ...
  • 99
0 votes
0 answers
60 views

How could this scheme work?

When we use a secret sharing scheme we usually want to reconstruct the polynomial function $p(x)\in\mathbb{Z}_q[X]$ with the Lagrange interpolation method and then compute $s=p(0)=a_0$. However, the ...
0 votes
2 answers
121 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}$ ...
0 votes
0 answers
23 views

Witness Recovery in SPDZ Offline Phase

I am currently reading SPDZ: https://eprint.iacr.org/2011/535.pdf. The MPC protocol uses an encryption scheme $\operatorname{Enc}_{\operatorname{pk}}(x,r)$ based on Brakerski, V. Vaikuntanathan (...

1
2 3 4 5
10