Paper 2023/870
Additive Randomized Encodings and Their Applications
Abstract
Addition of $n$ inputs is often the easiest nontrivial function to compute securely. Motivated by several open questions, we ask what can be computed securely given only an oracle that computes the sum. Namely, what functions can be computed in a model where parties can only encode their input locally, then sum up the encodings over some Abelian group $\G$, and decode the result to get the function output. An *additive randomized encoding* (ARE) of a function $f(x_1,\ldots,x_n)$ maps every input $x_i$ independently into a randomized encoding $\hat x_i$, such that $\sum_{i=1}^n$ $\hat x_i$ reveals $f(x_1,\ldots,x_n)$ and nothing else about the inputs. In a *robust* ARE, the sum of any subset of the $\hat x_i$ only reveals the residual function obtained by restricting the corresponding inputs. We obtain positive and negative results on ARE. In particular: * Informationtheoretic ARE. We fully characterize the 2party functions $f:X_1\times X_2\to\{0,1\}$ admitting a perfectly secure ARE. For $n\ge 3$ parties, we show a useful ``capped sum'' function that separates statistical security from perfect security. * Computational ARE. We present a general feasibility result, showing that *all functions* can be computed in this model, under a standard hardness assumption in bilinear groups. We also describe a heuristic latticebased construction. * Robust ARE. We present a similar feasibility result for {\em robust} computational ARE based on ideal obfuscation along with standard cryptographic assumptions. We then describe several applications of ARE and the above results. * Under a standard cryptographic assumption, our computational ARE schemes imply the feasibility of general noninteractive secure computation in the shuffle model, where messages from different parties are shuffled. This implies a general utilitypreserving compiler from differential privacy in the central model to computational differential privacy in the (nonrobust) shuffle model. * The existence of informationtheoretic {\em robust} ARE implies "bestpossible" informationtheoretic MPC protocols (Halevi et al., TCC 2018) and degree2 multiparty randomized encodings (Applebaum et al., TCC 2018). This yields new positive results for specific functions in the former model, as well as a simple unifying barrier for obtaining negative results in both models.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 A major revision of an IACR publication in CRYPTO 2023
 Keywords
 Randomized EncodingSecure MPC
 Contact author(s)

shaih @ alum mit edu
yuval ishai @ gmail com
eyal kushilevitz @ gmail com
talr @ seas upenn edu  History
 20230612: approved
 20230607: received
 See all versions
 Short URL
 https://ia.cr/2023/870
 License

CC BY
BibTeX
@misc{cryptoeprint:2023/870, author = {Shai Halevi and Yuval Ishai and Eyal Kushilevitz and Tal Rabin}, title = {Additive Randomized Encodings and Their Applications}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/870}, year = {2023}, url = {https://eprint.iacr.org/2023/870} }