Paper 2024/249

Robust Additive Randomized Encodings from IO and Pseudo-Non-linear Codes

Nir Bitansky, Tel Aviv University
Sapir Freizeit, Tel Aviv University

Additive randomized encodings (ARE), introduced by Halevi, Ishai, Kushilevitz, and Rabin (CRYPTO 2023), reduce the computation of a k-party function $f (x_1, . . . , x_k )$ to locally computing encodings $\hat{x}_i$ of each input xi and then adding them together over some Abelian group into an output encoding $\hat{y} = ∑ \hat{x}_i$, which reveals nothing but the result. In robust ARE (RARE) the sum of any subset of $\hat{x}_i$, reveals only the residual function obtained by restricting the corresponding inputs. The appeal of (R)ARE comes from the simplicity of the online part of the computation involving only addition, which yields for instance non-interactive multi-party computation in the shuffle model where messages from different parties are anonymously shuffled. Halevi, Ishai, Kushilevitz, and Rabin constructed ARE from standard assumptions and RARE in the ideal obfuscation model, leaving open the question of whether RARE can be constructed in the plain model. We construct RARE in the plain model from indistinguishability obfuscation, which is necessary, and a new primitive that we call pseudo-non-linear codes. We provide two constructions of this primitive assuming either Learning with Errors or Decision Diffie Hellman. A bonus feature of our construction is that it is online succinct. Specifically, encodings $\hat{x}_i$ can be decomposed to offline parts $\hat{z}_i$ that can be sent directly to the evaluator and short online parts $\hat{g}_i$ that are added together.

Available format(s)
Cryptographic protocols
Publication info
Robust Additive Randomized EncodingsARERARERandomized EncodingsIOPseudo non linear codes
Contact author(s)
nbitansky @ gmail com
sapirfreizeit @ gmail com
2024-05-30: last of 2 revisions
2024-02-15: received
See all versions
Short URL
No rights reserved


      author = {Nir Bitansky and Sapir Freizeit},
      title = {Robust Additive Randomized Encodings from {IO} and Pseudo-Non-linear Codes},
      howpublished = {Cryptology ePrint Archive, Paper 2024/249},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.