## Efficient NIZK Arguments via Parallel Verification of Benes Networks

Helger Lipmaa. Efficient NIZK Arguments via Parallel Verification of Benes Networks. In Michel Abdalla and Roberto De Prisco, editors, *SCN 2014*, volume 8642 of *Lecture Notes in Computer Science*, pages 416--434, Amalfi, Italy, September 3--5, 2014. Springer, Cham.

**File:**
[.pdf (526 KB)] __ recommended__.

**Abstract**:

We work within the recent paradigm, started by Groth (ASIACRYPT 2010), of
constructing short non-interactive zero knowledge arguments from a small
number basic arguments in a modular fashion. The main technical result of
this paper is a new permutation argument, by using product and shift
arguments of Lipmaa (2014) and a parallelizable variant of the Beneš
network. We use it to design a short non-interactive zero knowledge
argument for the NP-complete language CIRCUITSAT with Theta (n
log^{2} n) prover's computational complexity, where n is the size of the
circuit. The permutation argument can be naturally used to design direct
NIZK arguments for many other NP-complete languages..

**Keywords:** Beneš networks, modular NIZK arguments, perfect zero knowledge, product argument, shift argument, shuffle.

**Comment:**
Accepted. Abstract corresponds to prefinal version. The file corresponds to preliminary full version

**Authors:**

Page by Helger Lipmaa. Send your inqueries to `<helger.lipmaa>gmail.com`.