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.

58 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
7
votes
0answers
268 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 ...
6
votes
0answers
82 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\}$, ...
5
votes
0answers
50 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 ...
4
votes
0answers
109 views

Multi-party computation with untrusted nodes?

Let $L = [b_1, \dots, b_k]$ be a list of blocks of a file. I want to compute the function $f = h(g(b_1), \dots, g(b_k))$ on $N$ untrusted nodes such that: Anyone can be reasonable convinced (with ...
4
votes
0answers
127 views

An MPC protocol from Elgamal is a good solution a homomorphic multiplication?

I want to compute a multiplication between many secret values and then distribute the result to everyone involved. For this, I thought about an MPC protocol built from Threshold Homomorphic Elgamal. ...
4
votes
0answers
237 views

How can I implement decryption for NTRU homomorphic encryption scheme?

I have come across this paper On-the-fly multiparty computation via on-the-cloud Multikey from Fully Homomorphic Encryption by Lopez-Alt et al., where authors describe a NTRU-based homomorphic ...
4
votes
0answers
110 views

How about a homomorphic integer sorting in a MPC context?

I want to implement the ATV-FHE scheme as described by Adriana López-Alt, Eran Tromer, Vinod Vaikuntanathan: On-the-Fly Multiparty Computation on the Cloud via Multikey Fully Homomorphic Encryption (...
3
votes
0answers
104 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 ...
2
votes
0answers
48 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 ...
2
votes
0answers
70 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
64 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 ...
2
votes
0answers
28 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
0answers
61 views

Necessity of Randomness when Privately Computing a Sum

I want to show that no 1-private deterministic protocol exists for calculating a sum of $n \geq 3$ parties (within the realms of Perfect rather than Computational Security). I'm having trouble showing ...
2
votes
0answers
25 views

Computationally secure ORAMs with O(lg n)-bit words: shouldn't they fail with $n^{-O(1)}$ probability?

Virtually all "hierarchical" Oblivious RAMs use "cryptographically secure" hash functions to determine the position of an item at a given level; and implicitly assume (as can be evinced from the cost ...
2
votes
0answers
89 views

Is there any OPRF (oblibivious pseudo random random functions) between one receiver (1 input) and n senders (n inputs)? any references to read?

I am looking for some references for multi-party / distributed Oblivious pseudorandom Functions. I found two party OPRF protocols between a sender $S$ and a receiver $R$ for securely computing a ...
2
votes
0answers
86 views

Are there any information-theoretically secure verifiable secret sharing protocols with t=n?

Disregarding matters such as efficiency and round complexity, can verifiable secret sharing be done in a way such that the secret cannot be decoded unless you have all n shares, and that this ...
2
votes
0answers
145 views

How does threshold decryption with secretly shared exponents actually work?

Imagine the case where you have a sufficiently large finite field (or any multiplicative field for that matter) $\mathbb{Z}_{p}$ where p is some large prime. Now, I have a number $g \in \mathbb{Z}_{p}...
2
votes
0answers
77 views

Can we use a pseudorandom function in both models of a simulation based proof?

Assume in the real model a party blinds a fixed element $b$ as: $v_i=r_i\cdot b$, where $r_i$ is a output of pseudorandom function. So we give $v_i$ to a semi-honest adversary. Now we want to sketch ...
2
votes
0answers
94 views

Why do authors execute a leakage resilient election protocol inside a leak-free phase?

In the paper "Multiparty Computation Secure Against Continual Memory Leakage", on page 1241 (that's page 7 of the PDF) under section 2.3, the authors discuss "The Election Protocol" that they use to ...
2
votes
0answers
76 views

Can you clarify the proof that secure LR-two party protocols do not exist?

In the paper “Multiparty Computation Secure Against Continual Memory Leakage” on pg. 1237, the footnote #1 discuss why it is not possible to construct a leakage resilient two-party protocol. But I'm ...
1
vote
1answer
28 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 ...
1
vote
0answers
52 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
0answers
44 views

What's the difference between compromise and corruption in MPC?

What is the difference between corruption and compromise? Are Compromising a user and ...
1
vote
0answers
54 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, ...
1
vote
0answers
49 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 ...
1
vote
0answers
20 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 ...
1
vote
0answers
49 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 ...
1
vote
0answers
80 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
0answers
252 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 ...
1
vote
0answers
82 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 ...
1
vote
0answers
94 views

Optimized Random-OT Security in Standard Model

I was going through the paper - " Efficient Oblivious Transfer and Extensions for Faster Secure Computation" by Asharov et al. where the authors propose an optimized OT protocol along with a Random-OT ...
1
vote
0answers
32 views

Secure multiparty computation connectivity bound

I read some papers which studied the relation between the fault tolerance in secure multiparty computation and the connectivity of the underlying communication graph. Here I consider information-...
1
vote
0answers
143 views

Rewinding techniques with some examples

I'm aware of these posts: What is a "rewinding argument"? Random oracle model proofs and programmability But I think, some concrete examples are missing. I need to know how exactly ...
1
vote
0answers
189 views

Homomorphic encryption - addition for more than two parties

I have just found out about the homomorphic encryption and I was wondering how is it possible to perform an addition for more than two parties? More concretely, I want to have several parties $P_i$, ...
1
vote
0answers
129 views

What SMPC protocols make use only of additive secret sharing?

In Appendix G of the Hawk paper, where it talks about financially fair SFE, it mentions that it's possible to run a SMPC protocol where, at the end, each party has a share of their own output y, and a ...
1
vote
0answers
372 views

Create digital signature with input from multiple users?

Suppose that users A,B and C want to create a digital signature together. The users do not trust each other so, they need to create a signature that receives input from all of them. The best way I ...
1
vote
0answers
237 views

Design a simplified version of the protocol for secure addition

To learn secure multiparty communication, I want to design a simplified protocol for secure addition, where instead of receiving two (random) numbers in $Z_p$, a player only receives a single (random) ...
1
vote
0answers
156 views

Whcih one is computationally more expensive: Zero knowledge proof or cut-and-choose

As we know, in order to have multi-party protocol secure against the malicious parties, researchers usually utilise the standard techniques such as zero-knowledge proofs or cut-and-choose technique. ...
1
vote
0answers
425 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 ...
1
vote
0answers
59 views

What is the right tool to MPC linear equations system

Given two parties who have private inputes Player 1 - $X_1,...X_n$ Player 2 - $Y_1,...Y_n$ We want to compute a solution to a linear system equation: $f_1(X_1,...X_n,...Y_1,...Y_n) +h_1(X_1,......
1
vote
0answers
123 views

Does using a verifiable secret sharing scheme ensure robustness of a protocol if it is secure under the semi-honest adversarial model

Consider a protocol $\pi$ which uses a linear secret sharing scheme like that of Shamir secret sharing. Further assume that the protocol $\pi$ has been proven to be secure (correctness and privacy) ...
1
vote
0answers
29 views

Proving for a single input vs several inputs. Is there any difference?

I am working on a new protocol for pattern matching. While defining the ideal functionality, it is possible to say: Alice sends $p$ and Bob sends $T$ to the ideal functionality. i.e. searching for ...
1
vote
0answers
37 views

Why does a joint leakage MPC protocol not directly apply to a disjoint leakage requirement?

In the paper "Multiparty Computation Secure Against Continual Memory Leakage" on pg. 1239 the footnote at the bottom points out the difference between $joint$ leakage and $disjoint$ leakage. The ...
0
votes
1answer
28 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 ...
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 ...
0
votes
0answers
30 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 ...
0
votes
0answers
109 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
59 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
0answers
39 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 ...