New Non-Interactive Zero-Knowledge Subset Sum, Decision Knapsack and Range Arguments
The authors propose two basic NIZK arguments, one for Hadamard product of two vectors and another one for a shift of a vector. The first argument is based on the corresponding argument of Lipmaa (TCC 2012), but makes use of Fast Fourier Transform and Pippenger's multi-exponentiation algorithm to achieve quasilinear (as opposed quadratic) computational complexity. The shift argument seems to be novel. Based on the new basic arguments, they propose a NIZK argument for subset sum. This seems to be the only known (direct) sublinear NIZK argument for some other NP-complete language than Circuit-SAT. Moreover, it is significantly more efficient than the known sublinear Circuit-SAT arguments by Groth (Asiacrypt 2010) and Lipmaa.