Arithmetic Cryptography

Benny Applebaum*, Jonathan Avron, Chris Brzuska

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

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 that 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 coding-related intractability 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, additively 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.

Original languageEnglish
Article number10
Number of pages74
JournalJournal of the ACM
Volume64
Issue number2
DOIs
Publication statusPublished - Jun 2017
MoE publication typeA1 Journal article-refereed

Keywords

  • Arithmetic complexity
  • cryptography
  • secure computation
  • learning with noise
  • HOMOMORPHIC ENCRYPTION
  • MULTIPARTY COMPUTATION
  • RANDOMIZING POLYNOMIALS
  • OBLIVIOUS TRANSFER
  • LOWER-BOUNDS
  • ALGORITHMS
  • COMPLEXITY
  • SECRET

Cite this