Helger Lipmaa's publications

Efficient Modular NIZK Arguments from Shift and Product

Prastudy Fauzi, Helger Lipmaa and Bingsheng Zhang. Efficient Modular NIZK Arguments from Shift and Product. In Michel Abdalla, Cristina Nita-Rotaru and Ricardo Dahab, editors, CANS 2013, volume 8257 of Lecture Notes in Computer Science, pages 92--121, Paraty, Brazil, November 20--22, 2013. Springer, Heidelberg.

File: [.pdf (649 KB)] pdf recommended.

Abstract:

We propose a non-interactive product argument, that is more efficient than the one by Groth and Lipmaa, and a novel shift argument. We then use them to design several novel non-interactive zero-knowledge (NIZK) arguments. We obtain the first range proof with constant communication and subquadratic prover's computation. We construct NIZK arguments for $\mathbf{NP}$-complete languages, \textsc{Set-Partition}, \textsc{Subset-Sum} and \textsc{Decision-Knapsack}, with constant communication, subquadratic prover's computation and linear verifier's computation..

Keywords: FFT, multi-exponentiation, non-interactive zero knowledge, product argument, range argument, shift argument.


Comment: Abstract corresponds to prefinal version


Authors:

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