Paper 2015/336

Arithmetic Cryptography

Benny Applebaum, Jonathan Avron, and Chris Brzuska

Abstract

We study the possibility of computing cryptographic primitives in a fully-black-box arithmetic model over a finite field $\F$. In this model, the input to a cryptographic primitive (e.g., encryption scheme) is given as a sequence of field elements, the honest parties are implemented by arithmetic circuits which make only a black-box use of the underlying field, and the adversary has a full (non-black-box) access to the field. This model captures many standard information-theoretic constructions. We prove several positive and negative results in this model for various cryptographic tasks. On the positive side, we show that, under reasonable assumptions, computational primitives like commitment schemes, public-key encryption, oblivious transfer, and general secure two-party computation can be implemented in this model. On the negative side, we prove that garbled circuits, multiplicative-homomorphic encryption, and secure computation with low online complexity cannot be achieved in this model. Our results reveal a qualitative difference between the standard Boolean model and the arithmetic model, and explain, in retrospect, some of the limitations of previous constructions.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Major revision. ITCS 2015
DOI
10.1145/2688073.2688114
Contact author(s)
benny applebaum @ gmail com
History
2015-04-19: received
Short URL
https://ia.cr/2015/336
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/336,
      author = {Benny Applebaum and Jonathan Avron and Chris Brzuska},
      title = {Arithmetic Cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2015/336},
      year = {2015},
      doi = {10.1145/2688073.2688114},
      note = {\url{https://eprint.iacr.org/2015/336}},
      url = {https://eprint.iacr.org/2015/336}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.