# Zero-Knowledge Proofs for Finite Field Arithmetic or: Can Zero-Knowledge be for Free?

## DOI:

https://doi.org/10.7146/brics.v4i27.18953## Abstract

We present zero-knowledge proofs and arguments for arithmetic circuits over finite prime fields, namely given a circuit, show in zero-knowledge that inputs can be selected leading to a given output. For a field GF(q), where q is an n-bit prime, acircuit of size O(n), and error probability 2^−n, our protocols require communication of O(n^2) bits. This is the same worst-cast complexity as the trivial (non zero-knowledge)

interactive proof where the prover just reveals the input values. If the circuit involves n multiplications, the best previously known methods would in general require communication

of Omega(n^3 log n) bits.

Variations of the technique behind these protocols lead to other interesting applications.

We first look at the Boolean Circuit Satisfiability problem and give zero-knowledge proofs and arguments for a circuit of size n and error probability 2^−n in which there is an interactive preprocessing phase requiring communication of O(n^2)

bits. In this phase, the statement to be proved later need not be known. Later the prover can non-interactively prove any circuit he wants, i.e. by sending only one message, of size O(n) bits.

As a second application, we show that Shamirs (Shens) interactive proof system for the (IP-complete) QBF problem can be transformed to a zero-knowledge proof

system with the same asymptotic communication complexity and number of rounds. The security of our protocols can be based on any one-way group homomorphism with a particular set of properties. We give examples of special assumptions sufficient for this, including: the RSA assumption, hardness of discrete log in a prime order group, and polynomial security of Die-Hellman encryption. We note that the constants involved in our asymptotic complexities are small enough for our protocols to be practical with realistic choices of parameters.

## Downloads

## Published

1997-01-27

## How to Cite

*BRICS Report Series*,

*4*(27). https://doi.org/10.7146/brics.v4i27.18953

## Issue

## Section

Articles

## License

Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.