Paper 2023/870

Additive Randomized Encodings and Their Applications

Shai Halevi, Algorand Foundation
Yuval Ishai, Technion – Israel Institute of Technology
Eyal Kushilevitz, Technion – Israel Institute of Technology
Tal Rabin, University of Pennsylvania

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: * Information-theoretic ARE. We fully characterize the 2-party 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 lattice-based 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 non-interactive secure computation in the shuffle model, where messages from different parties are shuffled. This implies a general utility-preserving compiler from differential privacy in the central model to computational differential privacy in the (non-robust) shuffle model. * The existence of information-theoretic {\em robust} ARE implies "best-possible" information-theoretic MPC protocols (Halevi et al., TCC 2018) and degree-2 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.

Available format(s)
Publication info
A major revision of an IACR publication in CRYPTO 2023
Randomized EncodingSecure MPC
Contact author(s)
shaih @ alum mit edu
yuval ishai @ gmail com
eyal kushilevitz @ gmail com
talr @ seas upenn edu
2023-06-12: approved
2023-06-07: received
See all versions
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.