Efficient Modular NIZK Arguments from Shift and Product

摘要

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 NP-complete languages, Set-Partition, Subset-Sum and Decision-Knapsack, with constant communication, subquadratic prover's computation and linear verifier's computation.