Helger Lipmaa's publications

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.


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 log2 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


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