# Zero-knowledge proof for subset sum problem?

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?

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.