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