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
Abstract
Addition of 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 , and decode the result to get the function output.
An *additive randomized encoding* (ARE) of a function maps every input independently into a randomized encoding , such that reveals and nothing else about the inputs. In a *robust* ARE, the sum of any subset of the 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 admitting a perfectly secure ARE. For 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.
@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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org
does not use cookies or embedded third party content.