7
$\begingroup$

What is the currently most efficient (interactive) zero knowledge proof/argument for the subset sum problem?

The most recent relevant paper I have found is Efficient Modular NIZK Arguments from Shift and Product - Prastudy Fauzi, Helger Lipmaa, Bingsheng Zhang, but it considers NIZKs and is quite involved.

I assume there are more efficient interactive protocols?

$\endgroup$
1
$\begingroup$

I would suggest rewriting your subset-sum problem as a lattice problem, either Approximate Close Vector Problem (Approx-CVP) either a Bounded Distance Decoding Problem (BDD), depending whether your subset-sum has low density or high density. Then, there should be plenty of litterature for efficient zero-knowledge proofs for lattice problem (like this one, but I'd guess there are more recent work with better efficiency).

To translate the subset-sum instance $t = \sum^n_{i=1} x_i b_i \bmod M$ into a lattice problem, consider the $n$-dimensional lattice $L = \{ \vec v \in \mathbb Z^n | \sum v_i b_i = 0 \bmod M\}$. Choose any $\vec y \in \mathbb Z^n$ (not small) such that $t = \sum^n_{i=1} y_i b_i \bmod M$. Then, solving your subset-sum is equivalent to to writing $\vec y = \vec v + \vec x$ where $\vec v \in L$ and $\vec x$ is small. Depending on how short of an $\vec x$ you expect, this is either an Approx-CVP problem or a BDD problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.