Paper 2014/960
NonInteractive Secure Multiparty Computation
Amos Beimel, Ariel Gabizon, Yuval Ishai, Eyal Kushilevitz, Sigurd Meldgaard, and Anat PaskinCherniavsky
Abstract
We introduce and study the notion of noninteractive 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 $f(x_1,\ldots,x_n)$. For a set $T\subseteq[n]$, the protocol is said to be $T$robust if revealing the messages $(Enc_i(x_i,R_i))_{i\not\in T}$ together with the randomness $(R_i)_{i\in T}$ gives the same information about $(x_i)_{i\not\in T}$ as an oracle access to the function $f$ restricted to these input values. Namely, a coalition $T$ can learn no more than the restriction of $f$ fixing the inputs of uncorrupted parties, which, in this noninteractive setting, one cannot hope to hide. For $0\le t\le n$, the protocol is $t$robust if it is $T$robust for every $T$ of size at most $t$ and it is fully robust if it is $n$robust. A 0robust NIMPC protocol for $f$ coincides with a protocol in the private simultaneous messages model of Feige et al.~(STOC 1994). In the setting of computational (indistinguishabilitybased) security, fully robust NIMPC is implied by multiinput functional encryption, a notion that was recently introduced by Goldwasser et al. (Eurocrypt 2014) and realized using indistinguishability obfuscation. We consider NIMPC in the informationtheoretic setting and obtain unconditional positive results for some special cases of interest: Group products. For every (possibly nonabelian) finite group $G$, the iterated group product function $f(x_1,\ldots,x_n)=x_1x_2\ldots x_n$ admits an efficient, fully robust NIMPC protocol. Small functions. Every function $f$ admits a fully robust NIMPC protocol whose complexity is polynomial in the size of the input domain (i.e., exponential in the total bitlength of the inputs). Symmetric functions. Every symmetric function $f:\X^n\to \Y$, where $\X$ is an input domain of constant size, admits a $t$robust NIMPC protocol of complexity $n^{O(t)}$. For the case where $f$ is a $w$outof$n$ threshold function, we get a fully robust protocol of complexity $n^{O(w)}$. On the negative side, we show that natural attempts to realize NIMPC using private simultaneous messages protocols and garbling schemes from the literature fail to achieve even 1robustness.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 A major revision of an IACR publication in CRYPTO 2014
 Keywords
 secure multiparty computationobfuscationprivate simultaneous messages protocolsrandomized encoding of functionsgarbling schemesmultiinput functional encryption
 Contact author(s)
 amos beimel @ gmail com
 History
 20141125: received
 Short URL
 https://ia.cr/2014/960
 License

CC BY
BibTeX
@misc{cryptoeprint:2014/960, author = {Amos Beimel and Ariel Gabizon and Yuval Ishai and Eyal Kushilevitz and Sigurd Meldgaard and Anat PaskinCherniavsky}, title = {NonInteractive Secure Multiparty Computation}, howpublished = {Cryptology ePrint Archive, Paper 2014/960}, year = {2014}, note = {\url{https://eprint.iacr.org/2014/960}}, url = {https://eprint.iacr.org/2014/960} }