Cryptology ePrint Archive: Report 2012/548
New Non-Interactive Zero-Knowledge Subset Sum, Decision Knapsack And Range Arguments
Prastudy Fauzi and Helger Lipmaa and Bingsheng Zhang
Abstract: We propose several new efficient non-interactive zero knowledge (NIZK) arguments in the common reference string model. The final arguments are based on two building blocks, a more efficient version of Lipmaa's Hadamard product argument from TCC 2012, and a novel shift argument. Based on these two arguments, we speed up the recent range argument by Chaabouni, Lipmaa and Zhang (FC 2012). We also propose efficient arguments for two NP-complete problems, subset sum and decision knapsack, with constant communication, quasilinear prover's computation and linear verifier's computation.
Category / Keywords: Decision knapsack, FFT, non-interactive zero knowledge, progression-free sets, range argument, subset sum.
Date: received 19 Sep 2012, last revised 13 Feb 2013
Contact author: helger lipmaa at gmail com,b zhang2009@gmail com
Available formats: PDF | BibTeX Citation
Version: 20130213:075202 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]