Software Investigate

New Non-Interactive Zero-Knowledge Subset Sum, Decision Knapsack and Range Arguments

Download now Free registration required

Executive Summary

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.

  • Format: PDF
  • Size: 617 KB