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.

Filter by
Sorted by
Tagged with
1
vote
1answer
54 views

What does non-collusion assumption mean in server-aided protocol based on secret sharing?

Suppose $m$ clients split their own input into $n$ shares using additive secret sharing scheme (mod something). Then, each of the clients sends each share to each of $n$ external servers. After ...
2
votes
1answer
218 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 ...
6
votes
0answers
232 views

Share Conversion between Different Finite Fields

Let us have any linear secret sharing scheme (LSSS) that works on some field $Z_{p}$, where p is some prime or a power of a prime e.g., Shamir Secret Sharing, Additive secret Sharing. The problem at ...
0
votes
0answers
40 views

How to combine homomorphic encryption with secure multi-party computing?

I admit that I am a novice in cryptography, and I temporarily received a project that requires the use of homomorphic encryption technology and secure multiparty computing technology. Our team plans ...
0
votes
0answers
15 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
46 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 ...
0
votes
0answers
31 views

Simulation-based proof in a particular scenario

Suppose we have a two-party protocol in the semi-honest model, which is based on an additive homomorphic cryptosystem like Paillier.(P2 will generate the public and private key and publish the public ...
1
vote
0answers
316 views

Complexity of computing homomorphic encrypted matrix multiplication

Given two players $P_1 , P_2$ . In our setting $P_1$ poses two encrypted matrices $M_{1_{k \times k}},M_{2_{k \times k}}$ over field $F$, and the encryption has additive homomorphic property, over ...
3
votes
3answers
147 views

Group membership with unique anonymous claims

Is it possible to accomplish the following scheme? There is a Server (S) and many clients. Each client enrolls with S, exposing its real identity; S saves the real identity information in its ...
0
votes
0answers
29 views

Privacy by Simulation with Simulation-based Proof

In the semi-honest model for 2PC, why can we say that "if parties' views can be simulatable given the parties' inputs and outputs, then this implies that the parties learn nothing from the protocol ...
0
votes
1answer
74 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 ...
0
votes
2answers
52 views

Why this malicious behavior of corrupted sender isn't considered in malicious-secure OT?

I have read some oblivious transfer protocols, and I am confused about why they do not mention the malicious behavior that the corrupted sender may encrypt the wrong message $x_0'$ and $x_1'$ so that ...
2
votes
0answers
68 views

Multi-party computation with only 1 party?

MPC is $f(E_1(a), E_2(b)) = c$, where $E$ is encryption by different keys $k_1$ and $k_2$. Homomorphic encryption is $f(E_1(a)) = E_1(c)$, where the input and output are encrypted. I want $f(E_1(a)) ...
2
votes
0answers
63 views

Are there secure MPC schemes that support uneven load balancing between the parties?

In a scenario of which some of the parties have more data / compute power / trust reputation etc. than other parties - are there known methods to do secure multiparty computation with load balancing ...
3
votes
2answers
232 views

Concept Question for Secure Computation

I think this should be a simple question and I might be missing something fairly fundamental, but I haven't been able to find the answer. Basically, suppose there are parties $A$ and $B$. Party $A$ ...
2
votes
1answer
50 views

Security of secure two-party computation with a trusted dealer during offline phase?

In the SecureML paper, one can assume that two non-colluding servers can run secure two-party computation protocol based on secret sharing with the help of a third party (client). The client would ...
1
vote
1answer
59 views

Do garbled circuits run in constant time?

It seems like garbled circuits should not be input dependent, and hence should always run in constant time. Just wanted to clarify if this is true.
2
votes
0answers
27 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 ...
1
vote
0answers
51 views

Why is 2PC not used as any other primitive like DH? [closed]

Why is 2PC (2-Party Computation) not used as any other primitive like Diffie-Hellman? I'm not talking about the general secure computing, but some weaker security requirement or special case schemes. ...
2
votes
1answer
104 views

How many parties are needed to compute multiplication with BGW?

Let's say we have 3 parties and each one of them has a different secret number. Every party wants to learn the product of all the 3 numbers without learning about the other inputs. With the BGW ...
3
votes
0answers
90 views

Literature question on secure multiparty computation

Consider $N$ players and assume that a private channel between each pair of players is available. Player $i \in \{ 1, \ldots,N\}$ holds a secret $S_i$, which is a sequence of $B$ random bits. The ...
1
vote
1answer
52 views

Where was the stand-alone model for simulation-based MPC proposed first?

The stand-alone model and the UC model for simulation-based proofs in multiparty computation differ in the guarantees that they provide: The stand-alone model provides security under sequential ...
1
vote
1answer
79 views

Information Theoretic Oblivious Transfer?

Do we have information theoretic oblivious transfer protocols that are that can not be broken by a computationally unbounded attacker?
2
votes
1answer
57 views

half-gates in garble circuit

Recently I've been reading papers about MPC protocol, but when I read the paper by Zahur, S., M. Rosulek, and D. Evans. 2015 Two Halves Make a Whole- Reducing Data Transfer in Garbled Circuits Using ...
0
votes
0answers
27 views

A secure multi-party computation problem

The problem is expressed as follows: User $u_1$ owns $a_1$, user $u_2$ owns $a_2$, $\cdots$, user $u_n$ owns $a_n$, and Alice owns a vector $\vec b = \{b_1,b_2,\cdots,b_n\}$. Then, Alice want to ...
0
votes
0answers
27 views

How to create a generator for a $Q_3$ access structure?

I'm reading about access structures used for multiparty-computation from https://eprint.iacr.org/2004/245 and https://eprint.iacr.org/2000/037. My understand is that to actually use the access ...
1
vote
0answers
56 views

How Multi-party Computation works [closed]

I'm new to MPC. I was reading about it when I found an example that seemed to be trivial about how it works. In the picture below, the way X1 sends its data to X2 is by generating a huge random ...
2
votes
1answer
63 views

Difference between MPC and outsourced computation

I am reading an introductory paper on multi-party computation (MPC), and it makes a distinction between outsourced computation and MPC. In an outsourced computation, one party owns the data and ...
0
votes
0answers
37 views

Yao's millionaires problem - solution complexity

In his 82 paper, Yao gave two theorems regarding the maximum number of bits transmitted between Alice and Bob in order to privately compute a function $f$ on two private $n$-bit inputs $i$ and $j$. ...
0
votes
1answer
35 views

Order of OTs and commitments in Yao's Protocol for malicious adversaries

I was reading the book Efficient Secure Two-Party Protocols by Y. Lindell and C. Hazay. Page 92 of the book says This check is crucial and thus the order of first running the oblivious transfer and ...
0
votes
1answer
30 views

Constant number of rounds in Yao's Protocol for semi honest adversaries

According to me, every OT takes a constant number of rounds and since we have to do an OT for every input of one party, we'll have to do O(n) OTs which would correspond to O(n) rounds. But I have read ...
2
votes
1answer
100 views

Why BGW Multiplication Gate Works?

I am reading Pragmatic MPC (link) about the BGW protocol. I also cross-reference here (click on lecture link for slides) *The BGW Construction for the Information Theoretic Setting – Benny Pinkas I do ...
3
votes
2answers
2k views

Can I use Shamir's secret sharing scheme for multiplicative homomorphism for secure multiparty computation?

I would like to perform a dot product operation among $m$ parties using Shamir's $(m,m)$ secret sharing that is used for Secure Multiparty Computation. I am aware that Shamir's $(m,m)$ scheme is ...
7
votes
1answer
118 views

Limitations of boolean and arithmetic circuits

Much of modern cryptography is based around working with boolean or arithmetic circuits. For example in Multi-Party Computation the 'famous' results allow for the secure computation of any function ...
3
votes
1answer
118 views

Multiparty millionaire problem where members only know if they are the richest one

I'm looking for a generalisation of Yao's millionaire problem: $N$ parties want to know whether they are the richest one. If they are not, then they just know they are not the richest party - but do ...
1
vote
1answer
138 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 ...
1
vote
1answer
56 views

Securely computing functions over source code

I have been studying multi-party computation and want to start implementing it. I think it would be interesting to do this where one of the inputs (say party 1) is some source code, say a .py file. ...
0
votes
0answers
23 views

Secure Computation with TTP using Ring-LWE Homomorphic Encryption

I was working with secure outsourced computation for multi-party computation in which security is assured by ring-LWE based asymmetric homomorphic encryption in the semi-honest model. Is it feasible ...
1
vote
1answer
55 views

How can one prove correctness of shared secrets in secret sharing schemes?

Assume we are in a centralized secret sharing setting, where one party generates the shares, and distributes them to other parties. How can the distributor who creates the shares prove to the parties ...
0
votes
0answers
27 views

Commitment HIDING ⇒ Real≈Ideal in Multiple Coin Tossing Security

I'm reading /Multiple_Coin_Tossing_Security/P2_Corrupted/ ("Information Security and Cryptography" Theorem 6.7.4 starting from page 325) and after description of Simulator for P2, the author continues ...
3
votes
1answer
80 views

MPC and Secret Sharing in not Fully-Connected Network

I have an interest in applications of MPC and Secret Sharing. My point of view is from fields of distributed computing and Game Theory. I want to generalize some results to arbitrary network ...
9
votes
3answers
2k views

Examples of protocols that are insecure when run concurrently

I was reading Canetti00 Universally Composable security paper. The first page of introduction says that there are some MPC protocols and Zero knowledge protocols that are insecure under concurrent ...
1
vote
1answer
65 views

Why do we use addition and multiplication in GMW protocol

So i'm reading about secure computation and the GMW protocol. I don't understand why the protocol evaluates the addition and the multiplication ? Why not just the multiplication ? I didn't find any ...
1
vote
1answer
28 views

OT extensions paper: Why is $G_{m+1} \nleq m \times AND_B$?

I am reading this paper, in which Beaver shows how to take a small number of Oblivious Transfers (OTs) and extend them into an arbitrary number of OTs by implementing a pseudo-random number generator ...
1
vote
0answers
39 views

Question about the BCP cryptosystem

Is it possible to have a multiparty untrusted generation of the public parameters for the BCP cryptosystem (https://www.iacr.org/archive/asiacrypt2003/01_Session01/03_106/28940037.pdf), so that a ...
0
votes
0answers
84 views

Split TOTP/HOTP secret and generate pin without trusted dealer

Many site use time-based one time password (totp) as second factor auth method, such as aws. So we can split the totp secret and distribute each part to different party to achieve threshold login ( ...
-1
votes
1answer
47 views

Ensuring correctness property in multi-party protocols

Can you suggest mechanisms to ensure the correctness of the protocol output, against Active Adversaries in multi-party protocols. Specifically for a dishonest majority setting? I would like to have ...
5
votes
2answers
165 views

MPC protocols for high school kids

I was explaining MPC to a high school student. He was excited and asked me for some examples. The only ones that I could think of are by using garbled circuits. Are there some simple MPC protocols for ...
2
votes
1answer
71 views

Is it possible to represent max{a,b} as a binary polynomial?

For privacy-preserving comparison, is it possible to represent the function of $f(a,b)=\max\{a,b\}$ as a binary polynomial $p(a,b)$?
0
votes
0answers
53 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 2 3 4 5 6