# Collisions in the cyclotomic knapsack function

I've been working my way through the paper “Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices” by Peikert and Rosen, and I've come across something that doesn't seem to make sense to me. (Apologies if the level of detail in the following is inconsistent, I'm somewhat less than familiar with the context.)

Here's my problem.

What I'm understanding is a simple linear algebra thing: Take a subspace of $\mathbb R^n$, then reduce a vector in that subspace modulo a lattice, but there's not enough of restriction on the structure of the subspace and lattice that that should stay in the subspace.

In particular

$\mathbb Z[\alpha]/(\alpha^n-1)$ is identified with $\mathbb Z^n$ by considering the representative with degree less than $n$, and taking $b_0+b_1\alpha+\cdots+b_{n-1}\alpha^{n-1}\mapsto(b_0,b_1,\cdots,b_{n-1})$.

We are looking at a restricted collection of lattices $\mathcal{L}(B)\cap H_\Phi$ where $\mathcal L(B)$ is a cyclic lattice (that is, one that is an ideal in $Z[\alpha]/(\alpha^n-1)$, or equivalently that is closed under ${\rm rot}:(c_1,c_2,\cdots,c_n)\mapsto(c_n,c_1,\cdots,c_{n-1})$), and we define the subspace $H_\Phi$ of $\mathbb{R}^n$ to be $\mathbb{R}[\alpha]\Phi(\alpha)/(\alpha^n-1)$ the multiples of some $\Phi(\alpha)=(\alpha^n-1)/(\Phi_k(\alpha))$ where $\Phi_k(\alpha)$ is a cyclotomic polynomial.

Then, we take $y\in\mathcal L(B)\cap H$, and let $y'=y \mod B$, the vector in $B[0,1)^n$ with $y-y'\in\mathcal L(B)$, and it is claimed that $y'\in H_\Phi$. As I understand things, however, this isn't true; take, for example, the following (general) counterexample:

Let $k=n$ for prime $n$. Then we have $\Phi(\alpha)=\alpha-1$, and \begin{align*} H_\Phi &=\left\{(b_0+\cdots+b_{n-1}\alpha^{n-1})(\alpha-1)\right\}\\ &=\left\{(b_{n-1}-b_0)+(b_0-b_1)\alpha+\cdots+(b_{n-1}-b_n)\alpha^{n-1}\right\}\\ &=\left\{(c_0,\cdots,c_{n-2},-(c_0+\cdots+c_{n-2}))\right\}. \end{align*} Then let $B$ be the standard basis for $\mathbb Z^n$, and take $y=(1/(n-1),\cdots,1/(n-1),-1)$, so that $y'=(0,\cdots,0,-1)$. But clearly $y$ is in $H_\Phi$, but $y'$ is not.

I'm not really sure what's going on here, because it is claimed that $y'\in H$ more or less by construction, making me think I'm confused somewhere along the way with the notation, but I can't seem to find it.

I'm fairly certain that what I have written above is correct, as well as that that it is claimed in the paper I linked above (in the proof of claim 5.3) that $y'\in H_\Phi$. Can someone point me to where I'm going wrong?

• Maybe you'll get lucky and one of the authors will comment. – puzzlepalace May 23 '16 at 22:55
• … and mentioning @chris-peikert accordingly would also enable him to get a system notification that his name was dropped in relation to this question, which definitely increases the chance that he notices this one question among the truckload of daily active questions. (Just saying.) – e-sushi May 24 '16 at 1:21
• To keep the off-topic chat separate; some of the comments have been moved to chat. – e-sushi May 24 '16 at 6:24

Thanks for the question! You are correct that there is a bug here. Indeed, the sentence "choose $\mathbf{b}_i$ s.t. $\ldots$" makes no sense: the LHS is in $H$, but the RHS may not be. Fortunately, there is a simple fix which guarantees $\mathbf{y}'_i \in H$. (This must have been what we intended in the first place, based on how the rest of the proof goes; see below.)
The fix: the proof of Theorem 5.1, Item 1, second bullet, should read: Let $\mathbf{y}'_i = \mathbf{y}_i \bmod \mathbf{B}'$ (not $\mathbf{B}$), where $\mathbf{B}'$ denotes an arbitrary basis of $\mathcal{L}(\mathbf{B}) \cap H$. (Such a basis is easy to compute by linear algebra.) That is, we sample a Gaussian over $H$, and mod it by a lattice contained in $H$. So, we clearly have $\mathbf{y}'_i \in H$.
Similarly, in the proof of Claim 5.2 ("Notice that $\mathbf{y}'_i \ldots$") we care about $D_{H,s} \bmod \mathcal{P}(\mathbf{B}')$, not $\mathbf{B}$. (Indeed, it doesn't make sense as currently written: Lemma 2.7 requires modding by a lattice contained in $H$.)
• Much better than my attempt to fix it by making $y_i'=y_i$ with nonnegiligible probability by taking $c$ wlog small... Thanks for the thorough answer! – Mar Johnson May 26 '16 at 18:32