# Reduction KnapSack to Closest Vector Problem (CVP) Being able to solve the [[Closest Vector Problem (CVP)]] enables solving [[The Knapsack Problem]]. Let $\{a_1,...,a_n,c\}$ be an instance of Knapsack problem. Define $L$ the lattice constructed from the solution of $\sum_{i=1}^na_iX_i=0$. Compute the integer solution $y=(y_1,...,y_n)\in\mathbb{Z}^n$ of $\sum_{i=1}^n a_iy_i=c$. define $y^*=(y_0-1/2,\ldots,y_n-1/2)$ and solve CVP i.e., find $z\in L$ s.t. $z\in L$ is the closest vector to $y^*$. we claim that the solution must be $z:=(y_0-x_0,...,y_n-x_n)$ and from here we can compute the solution of the Knapsack problem $x:=y-z=(x_0,...,x_n)$. Why the CVP solution must be $z:=(y_0-x_0,...,y_n-x_n)$? If $z^\prime\in\mathbb{Z}^n$, $y^*-z'=(y_0-1/2-z'_0,\ldots,y_n-1/2-z'_n)$ and its minimal norm $\sqrt{n/4}$ occur for $y_i-z'_i\in\{0,1\}$. As $L\subset \mathbb{Z}^n$ , the minimum distance of $y^*$ from $L$ is $\sqrt{n/4}$. $z\in L$ as $\sum_{i-1}^n a_iz_i=\sum_{i-1}^n a_i(y_i-x_i)=0$ and the distance of $y^*$ from $z$ is exactly $\sqrt{n/4}$ and so $z$ must be CVP solution. Reference: [[@The Two Faces of Lattices in Cryptology]] ## Created 2026-06-19 19:44