We show that every NP relation that can be verified by a bounded-depth polynomial-sized circuit, or a bounded-space polynomial-time algorithm, has a computational zero-knowledge proof (with statistical soundness) with communication that is only additively larger than the witness length. Our construction relies only on the minimal assumption that one-way functions ... more >>>

The classical Reed-Muller codes over a finite field $\mathbb{F}_q$ are based on evaluations of $m$-variate polynomials of degree at most $d$ over a product set $U^m$, for some $d$ less than $|U|$. Because of their good distance properties, as well as the ubiquity and expressive power of polynomials, these codes ... more >>>

We present a polynomial-time pseudo-deterministic algorithm for constructing irreducible polynomial of degree $d$ over finite field $\mathbb{F}_q$. A pseudo-deterministic algorithm is allowed to use randomness, but with high probability it must output a canonical irreducible polynomial. Our construction runs in time $\tilde{O}(d^4 \log^4{q})$.

Our construction extends Shoup's deterministic algorithm ... more >>>