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.
342
questions
1
vote
1answer
61 views
In simulation proofs of MPC, why could random oracle extract adversary's input?
I am learning the simulation-based security proofs in MPC, and have read the great tutorial "How to simulate it" by Prof. Lindell.
Here's my understanding about why we need to "extract ...
2
votes
1answer
39 views
Real-world offline phase implementation in MPC setting
I've been reading up on various basic MPC primitives (multiplication, inversion, exponentiation and so on of secrets shared between multiple parties).
One of the problems of implementing MPC in real-...
0
votes
0answers
29 views
Multiparty computation on circuits that perform group operations
I see that a lot of multiparty computation and garbling protocols are implemented for circuits like AES or SHA256.
For my project, I would like to garble a circuit that performs some group operations ...
1
vote
2answers
81 views
Multiparty Computation to calculate addition of shares without revealling individual shares
I have $n$ persons, each holding a secret integer $x_i$ ($i$ from $1$ to $n$) and I'm looking for a way for them to jointly compute the sum of these secrets without revealing to each other their ...
2
votes
1answer
90 views
Should the field size in Shamir secret sharing scheme be larger than secret?
I'm playing around with implementing Shamir's secret sharing scheme in Kotlin.
Here is implementation so far:
...
2
votes
0answers
40 views
Trade-offs for more parties in PICNIC multi-computation
In the PICNIC post-quantum signature scheme, a zero-knowledge proof of the secret key for a symmetric encryption is produced by implementing the encryption as a Yao garbled circuit of a three-party ...
2
votes
0answers
64 views
Authenticated sharing in MASCOT protocol
I am studying MASCOT protocol for multiparty computation and I am stuck in the comprehension of the authentication protocol $\Pi_{[[ \cdot ]]}$ and its security proof.
Supposing the initialize phase ...
2
votes
0answers
52 views
Why should the smudge noise be used?
Consider a threshold FHE scheme based on RLWE like this:
Refer to this paper
$\textbf{Initialization:}$
Every party generates his own secret key $s_i$, then uses the common polynomial $a$ to generate ...
1
vote
0answers
23 views
Threshold signature verified by an equivalent key
I am looking for references for the following problem:
Consider we have a DSA with the keypair $(sk, pk)$ and a message $m$, such that its signature is $s = sig(m,sk)$ and the verification result is $...
1
vote
0answers
38 views
Understanding multiplication of Shamir secret sharing during threshold (EC)DSA signing
I have been looking at the threshold (EC)DSA schemes for honest majority by Gennaro et al. https://www.sciencedirect.com/science/article/pii/S0890540100928815. In the scheme, there are steps where we ...
0
votes
0answers
35 views
Constructing efficient zero knowledge proof card game
I had asked an unanswered question earlier and now, I think I have an answer (sort of), not really but I think I know where to look for it. We assign each type of card combination a score such that a ...
0
votes
1answer
43 views
May it be possible that the trusted third party knows the parties' private keys in an “ideal model” of a Secure multiparty computation protocol?
May it be possible that the trusted third party knows the parties' private keys in an “ideal model” of a Secure multiparty computation protocol?
I wonder if it may be possible that a trusted third ...
0
votes
0answers
38 views
Encrypting multiple groups of data with separate keys in a single encrypted column
I will write this question using a database example, but please note this detail may be irrelevant.
Let's say I have data belonging to N clients stored in a single column of a database table. Each ...
1
vote
1answer
53 views
is coin-tossing an instance of secure computation (MPC, 2PC, etc.)?
Coin-tossing protocol is defined as a protocol between at least 2 non-trusting parties that allows them to obtain an unbias random bit in such a way that no involved party can influence the output. ...
0
votes
1answer
41 views
Is it meaningful to allow parties to use a non-uniform random tape in 2-party computation?
Consider a trivial example where two semi-honest parties want to flip a biased coin. Since the sender is semi-honest, the sender can locally flip a biased coin and send it to the receiver. A natural ...
3
votes
2answers
150 views
What is the difference in designing an MPC protocol by ring or field?
To the best of my knowledge, most of the MPC protocol's are built on a ring $\mathbb{Z}_{2^\ell}$(usually $\mathbb{Z}_{2^{64}}$) or field $\mathbb{Z}_p$ ($p$ is a big prime), why? What is the ...
1
vote
0answers
19 views
2 Round Secure Multiparty Computation with BGW
The BGW protocol gives us security aginst a dishonest minority of parties, with round complexity linear in the function's circuit depth.
Several works (like ABT18 or LLW20) use the BGW protocol to get ...
0
votes
1answer
39 views
Can you use a “power of 2” gate in the BGW protocol
I am learning about the BGW Protocol and I understand that for a MUL gate, you need to follow the degree reduction protocol. I am wondering if it is possible to implement a single input and single ...
1
vote
1answer
43 views
Why did replicated secret sharing use correlated randomness?
When I read the AFL16 paper by Araki, each party's share is adding a correlated randomness, like r1 = (a1b1−x1y1+α)/3 , r2 = (a2b2−x2y2+β)/3, r3 = (a3b3−x3y3+γ)/3 with α+β+γ=0, and use AES to ...
2
votes
1answer
95 views
What is the most efficient 1-out-of-N Oblivious Transfer construction described in current literature?
I have been studying Oblivious Transfer for my bachelor's thesis and have been surprised at the number of variations of OT.
From what I've read so far, the constructions proposed by Naor and Pinkas in ...
0
votes
1answer
54 views
Secret Sharing Domain Questions
all,
I have a very fundamental question on Secret Sharing schemes such as SPDZ families.
As far as I can see for now, SS schemes always assume a certain variable range. For example, suppose the bit ...
2
votes
0answers
55 views
Secure Protocol
How to show there is no secure protocol to compute OR?
I need to know the mathematical proof of this statement. I am understanding this statement using the matrix representation of $f(x,y)$ but unable ...
0
votes
1answer
33 views
LSB extraction in MPC: Doubts about correctness
I have doubts about whether the protocol below for LSB extraction (denoted Mod2) from the paper Improved Primitives for Secure Multiparty Integer Computation is correct. Clarifications will be ...
2
votes
1answer
56 views
How (generally) do modern schemes deal with an adversary with the capacity to either instantly, or over time, corrupt a majority of parties
I'm curious about the honest minority case and what cryptographers have and are currently using to get around this. My motivation is primarily the MPC space, but I'm sure there are other subfields ...
1
vote
1answer
56 views
Simulating a joint distribution of an *almost* deterministic function
The following is in the context of secure MPC.
Suppose that there is a functionality $f(x,y)$ which outputs 'answer' with probability $1-\textrm{negl}(n)$ for some security parameter $n$, and 'other ...
1
vote
1answer
57 views
Boolean circuit: can the output wire of a gate be used by many different gates in the next layer?
There are two typical secure multiparty computation paradigms using boolean circuits, namely garbled circuit and secret-sharing-based boolean computation. It is well-known that garbled circuits can be ...
3
votes
1answer
79 views
Why does verifiable secret sharing with an honest majority require a broadcast channel?
In the information-theoretic model with active adversaries, it seems to be well-known that no protocols with exact reconstruction of the secret exist for the task of verifiable secret sharing (VSS) ...
3
votes
1answer
83 views
Is there any examples of information-theoretic secure MPC for dishonest majority against malicious adversary?
My research is to propose highly secure MPC protocol with some conditions.
Especially, I want to consider that
security against malicious (active) adversary
dishonest majority setting
information-...
1
vote
0answers
60 views
Non-post quantum primitives in MPC protocols: for and against?
Is it acceptable from a security point of view for an MPC protocol to use non-post quantum cryptographic primitives?
Note that except for secret sharing, which provides information-theoretic security, ...
1
vote
2answers
246 views
Imposibility of bias-resistant coin tossing (Cleve'86) and its connection to modern notion of fairness in Secure Multiparty Computation
In modern Secure Multi-party Computation (SMPC) protocols (informally) the notion of Fairness and Guaranteed Output Delivery (GOD) is defined as follows:
Fairness: If the adversary gets the output of ...
1
vote
0answers
76 views
What's the difference between compromise and corruption in MPC?
What is the difference between corruption and compromise? Are Compromising a user and ...
2
votes
1answer
64 views
Non-interactive proof of value in MPC
Does it exist? Specifically using Shamir secret sharing based MPC and looking for a (non-)interactive way to prove that the secret value is valid. A value is valid if it is part of a set for example $[...
2
votes
1answer
127 views
MPC protocols in plain/CRS/PKI models
I have seen that in MPC multiple models in different dimensions can be envisioned, like asynchronous vs synchronous networks, access to broadcast channels, and so on. However, a particularly ...
0
votes
0answers
34 views
Model a dishonest majority controlled by several adversaries in a voting protocol?
In the context of secure multi-party computation protocols, when a dishonest majority is considered, it is assumed the worst case scenario, i.e., all the corrupted parties are controlled by the same ...
2
votes
2answers
74 views
Regarding the feasibility of MPC protocols
I know that there is a general result stating that any function can be computed in an MPC protocol. In this question, I'm interested in understanding the practicality of MPC protocols.
Are any ...
0
votes
0answers
42 views
Steiner GDH3 (n-party Diffie Hellman)
I am trying to implement a n-party Diffie Hellman protocol.
In particular I'm implementing Steiners et. al. natural extension "GDH3" (starting on page 34).
The problem is that my python ...
6
votes
2answers
82 views
Garbling in the wild (soft question)
I am curious to know whether (Yao's) garbled circuits are actually deployed in practice. There has a lot of works on optimising garbled circuits (e.g., here and here) and I am interested in whether ...
1
vote
1answer
35 views
Secure multiparty computation… where one entity owns all parties
Here's a corner case for you.
A user produces a small amount of confidential data and would like to delegate a third-party to perform some computation on it and return the results. Data and results ...
3
votes
1answer
212 views
Is there a secure multi-party computation (SMPC) scheme that doesn't use secret sharing?
According to the Wikipedia article about SMPC:
Secure MPC is closely related and builds on to the problem of secret
sharing, and more specifically verifiable secret sharing (VSS), which
many ...
4
votes
1answer
61 views
Multiparty dataset intersection count
Typically, Private Set Intersection (PSI) protocols let you learn the subset of items on each party's dataset that are in the intersection. The problem in this case is a relaxation of these kind of ...
0
votes
0answers
172 views
CKKS Encoding scheme explanation
I have been going over the CKKS Homomorphic Encryption scheme but I can't seem to understand how the mapping takes place while encoding. I don't get what the line below is trying to convey. I saw this ...
0
votes
0answers
63 views
BGW Multiplication: Linearizing the polynomial
I have some trouble understanding the linearization of the degree 2t polynomial generated by multiplication in BGW. It would be great if someone could decode this ...
0
votes
1answer
120 views
BGW Multiplication: How does it work?
I could not understand how multiplication is carried out in the BGW protocol for 3 parties. Reference: https://crypto.stanford.edu/pbc/notes/crypto/bgw.html
I've understood that in multiplication, we ...
1
vote
2answers
76 views
GMW Multiplication AND for 2 parties
I am looking into the GMW protocol's evaluation for multiplication in 2 parties. I have referred to different materials on it but I didn't exactly understand how $a_i b_j + a_j b_i$ is calculated in a ...
2
votes
2answers
95 views
Does Cut-Choose technique for yao garbled circuit provide statistical security?
Yao Garbled circuit is 2 parties secure computation protocol between Semi honest adversaries. However, the cut-and-choose mechanism complies semi-honest garbled circuits into the one secure against ...
1
vote
0answers
55 views
Can two anonymous parties determine whether they interacted before, without being able to link encounters?
Assume an anonymous communication system in which anonymous parties randomly meet in pairs to exchange information.
How could two anonymous parties determine whether they have interacted before, ...
0
votes
1answer
105 views
Example of a Two-party GMW Protocol
I have been looking for a concrete example of GMW protocol for two parties. I was trying with the following example for computing $XOR$ of two parties:
A's secret bit is $a = 0$, B's secret bit is $b ...
2
votes
1answer
81 views
Extract adversary's secret input in simulation based security proofs
I am trying to understand the simulation-based security proofs (as well as the UC framework), I find that there is a basic assumption when proving the security, i.e., the simulator could extract the ...
-1
votes
1answer
79 views
If there exists MPC protocols such that f(x1,x2,…,xn)--> y,y,…,y then there exists MPC such that f(x1,x2,…,xn)--> y1,y2,…,yn
Show that if there exists MPC for all same-output n-party functionalities then there exists MPC
for all diff-output functionalities.
1
vote
0answers
53 views
Encrypting text with AES and MPC
I'm thinking of implementing text encryption and decryption in my program using AES using key sharing thanks to MPC (the point is that the key should never be provided in full), however, all public ...
