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.
0
votes
0answers
26 views
Decentralized / Distributed Private Key Generation between Untrusted Parties?
I found an interesting concept in this paper, page 13, (Link to the paper) called "Decentralized private key generation", as follows:
"Decentralized private key generation – Multiple Enigma nodes ...
1
vote
1answer
72 views
Simulation based proofs, what am I missing?
In the example given by in the top answer of Simulation based proofs: Simple examples claims that this is insecure the semi-honest, and I need assistance in where I am failing to reason why that this ...
3
votes
1answer
73 views
Where can I find open source code for Encryption Switching Protocol?
The concept of Encryption Switching Protocols was introduced in CRYPTO.
I was wondering if there is any pseudo-implementation of the protocol available or can I get some insights on how to implement ...
0
votes
1answer
58 views
Question on proof of coin-tossing in “how to simulate it”
I am reading Professor Lindell's "How To Simulate It - A Tutorial on the Simulation Proof Technique" paper, which is very enlightening.
I am trying to follow through the proof of the security of Blum'...
0
votes
1answer
56 views
How to do division using Beaver Multiplication Triples
It is very straight-forward and intuitively to achieve addition, subtraction and even generalized polynomial using Beaver's Multiplication Triples. However division seems difficult to achieve on two ...
0
votes
0answers
32 views
Blinding factor SEAL
For a protocol, I need to blind a ciphertext. I am not sure how to choose the blinding factor. How should I choose the range? What should I consider to offer security?
I am using CKKS scheme, the one ...
1
vote
1answer
52 views
Proving security for Secure Multiparty Computation with malicious adversaries
In the case of malicious adversaries, while creating a simulator for an attacker in the real world what are the algorithms that this simulator has access to and why?
For eg. I've seen simulators that ...
2
votes
0answers
19 views
Strategies for fast integrity attestation over multi party computation for large messages
I am looking for ways to efficiently perform integrity attestation over large messages using multi party computation. While, hashing (SHA1, 256...) is one alternative but it's painfully slow and grows ...
2
votes
1answer
61 views
Secure multi-party random number generation
This question is actually continuation of my previous one.
Secure multi-party computation for digital signature
to implement solution there, I have to generate random data for padding (I will use ...
2
votes
1answer
67 views
Secure multi-party computation for digital signature
Is there any practical algorithm that will allow to use public key cryptography (RSA or ECC) in the following way
There are N parties. Up to M are malicious adversaries (were trusted, but got taken ...
1
vote
0answers
63 views
Purpose of the ZKPoPK in the original SPDZ protocol
What is the purpose of ZKPoPK in the SPDZ paper? And will the following can detect the active adversaries in 2 party spdz excluding ZKPoPK step?
Each party sends a commitment on his MAC key ∆_i ...
1
vote
1answer
42 views
Is computing majority element while doing secure two party computation for inner products ( input of the two parties ) an attack on the protocol?
This was told to be an attack.
However, we can create a simulator in the ideal world which sends all 1s to the trusted party and receives the number of ones of the honest party. Is this simulation ...
0
votes
1answer
59 views
Two parties SPDZ Protocol Input sharing
Assume we have two computing parties for SPDZ protocol. The two parties are also the input parties. How can they share the MACs on their input shares assuming one party is the master who owns the MAC ...
0
votes
0answers
22 views
Time-locked deposit protocol?
I am designing a protocol where a user A sends a time-locked deposit to user that if the user B within time t provide a proof that he exists in a location x (this may be obtained by third party like ...
3
votes
1answer
55 views
BGV KeyGen— Can a maliciously-generated secret-shared key break security (e.g. SPDZ)?
I was (re)reading the paper "Practical Covertly Secure MPC for Dishonest Majority–or: Breaking the SPDZ Limits".
One of the key points in this paper is that they present a covertly secure BGV key ...
3
votes
1answer
113 views
Security of Fast Two-Party ECDSA Signing
The paper "Fast Secure Two-Party ECDSA Signing" by Yehuda Lindell describes a system in which two parties, $P_1$ (with 1/2 of a share of a long-term ECDSA signing key $x_1$) and $P_2$ (with the other ...
0
votes
1answer
47 views
Oblivious transfer with trusted third party Trent
I am trying to solve this exercise.
Assume an oblivious transfer protocol that uses a trusted third party Trent.
Alice's messages $M_0$ and $M_1$ are binary values of length $k$. Bob's message ...
2
votes
3answers
100 views
Algorithm for binary less than in MPC
Given binary shares $[a_{l-1}]_p,...,[a_0]_p, [b_{l-1}]_p,...,[b_0]_p$ such that $a = \sum_{i=0}^{l-1} a_i2^i,b = \sum_{i=0}^{l-1} b_i2^i $
for $a,b \in Z_p$, how to compute $a \overset{?}{\lt} b$ in ...
1
vote
1answer
114 views
Interactive Homomorphic Encryption
Let's say that I have a plain computational process that consists of several divisions and I do not want to do it with non-interactive homomorphic encryption.
I would like to ask how can I call this ...
2
votes
1answer
83 views
Blind Computation
Let's say that there are two parties. Party $A$ has ciphertexts $c_1, c_2$ encrypting data $m_1,m_2$ respectively. $A$ does not know the secret key to decrypt $c_1, c_2$. Party $B$ has the secret key.
...
6
votes
2answers
144 views
Algorithm for computing modular inverse in MPC
Is there any known algorithm for calculating $a^{-1} \pmod{q}$, where $ q < p$ and $F_{p}$ is the prime field of the MPC, in a linear secret sharing scheme ?
I have tried using the standard ...
6
votes
0answers
68 views
Distributed generation of random integers with prescribed sum
While reading this document I came across the following problem. Assume you have $n$ clients. The clients need to generate random integers in $\mathbb{Z}_p$, say $T_i$ for $i \in \{1, \ldots, n\}$, ...
0
votes
2answers
164 views
Difference between Zero Knowledge Proofs and Multi Party Computation
I am struggling with understanding the difference between the two. From what I am putting together, they have different adversarial models, MPC adds the condition of collusion between parties i.e. ...
0
votes
1answer
65 views
What (Where) is the formal definition of Multiparty Computation? [closed]
I'm just curious where we can see a (original) formal definition of MPC.
What (Where) is the formal definition of MPC?
We have a bunch of tools to build a MPC protocol.
Is oblivious transfer (or OT-...
4
votes
1answer
67 views
Under what conditions is broadcast possible? (Cryptographically, and in the model of Maurer 2006)
In this paper, Ueli Maurer uses a very cool model to generalize a number of results about broadcast, secret sharing and secure multiparty computation. Rather than talking about an adversary being ...
1
vote
2answers
81 views
Multi-secret sharing (Packed secret sharing) - Some questions
In the publication - "Communication complexity of secure computation", I have encountered a small problem - on page 5 of the literature under the heading "Theorem 1" they have described a $(c,d; k,n)$ ...
1
vote
1answer
94 views
Is the simulation-based proof difficult and needed? [closed]
What is the role for simulation-based proof under the semi-honest model without considering malicious adversaries?
I agree with that a view of a some party is important to prove that a protocol is ...
0
votes
1answer
68 views
MPC on boolean circuits
I am reading about Yao's and GMW protocols and was wondering if there is any perfectly secure MPC protocol in the semi-honest setting, where the underlying circuit is a Boolean circuit (eg. n=3 and t=...
2
votes
1answer
54 views
Commitment in two party protocols
I have been reading Fast Secure Two-Party ECDSA Signing by Lindell, and I see that in key generating and signing (pages 9-10, especially visible from Figure 1), only the first party performs a ...
3
votes
1answer
88 views
Testing whether a secret value is zero without security bits (in SPDZ)
To test whether a secret value $[x]$ is zero, where $x \in [0,2^{k−1}]$, SPDZ uses the a based on the method of Catrina and de Hoogh [1].
This method requires to working on a field with modulus $p>...
0
votes
2answers
149 views
How to compute secure sum using secure multparty computation?
Suppose there are three voters $P$, $Q$ and $R$, and each will vote only on one candidate out of $X$, $Y$ or $Z$, with a 6 bit vote vector corresponding to $X
$, $Y$ and $Z$ respectively (with 2 bits ...
7
votes
3answers
144 views
How to determine the layers of a circuit?
In many cryptographic applications like Multiparty Computation (MPC) or Fully Homomorphic Encryption (FHE), you consider a function $f$ described by a circuit over some algebraic structure, typically ...
1
vote
1answer
46 views
In Multi-party communication, how can I find that one encrypted value is negative or not?
I'm using Pailier Cryptosystem as an additive homomorphic system in my scenario. I have two parties: Alice and Bob.
Alice has one pair of (SK, Pk) keys. She encryptes one value using her public key ...
2
votes
1answer
76 views
computing INV in boolean circuit for MPC
Is it feasible to generate an efficient MPC function that compute $a^{-1}$ for $a \in \mathbb{F_q}$, with Boolean circuit?
The naive way seems impossible since the depth of the computation might ...
2
votes
1answer
47 views
What is shared-input for Multi Party Computation?
I heard shared input.
For example, original values $x,y \in M$ are divided into pairs of shares $(x_1,x_2)$ and $(y_1, y_2)$ such that $x_1 + x_2 = x \text{ and } y_1 + y_2 = y$.
Each share is ...
1
vote
0answers
122 views
Multi-Party Offline Key Exchange Using Public and Private Keys
I hope the title already explains the problem I have in mind; but let me lay out some more details.
Given public-private key pairs $P_A, P_B, P_C, ... P_Z$, (first $3$ of which are owned by our usual ...
2
votes
1answer
44 views
complete functionality for fair multiparty computation
In this paper I found the statement "We reduce the fairness problem in MPC to the problem of fair decryption [...] Fair decryption was shown to be a complete functionality for fair MPC in [GIM+10]".
...
1
vote
1answer
74 views
Check if $a<b$ in a trustless scenario
Let's say Alice has access only to a value $a$ and Bob has access to both $a$ and $b$. I need ...
1
vote
0answers
43 views
Threshold Bitcoin signature scheme
Any advice would be appreciated:
It seems to me that using an uncomplicated combination of a shamir scheme and schnorr it's fairly trivial to have a threshold signature scheme.
I think it's also ...
3
votes
2answers
194 views
How to use Homomorphic encryption for secure computing Arctan() function?
In the multi-party communication(MPC), if partyA has the coordinate(x1 y1) and partyB has the coordiante(x2,y2), how two parties can securely compute Arctan((y1-y2)/(x1-x2)) without revealing their ...
4
votes
2answers
133 views
Atomic multi-party commitments
Alice and Bob publicly choose the messages $M_A$ and $M_B$ and independently sign them (Alice privately signs $M_A$, Bob signs $M_B$).
Now Alice and Bob are looking for a protocol that allows them to:...
4
votes
3answers
80 views
communication efficient private lookup
I have a scenario where a client has a private set and the server has a large public set, we would like an estimate of the intersection size or more specifically the percent of the private set covered ...
1
vote
1answer
253 views
AES encryption using MPC SPDZ protocol
I'm reading the article about SPDZ protocol for secure multiparty computation (and also improvements for offline phase like MASCOT).
However I'm thinking about practical application of SPDZ for AES ...
3
votes
1answer
125 views
Can we convert a pseudorandom function (PRF) to an Oblivious PRF (OPRF) through an Oblivious Transfer (OT) protocol?
I'm a software engineer, so I generally think in building blocks. And I'm not so familiar with the Math notation in Crytography, so I'll stick with function calls and function blueprints (which I ...
2
votes
1answer
95 views
How can Alice enable Bob to look-up values in a private map
I think this problem is similar to private set intersection, yet distinct in a way where:
Alice has an extensive Mapping of say id to name
id1 -> John Doe
id2 -> Jane Doe
id3 -> Edgar ...
4
votes
1answer
115 views
Secure Computation: Reactive Functionalities in the Hybrid Model for Standalone Security
A common approach to make (secure computation) protocol descriptions and proofs simpler is to describe them in a hybrid model, where the protocol in the real world has access to some auxiliary ideal ...
2
votes
2answers
90 views
Multiparty secret generation protocol
The goal is to create a secret S on a trusted server by having users A, B and C each send a private seed to the server, in such a way that any 2 of them can later recover S by resubmitting their ...
1
vote
1answer
68 views
Difference in the Powers of Simulator and Environment in Universal Composability
I know that in UC model, environment controls the real world adversaries but there is still a simulator wrapped around these real-world adversaries in the ideal world (which we sometimes collectively ...
7
votes
1answer
222 views
Extractability for Simulator in Malicious Model
It is sometimes required while proving the security of a protocol in the malicious setting that the simulator is able to extract the witness set of the adversary, who tends to be the prover of ...
0
votes
1answer
33 views
Private set supporting adding elements and proving elements exist
Is it possible to construct such a set that parties can
Add elements to the set without revealing the elements or knowing the elements presently in the set.
Proving to other parties that a certain ...
