6 results sorted by ID
On the (Im)possibility of Distributed Samplers: Lower Bounds and Party-Dynamic Constructions
Damiano Abram, Maciej Obremski, Peter Scholl
Cryptographic protocols
Distributed samplers, introduced by Abram, Scholl and Yakoubov (Eurocrypt ’22), are a one-round, multi-party protocol for securely sampling from any distribution. We give new lower and upper bounds for constructing distributed samplers in challenging scenarios. First, we consider the feasibility of distributed samplers with a malicious adversary in the standard model; the only previous construction in this setting relies on a random oracle. We show that for any UC-secure construction in the...
Security-Preserving Distributed Samplers: How to Generate any CRS in One Round without Random Oracles
Damiano Abram, Brent Waters, Mark Zhandry
Cryptographic protocols
A distributed sampler is a way for several mutually distrusting parties to non-interactively generate a common reference string (CRS) that all parties trust. Previous work constructs distributed samplers in the random oracle model, or in the standard model with very limited security guarantees. This is no accident, as standard model distributed samplers with full security were shown impossible.
In this work, we provide new definitions for distributed samplers which we show achieve...
Threshold Garbled Circuits and Ad Hoc Secure Computation
Michele Ciampi, Vipul Goyal, Rafail Ostrovsky
Cryptographic protocols
Garbled Circuits (GCs) represent fundamental and powerful tools in cryptography, and many variants of GCs have been considered since their introduction. An important property of the garbled circuits is that they can be evaluated securely if and only if exactly 1 key for each input wire is obtained: no less and no more.
In this work we study the case when: 1) some of the wire-keys are missing, but we are still interested in computing the output of the garbled circuit and 2) the evaluator of...
Multiparty Reusable Non-Interactive Secure Computation
Fabrice Benhamouda, Huijia Lin
Cryptographic protocols
Reducing interaction in Multiparty Computation (MPC) is a highly desirable goal in cryptography. It is known that 2-round MPC can be based on the minimal assumption of 2-round Oblivious Transfer (OT) [Benhamouda and Lin, Garg and Srinivasan, EC 2018], and 1-round MPC is impossible in general. In this work, we propose a natural ``hybrid'' model, called \textbf{multiparty reusable Non-Interactive Secure Computation Market (mrNISC)}. In this model, parties publish encodings of their private...
The Complexity of Multiparty PSM Protocols and Related Models
Amos Beimel, Eyal Kushilevitz, Pnina Nissim
Cryptographic protocols
We study the efficiency of computing arbitrary k-argument functions in the Private Simultaneous Messages (PSM) model of (Feige et al. STOC'94, Ishai and Kushilevitz ISTCS'97). This question was recently studied by (Beimel et al. TCC'14), in the two-party case (k = 2). We tackle this question in the general case of PSM protocols for k > 2 parties. Our motivation is two-fold: On one hand, there are various applications (old and new) of PSM protocols for constructing other cryptographic...
Non-Interactive Secure Multiparty Computation
Amos Beimel, Ariel Gabizon, Yuval Ishai, Eyal Kushilevitz, Sigurd Meldgaard, Anat Paskin-Cherniavsky
Cryptographic protocols
We introduce and study the notion of non-interactive secure multiparty computation (NIMPC). An NIMPC protocol for a function $f(x_1,\ldots,x_n)$ is specified by a joint probability distribution $R=(R_1,\ldots,R_n)$ and local encoding
functions $Enc_i(x_i,R_i)$, $1 <= i <= n$. Given correlated
randomness $(R_1,\ldots,R_n)\in_R R$, each party $P_i$, using its input $x_i$ and its randomness $R_i$, computes the message $m_i= Enc_i(x_i,R_i)$. The messages $m_1,\ldots,m_n$ can be used to decode...
Distributed samplers, introduced by Abram, Scholl and Yakoubov (Eurocrypt ’22), are a one-round, multi-party protocol for securely sampling from any distribution. We give new lower and upper bounds for constructing distributed samplers in challenging scenarios. First, we consider the feasibility of distributed samplers with a malicious adversary in the standard model; the only previous construction in this setting relies on a random oracle. We show that for any UC-secure construction in the...
A distributed sampler is a way for several mutually distrusting parties to non-interactively generate a common reference string (CRS) that all parties trust. Previous work constructs distributed samplers in the random oracle model, or in the standard model with very limited security guarantees. This is no accident, as standard model distributed samplers with full security were shown impossible. In this work, we provide new definitions for distributed samplers which we show achieve...
Garbled Circuits (GCs) represent fundamental and powerful tools in cryptography, and many variants of GCs have been considered since their introduction. An important property of the garbled circuits is that they can be evaluated securely if and only if exactly 1 key for each input wire is obtained: no less and no more. In this work we study the case when: 1) some of the wire-keys are missing, but we are still interested in computing the output of the garbled circuit and 2) the evaluator of...
Reducing interaction in Multiparty Computation (MPC) is a highly desirable goal in cryptography. It is known that 2-round MPC can be based on the minimal assumption of 2-round Oblivious Transfer (OT) [Benhamouda and Lin, Garg and Srinivasan, EC 2018], and 1-round MPC is impossible in general. In this work, we propose a natural ``hybrid'' model, called \textbf{multiparty reusable Non-Interactive Secure Computation Market (mrNISC)}. In this model, parties publish encodings of their private...
We study the efficiency of computing arbitrary k-argument functions in the Private Simultaneous Messages (PSM) model of (Feige et al. STOC'94, Ishai and Kushilevitz ISTCS'97). This question was recently studied by (Beimel et al. TCC'14), in the two-party case (k = 2). We tackle this question in the general case of PSM protocols for k > 2 parties. Our motivation is two-fold: On one hand, there are various applications (old and new) of PSM protocols for constructing other cryptographic...
We introduce and study the notion of non-interactive secure multiparty computation (NIMPC). An NIMPC protocol for a function $f(x_1,\ldots,x_n)$ is specified by a joint probability distribution $R=(R_1,\ldots,R_n)$ and local encoding functions $Enc_i(x_i,R_i)$, $1 <= i <= n$. Given correlated randomness $(R_1,\ldots,R_n)\in_R R$, each party $P_i$, using its input $x_i$ and its randomness $R_i$, computes the message $m_i= Enc_i(x_i,R_i)$. The messages $m_1,\ldots,m_n$ can be used to decode...