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.
453
questions
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 ...
- 103
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 ...
- 11
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 ...
- 203
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) ...
- 41
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(...
- 35
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\}\}$ ...
- 561
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 ...
- 269
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}$ ...
- 269
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 (...
