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.
510
questions
1
vote
1
answer
80
views
Secure multiparty computation protocols for stable matching?
Are you aware of papers proposing secure multiparty computation protocols for stable matching problems such as Stable Roommates and Stable Marriage problems?
Specifically, I would like the ranking of ...
- 149
2
votes
1
answer
90
views
Is there any secure deterministic two-party computation protocol?
The notion of security considered here is privacy. Is there a secure two-party protocol does not rely on randomness at all when considering passive adversaries (or active adversaries)? If the answer ...
- 33
7
votes
1
answer
284
views
Generating suitable prime numbers for Paillier key pair in GG18
I am working on MPCs (multi party computation) in crypto, and now I am developing a implementation of GG 18.
In sign phase, algorithm needs MtA (Multiplicative to Additive) and uses a Paillier key ...
- 83
1
vote
1
answer
71
views
Does game-theoretical fairness work in when the goal of one party is randomness
When we take the coin flip in Blum's algorithm in "Coin flipping by telephone a protocol for solving impossible problems", where Alice and Bob both want ownership over the same car, then one ...
- 13
1
vote
0
answers
61
views
Constructing OR gate with OT
I am constructing a two-party OR gate and trying to do this with oblivious transfer. Yet I am very new to oblivious transfer, wishing to know whether the following construction makes sense.
Goal: ...
- 11
1
vote
1
answer
48
views
How to build a secure multiparty computation protocol using oblivious transfer as a blackbox?
The following statements seems to be a consensus in cryptography community.
Oblivious tranfer is a complete primitive for secure multiparty computation (SMC).
But I cannot find any explicit ...
- 13
4
votes
0
answers
77
views
On the Adaptive Security of MPC Protocols
In adversarial context of MPC, the corruption behavior
refers to the assumptions about the corrupted parties’ deviation level from the protocol
specification. Three main types of corruption behaviors ...
- 640
5
votes
2
answers
2k
views
Is there a way to calculate a hash with two people so that no one knows the pre-image but if they get together they do?
I'm trying to find a way to have multi party hash computation, more specifically for SHA256. I want for two people to be able to compute a hash so that none of them knows the pre-image but when they ...
- 140
2
votes
0
answers
48
views
What's the fastest way to generate matrix vector Beaver triplets?
$\vec{u_0} + \vec{u_1} = (M_0 + M_1)\cdot (\vec{v_0} + \vec{v_1})$
$P_i$ gets $(\vec{u_i}, M_i, \vec{v_i})$ where $M_i$ is a matrix , $\vec{u_i},\vec{v_i}$ are vectors, with all entries uniformly ...
- 509
2
votes
0
answers
29
views
Why zero sharings are used to mask secret value to the masked value appears to be a random value?
Some interpretations say "By masking a secret value with a uniformly random zero sharing, the masked value appears to be a random value drawn from a uniform distribution. This randomness helps ...
- 21
2
votes
1
answer
301
views
Implementing ECDSA threshold using a secret sharing scheme
My question might be a duplicate but I wasn't able to find a similar question.
I recently developed a wallet-like app and I am trying to implement some MPC features.
I searched a little and even asked ...
- 21
1
vote
0
answers
50
views
How is a message $\mu$ encrypted in a witness encryption scheme below? What does C(x) = 1 mean below?
I was reading this paper, where I came across the following statement on Pg 4 under the Homomorphic Commitments:
A witness encryption scheme, associated with a
NP language, consists of an encryption ...
- 41
1
vote
1
answer
289
views
What does a semi-malicious setting mean in MPC? How is it different from malicious or semi-honest setting?
I was reading this paper, where I came across the following statement:
We consider the problem of unbounded MPC with security against semi-malicious adversaries in the dishonest majority setting. In ...
- 41
3
votes
1
answer
144
views
Garbled circuit and secret sharing
Recently, I was reading the paper One Hot Garbling published on CCS 2021. I noticed a sentence in it:
In this work, we forgo the standard GC notation of garbled labels in
favor of garbled sharings of ...
- 112
2
votes
0
answers
59
views
Why does joint distribution of simulation output and functionality output is required?
I was going through this simulation tutorial.
For example, let x and y be lists of data elements, and
let f be a functionality that outputs an independent random sample of x ∪ y of some predetermined
...
- 41
3
votes
0
answers
115
views
Dynamic Distributed Key Generation for elGamal
I am looking for a scheme for dynamic threshold public-key encryption, which includes dynamic distributed key generation.
Namely, the number of parties that participate in DKG is bounded, but unknown. ...
1
vote
1
answer
174
views
Question about Secure Multi-Party Computation
I am doing research about Non-interactive Secure Multi-party Computation and encounter a dilemma that I am not quite sure if it is possible and wonder if there are better thoughts that could help.
...
- 13
2
votes
1
answer
111
views
Multi party authentication or encryption
I rent a room in a building. There are also 9 others who rent other rooms in this building. Just like everyone else who rents a room I only have one key of this building.
With my key I can open the ...
- 123
0
votes
1
answer
50
views
SMCQL practical examples
I am looking for some practical examples on how to use SMCQL on some typical SQL queries. The paper seems to be oriented more towards theory. Can somebody point me to some examples to understand it ...
- 191
0
votes
1
answer
58
views
Honest programming language for malicious adversaries in MPC protocols
One method to create a secure MPC protocol against malicious adversaries is to create a secure protocol against semi-honest adversaries and then add some zero-knowledge proofs to ensure that the ...
user105855
2
votes
3
answers
636
views
Secure Multi-Party Computation (MPC) protocol with all dishonest parties
What if we consider an MPC protocol in which all parties are dishonest? Is it unattainable (even with allowing abort) or is it just meaningless to think about?
user105855
4
votes
0
answers
117
views
Signature size discrepancy for MPC in the Head signature
I have been puzzled by the following for a long time. In the (very well know in the field) paper:
Improved Non-Interactive Zero Knowledge with Applications
to Post-Quantum Signatures
, the authors ...
- 243
5
votes
1
answer
113
views
Security of pseudorandom correlation for bilinear correlations
A pseudorandom correlation generator for bilinear correlation (namely, $x_0 \otimes x_1 = z_0 + z_1$, where party $\sigma$ gets $x_\sigma, z_\sigma$) over some field $F$ works roughly as follows (...
- 1,365
2
votes
1
answer
132
views
How to implement CRS model in the real world?
Traditionally, I think that implementing the CRS (common reference string) model in the real world is usually through a trusted third party or running a distributed protocol. Are there specific papers ...
- 112
2
votes
1
answer
83
views
Why not substitute division of a public value by multiplication to its reciprocal?
MPC protocols have a harder time handling division (truncation) than multiplication. The case I am considering is when the divisor is a public value. Dividing it may lead to a wrong result due to ...
- 35
4
votes
1
answer
155
views
How can Garbled Circuits be utilized to reduce the round complexity of GMW?
I've been reading this set of notes on some topics in MPC and am having difficulty understanding the transformation the authors make in order to reduce the round complexity of the GMW protocol through ...
1
vote
0
answers
67
views
How can the AND gate be executed efficiently in the GMW protocol for the MPC setting?
GMW is a pretty straight forward protocol for the setting of 2PC. It is still straight forward for the case of MPC except for the AND gate. I'm struggling to understand how to obtain a "good"...
- 962
0
votes
1
answer
145
views
Conditional Boolean circuits
I have two questions I couldn't find straightforward answers to after many searches.
(1) We can perform 2-party MPC over arbitrary functions using Garbled Circuit. To do that, we first need to convert ...
- 103
1
vote
1
answer
72
views
Can BDOZ and SPDZ implement secure 2-party computation？
Considering that P1 has value x, P2 has value y and they want to compute x+y without telling the other what he has,So P1 and P2 secret-share their values to each other.
Now P1 gets x1 and y1, P2 gets ...
- 13
0
votes
1
answer
70
views
Oblivious Decision Making
Suppose there is a ciphertext $C_1$ that hides message $m_1$ using a distributed additively homomorphic public key. I would like the holders of the key to run a protocol where if $m_1 = 0$, then it ...
- 313
1
vote
0
answers
88
views
MPC Protocol with Additions and Multiplications for FREE
Imagine an MPC protocol where both multiplications and additions come for free (2 round). The protocol works over arithmetic circuits, and the security setup is as relaxed as possible:
Semi-Honest.
...
- 872
1
vote
0
answers
72
views
Most efficient way to implement a 1-out-of-4 OT for GMW?
Assuming evaluation in the online phase (no beaver triple/offline method used), each AND gate in GMW must be evaluated using a 1-out-of-4 OT. I've seen some sources (here, and here) say this can be ...
- 33
0
votes
2
answers
318
views
Security against malicious adversaries in MPC
I have a question in the context of two-party computation and the proof of the security of an MPC. I have looked at some of the beginning parts of this, this chapter 7, and
this But I couldn't achieve ...
- 283
2
votes
1
answer
133
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,365
0
votes
0
answers
46
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 ...
- 149
1
vote
0
answers
64
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 ...
- 113
1
vote
0
answers
52
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 $...
- 99
1
vote
1
answer
155
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
103
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).
...
- 33
0
votes
2
answers
121
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
129
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 $...
- 424
2
votes
0
answers
24
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
38
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 ...
- 243
0
votes
0
answers
74
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,365
1
vote
0
answers
36
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 ...
- 498
4
votes
0
answers
117
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
1
answer
83
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
...
- 251
4
votes
1
answer
130
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$ ...
- 962
1
vote
1
answer
214
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,365