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.

106 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
9
votes
0answers
311 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
89 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\}$, ...
4
votes
0answers
75 views

Secure multiparty scheme in key (splitting) distribution among the players

Suppose that we have a game with $I$ players and each of them has a private secret say $e_i$. Every player wants to share her secret with the rest of the players but in such a way that she will not be ...
4
votes
0answers
124 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 ...
4
votes
0answers
119 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
144 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
252 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
113 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
42 views

Algorithmic game theory and protocol design for communication

There is a field of exchanging information that combines cryptography and game theory. I am interested in understanding this field, but it's a little complex for me. To begin with there is a paper of ...
3
votes
0answers
40 views

What is the cost of emulating ring arithmetic (say modulo $2^k$) over a prime finite field?

Several papers in, for example, the domain of Secure Multiparty Computation, are set in the context in which the computation domain is a finite field $\mathbb{F}_p$, while some more recent works (e.g. ...
3
votes
0answers
36 views

Security proof regarding a zero-knowledge counterexample that is secure in the stand-alone model but insecure in the UC model

Background The following zero-knowledge (ZK) counterexample is described in Canetti's work [Security and Composition of Cryptographic Protocols: A Tutorial, page 26] to show that there exists some ...
3
votes
0answers
68 views

Product of secrets in multi-secret sharing schemes (aka packed secret sharing schemes)

The question is related to the multi-secret sharing scheme described in the following paper: [FY92] Matthew K. Franklin, Moti Yung: Communication Complexity of Secure Computation (Extended Abstract). ...
3
votes
0answers
77 views

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

In a scenario in which some of the parties have more data / compute power / trust reputation (or other meaningful properties) than other parties - are there known methods to do secure multiparty ...
3
votes
0answers
137 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
51 views

Could anybody help by applying a secure multiparty secret sharing scheme?

Suppose that we have a multi-secret sharing scheme as it is described in the literature Let there be $I$ agents and say that $S$ is the space of the (uniform) random variables $s=(s_1,s_2,\cdots,s_I)\...
2
votes
0answers
67 views

No-dealer secret sharing scheme that prevents anonymous collaboration to reconstruct the secret

Is there a no-dealer secret sharing scheme that allows a threshold $k$ of $n$ parties (where $k<n$) to collaborate to reconstruct a secret, but in such a way that none of those $k$ parties are able ...
2
votes
0answers
46 views

For unequal set sizes in PSI: why should the party with fewer elements use cuckoo hash rather than simple hash?

Most PSI papers usually use hash-to-bin to improve the number of comparsons. For unequal set sizes in 2PSI, I have read CCS17, which designs a PSI protocol for unequal size. The party with fewer ...
2
votes
0answers
23 views

Example of exchanging information

I am searching for a simle model that can simulate the following procedure. Suppose that $i$ and $j$ are two agents that each one obtains her state dependets signal $s_i(\omega)$ and $s_j(\omega)$. ...
2
votes
0answers
45 views

RLWE like problem

Assume we have the polynomial space $R_q$ defined as $R_q = Z_q/(X^n + 1)$. Additionally, we define the error distribution $\chi$ as a discrete centred Gaussian bounded by $B$. Let $s \gets R_q$ be a ...
2
votes
0answers
54 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
85 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
73 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 ...
2
votes
0answers
59 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
74 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
32 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
68 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
35 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
191 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 ...
2
votes
0answers
92 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
160 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
80 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
37 views

How to define a cryptosystem when the encryption-decyrption scheme is based on Shamir's secret sharing scheme?

I would like to make a parallelism between Shamir's secret sharing scheme and how to define a cryptosystem where the encryption scheme is based on secret sharing. To begin with I do not know if there ...
1
vote
0answers
21 views

Secret sharing scheme combined with probability theory results?

As a sequel of my previous post I am writing a new one with respect to the secret sharing scheme. I will only cite here the answer because I want to make a question on it. $\textbf{Answer:}$ To be ...
1
vote
0answers
38 views

Could anyone provide any idea of such a protocol?

Could anybody provide the seminal paper and/or every specific manual in mathematics that describes a secure multiparty computation procedure, where the players will exchange encrypted messages (...
1
vote
0answers
22 views

Sharing information scheme of cryptography - operations in modular arithmetic

Taking into account my previous question here and the answer about the proposed encryption-decryption scheme. I am trying to understand how to make possible operations in modular arithmetic for a ...
1
vote
0answers
20 views

Is it possible to construct a 1-out-of-N OT with communication complexity smaller than the sender's whole input?

The constructions of 1-out-of-$n$ OT for $l$-bit strings I've seen had communication complexity proportional to $nl$. I wonder, is it possible to do OT with active security and transfer less than $O(...
1
vote
1answer
40 views

Examples of oblivious transfer protocols secure under stronger security assumptions than semi-honest model?

The question is basically stated on the title. I have done some introductory reading on Oblivious Transfer and most of them are secure in the semi-honest model. Are there any protocols that are secure ...
1
vote
0answers
38 views

Secure protocols with the dynamic programming solution concept?

Suppose that we have the usual problem of secure communication, where each of the $I$ agents have a private signal $s_1,s_2,\dots,I$ and they wish to compute any function $f(s_1,s_1,...,s_I)=(x_1,x_2,....
1
vote
0answers
55 views

MPC arithmetic circuit file and benchmark

For doing MPC over Boolean circuits (typically XOR, AND, INV gates over field of size 2), Boolean circuit files can be found online for a range of interesting functions (e.g. AES, SHA-256). These ...
1
vote
1answer
37 views

Is there a secure two party protocol that makes P1 (with x as input) gets rx+r' and P2 gets (r,r')

It should be a secure two party protocol against malicious adversary. P1's input is X in Zp* (p is a prime number); P2's input is nothing. P1's output is rX+r'. r,r' are random numbers from Zp* P2' ...
1
vote
1answer
47 views

Find the product of two sums via SMPC

I'm currently working on a distributed threshold DSA scheme that requires to find the product of two sums via secure multi-party computation. Specifically speaking, every one of $n$ parties $P_i$ ...
1
vote
0answers
50 views

Formal Verification for Multiparty Computation and Homomorphic Encryption?

I've recently found some work on the use of Formal Verification Software, like ProVerif for enclaves. I wonder is if its feasible to have something similar for MPC and Homomorphic Encryption and ...
1
vote
0answers
22 views

Is it possible to Publicly Query Privately Held Data with proof of Correctness?

We can secretly query inputs from a public DBs using what we call in the literature PIR. We can secretly query inputs from a privately held DB by means of Private Set Intersection (PSI). We can also ...
1
vote
0answers
25 views

Why a simulator can obtain a corrupted party's input to some subrountine ideal functionality $F$ "for free" in $F$-hybrid model?

In "How To Simulate It" (page 45, line 10), Lindell noted that, in the $f_{\textsf{zk}}$-hybrid model (where $f_{\textsf{zk}}$ denotes the ideal zero-knowledge functionality) in the stand-...
1
vote
0answers
32 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
93 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 ...
1
vote
1answer
61 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 ...
1
vote
0answers
31 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 ...