Collisions in the cyclotomic knapsack function

Question

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?

Answer 1

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$.)

It looks like the rest of the proof goes through as written.

Let me also mention that subsequent works manage to avoid all this cumbersome "bookkeeping" associated with subspaces etc., by working with rings defined by irreducible polynomials (or more generally, in number rings). See, e.g., Lyubashevsky-Micciancio ICALP 2006, Peikert-Rosen STOC 2007, and Lyubashevsky-Peikert-Regev EUROCRYPT 2010/JACM 2013.