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
0answers
32 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,....
0
votes
0answers
13 views

MPC approach to compute +/- 1 times a variable

In an MPC protocol, does anyone know a better way to multiply a var p by epsilon in {-1,1} than using a beaver triple ? (I am thinking about doing it in a SPDZ like protocol such as Overdrive)
0
votes
0answers
23 views

Secure multiparty protocols proof and why is a necessary condition?

Is there a strict proof for secure multiparty protocols? What do they serve? I mean some have shown the existence for such protocols, but can I use them in order to substitute a mediator in game ...
2
votes
0answers
19 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)$. ...
3
votes
0answers
32 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
1answer
63 views

BGW multiplication by Gennaro et al.: Why does H(x) have exactly degree t and why is $2t + 1 \le n$ necessary?

With this question I am referring to the BGW multiplication by Gennaro et al (PDF here). The multiplication is described on the 4th page. (Another source for me was "A pragmatic Introduction to ...
1
vote
0answers
49 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
29 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
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. ...
1
vote
1answer
36 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
35 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
46 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
13 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
31 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
41 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
21 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
48 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
120 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
41 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
20 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
24 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
33 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
51 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
49 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
131 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
80 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
50 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
124 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
42 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
71 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
82 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
111 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
107 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
63 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
89 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
112 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
52 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
83 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
65 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
29 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
80 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
53 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
63 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
42 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
91 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
2 3 4 5
8