## Arithmetic Cryptography

by Benny Applebaum, Jonathan Avron, and Christina Brzuska.

#### Oded's comments

I find this new research direction interesting and likewise
both for the positive results and for the negative results.
The positive results offer an abstraction of ideas underlying
cryptographic schemes as well as their transportation between
different algebras. The negative results shed light on various
issues regarding the design of cryptographic schemes.
In particular, ``arithmetization'' (i.e., the existence
of a matching arithmetic schemes) emerges as a new barrier
(i.e., as an alternative to black-box reductions)
that may explain differences among cryptographic primitives.

#### The original 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 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, 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.

Back to
list of Oded's choices.