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.
337
questions
1
vote
0answers
14 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
36 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
21 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
27 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
28 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
41 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
44 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
40 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
146 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
17 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
38 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
40 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
64 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
48 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
54 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
32 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
50 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
53 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
52 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
75 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
72 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
58 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
243 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
65 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
63 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
95 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
70 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
38 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
79 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
34 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
165 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
54 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
152 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
27 views
Stand-alone vs UC and Non-reactive vs Reactive Functionalities
I'm looking for a simple and concise explanation for the following:
What are crucial differences and similarities between UC and stand-alone security? Under what conditions does one imply the other?...
0
votes
0answers
60 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
110 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
73 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
91 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
80 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
68 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
78 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
52 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 ...
0
votes
0answers
43 views
Confidential data encryption on ethereum
I already built a supply chain that is able to collect product information on Ethereum. Now, that data can be confidential, but I still want to do Matrix calculations on it. I came across homomorphic ...
1
vote
0answers
48 views
Google Timeline: is it encrypted and if so who has the key? [closed]
Google Timeline claims (e.g. here) that "Your Timeline is private, so only you can see it."
What does that mean? As a cryptographer I would take that to mean that the Timeline data is encrypted using ...
0
votes
1answer
77 views
Does secure multiplication makes sense in the case of 2 inputs?
I am looking at a protocol to securely multiply numbers, so as to preserve privacy of inputs.
In particular, suppose there are three parties $P_1$, $P_2$ and $P_3$ and 2 numbers to multiply, $a \in \...
1
vote
0answers
23 views
Partially synchronous model in broadcast
I am confused by the different definitions attributed to partially synchronous model: for e.g., in a paper by Hevia and Micciancio (PODC 2005), they state that messages sent in one round are ...
2
votes
1answer
217 views
Threshold decryption in multi-key homomorphic encryption
I have a problem understanding the security of threshold decryption in multi-key homomorphic encryption (MKHE) with so called "noise flooding". In particular I think that it is not secure, so probably ...
