Cryptography

Questions tagged [multiparty-computation]

Ask Question

Multi-party computation (MPC) allows a set of parties, each with a private input, to securely and jointly perform any computation over their inputs.

371 questions
Newest
Active
Bountied
Unanswered
Filter by
Sorted by
Tagged with
1
vote
0answers
37 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 ...
0
votes
0answers
26 views

Communication cost of bit level calculation for boolean shares in MPC

Bit operations, such as bit addition/multiplication, are quite efficient from computation point of view. But in MPC, for example, if we use beaver triples for bit multiplication, 2 parties have to ...
3
votes
0answers
38 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. ...
1
vote
1answer
26 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' ...
0
votes
0answers
30 views

Static vs Adaptive security of a distributed cryptographic protocol

Let $n$ be the number parties in a distributed cryptographic protocol where an adversary can corrupt up to $n/3$ nodes in the network. Static Adversary: The set of corrupt nodes is fixed a priori. ...
1
vote
1answer
34 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$ ...
0
votes
0answers
11 views

Does libsnark support generation of a trusted setup/public parameters via MPC?

Secure Sampling of Public Parameters for Succinct Zero Knowledge Proofs states: We design, build, and evaluate a multi-party protocol for securely sampling encodings of random evaluations of certain ...
2
votes
1answer
29 views

Ideal Objects: Is there such a thing as an Ideal Functionality with persistent memory?

In general, proofs of security for secure Multiparty Computation are based on Ideal Functionalities. For instance, see Definition 4.1 of this Simulator tutorial. However, in a regular program in an ...
1
vote
1answer
37 views

Are semi-honest adversaries specific for MPC?

I know that in multiparty computation we may consider semi-honest or malicious adversaries. I can find papers that consider malicious adversaries, but the semi-honest term is only mentioned in MPC ...
0
votes
0answers
19 views

Centralized orchestration of Secret Shares for SMPC

With regards to SMPC with additive secret sharing, the protocol I am using involves a centralized node(the querier) orchestrating the share creation at client end via setting their random seeds. Now ...
1
vote
1answer
47 views

Can interactive zero-knowledge proof systems be implemented using secure two-party computation?

I am defining multi-party computation using the real-ideal paradigm (see A Pragmatic Introduction to Secure Multi-Party Computation). That is, for any successful attack on an MPC protocol in the real ...
4
votes
1answer
113 views

Are there different definitions of secure two-party computation?

While reading tutorials on two-party computation I encountered two (at least formally) different definitions of security (with semi-honest adversaries). What I want to know is whether these ...
1
vote
0answers
39 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
19 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
23 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-...
3
votes
0answers
32 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 ...
1
vote
1answer
49 views

Multi-party Millionaire's variant: how to find the highest number without revealing who holds it?

Let's say that $n$ honest-but-curious parties each hold a value $x_i$. The parties want to learn what is the maximum value across the parties $\{x_1...x_n\}$ without sharing their values (unless they ...
0
votes
0answers
48 views

Comparing two private values and extracting the ciphertext corresponding to the minimum value

How can I solve this problem: I have a directed graph of nodes that can be malicious and all of them have a private value. Consider a node "B" with private value "BPrivateValue = b&...
1
vote
1answer
109 views

MPC Definitions: UC-Security vs. Real-Ideal Simulation?

I consider the "standard" definition of maliciously-secure 2PC to be the simulation-based, ideal–real-world indistinguishability definition of e.g. Lindell's How to Simulate It [Lin17, ...
3
votes
0answers
59 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). ...
0
votes
0answers
34 views

Can a garbler "open" a circuit by "opening" only her input labels and AND tables?

I'm using the word "open" as in chapter 6 "Malicious Security" of Pragmatic MPC, i.e. to "open" the circuit is for the garbler to provide all the randomness used to ...
3
votes
1answer
67 views

How can malicious garbling compromise evaluator's input in Yao's garbled circuit

Suppose, we have a circuit which outputs a sha256 hash of a concatenation of Alice's input and Bob's input (where Alice is the garbler and Bob is the evaluator). I am trying to understand what methods ...
0
votes
0answers
49 views

What security does the BMR protocol offer against corruption?

I've been conducting some research into general-purpose MPC protocols and have been unable to pinpoint the exact security offered by the BMR protocol. The reference I've been using for the majority of ...
0
votes
0answers
31 views

Algorithm to ensure m people signed off on a task out of a group of N

I have a task that needs M people to approve out of a group of N. I can obviously implement it in software using a basic ECC signature mechanism. The code on the "server" can send request ...
2
votes
2answers
96 views

Statistical security parameter -> information theoretically secure

If a cryptographic protocol has a computational security parameter and a statistical security parameter, does this mean it is only computationally secure instead of information-theoretically secure? I ...
2
votes
1answer
41 views

non-interactive secure computation with a twist?

non-interactive secure computation (NISC) (introduced by this paper, followed by others) is a variant of secure 2PC/MPC defined as the following setting: Alice publishes an encrypted version of f(*, y)...
2
votes
1answer
67 views

Efficient private set intersection protocol for small sets

I need to implement a PSI that will be used on mobile devices to find mutual contacts. Assuming the set cardinality from both parties A and B are less than 1000, what would be the most efficient PSI ...
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 ...
0
votes
1answer
78 views

Joint distribution of RLWE samples

Assume we have the polynomial space $R_q$ defined as $R_q = Z_q/(X^n + 1)$. We draw samples $s_i \gets R_q$ uniformly at random. Additionally, we define the error distribution $\chi$ as a discrete ...
2
votes
2answers
103 views

Role of AND operation in FHE, MPC and ZK

Going through LowMC, one of the main advantage of it seems to be useful in Fully Homomorphic Encryption (FHE), Multi-party Computation (MPC) and Zero Knowledge (ZK) proofs. I have no idea about any of ...
1
vote
1answer
103 views

In simulation proofs of MPC, why could random oracle extract adversary's input?

I am learning the simulation-based security proofs in MPC, and have read the great tutorial "How to simulate it" by Prof. Lindell. Here's my understanding about why we need to "extract ...
2
votes
1answer
54 views

Real-world offline phase implementation in MPC setting

I've been reading up on various basic MPC primitives (multiplication, inversion, exponentiation and so on of secrets shared between multiple parties). One of the problems of implementing MPC in real-...
0
votes
0answers
39 views

Multiparty computation on circuits that perform group operations

I see that a lot of multiparty computation and garbling protocols are implemented for circuits like AES or SHA256. For my project, I would like to garble a circuit that performs some group operations ...
1
vote
2answers
88 views

Multiparty Computation to calculate addition of shares without revealling individual shares

I have $n$ persons, each holding a secret integer $x_i$ ($i$ from $1$ to $n$) and I'm looking for a way for them to jointly compute the sum of these secrets without revealing to each other their ...
2
votes
1answer
108 views

Should the field size in Shamir secret sharing scheme be larger than secret?

I'm playing around with implementing Shamir's secret sharing scheme in Kotlin. Here is implementation so far: ...
2
votes
0answers
50 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
79 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
60 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
26 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
73 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
47 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 ...
1
vote
1answer
60 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
41 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
83 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. ...
1
vote
1answer
59 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
175 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
24 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
45 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
53 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
117 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 ...

1
2 3 4 5
…
8

Your privacy

By clicking “Accept all cookies”, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy.