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
0
votes
0answers
10 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
28 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
34 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
18 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
40 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 ...
3
votes
1answer
107 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
36 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
15 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 ...
0
votes
0answers
20 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-...
2
votes
0answers
27 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 ...
0
votes
1answer
48 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
43 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
51 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
57 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
63 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
47 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
79 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
61 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
67 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
98 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
93 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
53 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
87 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
103 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
49 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
58 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
68 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
45 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 ...
0
votes
1answer
55 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
76 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
55 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
172 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
52 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
115 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 ...
0
votes
1answer
59 views

Secret Sharing Domain Questions

all, I have a very fundamental question on Secret Sharing schemes such as SPDZ families. As far as I can see for now, SS schemes always assume a certain variable range. For example, suppose the bit ...
2
votes
0answers
58 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 ...
0
votes
1answer
37 views

LSB extraction in MPC: Doubts about correctness

I have doubts about whether the protocol below for LSB extraction (denoted Mod2) from the paper Improved Primitives for Secure Multiparty Integer Computation is correct. Clarifications will be ...
2
votes
1answer
60 views

How (generally) do modern schemes deal with an adversary with the capacity to either instantly, or over time, corrupt a majority of parties

I'm curious about the honest minority case and what cryptographers have and are currently using to get around this. My motivation is primarily the MPC space, but I'm sure there are other subfields ...
1
vote
1answer
60 views

Simulating a joint distribution of an *almost* deterministic function

The following is in the context of secure MPC. Suppose that there is a functionality $f(x,y)$ which outputs 'answer' with probability $1-\textrm{negl}(n)$ for some security parameter $n$, and 'other ...
2
votes
1answer
67 views

Boolean circuit: can the output wire of a gate be used by many different gates in the next layer?

There are two typical secure multiparty computation paradigms using boolean circuits, namely garbled circuit and secret-sharing-based boolean computation. It is well-known that garbled circuits can be ...

1
2 3 4 5
8