1
$\begingroup$

On this course, Micciancio talks about function families (functions parametrized by some value) that can be used in cryptography.

On page 2, he presents the following function family parametrized by bases of full-rank lattices:

For any invertible $ \mathbf{B} \in \mathbb{R}^{n \times n}$, let $f_\mathbf{B}(\mathbf{x}) = \mathbf{x} \mod \mathbf{B} = \mathbf{B} \left(\mathbf{B}^{-1}\lfloor \mathbf{x} \rfloor \right)$.

Clearly, there is a typo there, because $\mathbf{B} \left(\mathbf{B}^{-1}\lfloor \mathbf{x} \rfloor \right) = \lfloor \mathbf{x} \rfloor$ and this is at the same time independent of the basis and useless for cryptography.

So, maybe the correct definition must be $f_\mathbf{B}(\mathbf{x}) = \mathbf{x} \mod \mathbf{B} = \mathbf{B} \lfloor \mathbf{B}^{-1} \mathbf{x} \rfloor$. But in this case, the codomain $f_\mathbf{B}$ is the lattice $\mathcal{L}(\mathbf{B})$, but the text just below the definition says

In other words, $f_\mathbf{B}(\mathbf{x})$ rounds $\mathbf{x}$ to the corner of the fundamental parallelepiped $f_\mathbf{B}(\mathbf{x}) + \mathcal{P}(\mathbf{B})$ containing $\mathbf{x}$. As defined, $f_\mathbf{B}$ is a function with domain $X \subseteq \mathbb{R}^n$ and codomain $\mathcal{P}(\mathbf{B})$.

So, do you have any idea of what the actual definition should be?

$\endgroup$
  • $\begingroup$ I think your correction fits the text $\endgroup$ – Florian Bourse Apr 5 '18 at 15:49
  • $\begingroup$ But P(B) has only one lattice point and the image of the function I've defined has many lattice points, so P(B) cannot be its codomain. $\endgroup$ – Hilder Vitor Lima Pereira Apr 5 '18 at 16:56
  • 1
    $\begingroup$ $$x \bmod B$$ is often defined as $$x-B\lfloor B^{-1} x\rfloor \in P(B)$$, which has the codomain claimed in the text. $\endgroup$ – Chris Peikert Apr 9 '18 at 1:59
1
$\begingroup$

As pointed out by Chris Peikert in his comment, the actual definition must be

$f_\mathbf{B}(\mathbf{x}) = \mathbf{x} \mod \mathbf{B} = \mathbf{x} - \mathbf{B} \lfloor\mathbf{B}^{-1} \mathbf{x} \rfloor$.

we can see that the codomain of such $f_\mathbf{B}$ is the fundamental region $\mathcal{P}(\mathbf{B})$ as follows:

Write any given $\mathbf{x}$ as a linear combination of the columns $\mathbf{b}_1$, ..., $\mathbf{b}_n$ of $\mathbf{B}$, that is:

Let $\mathbf{x} = \mathbf{B}\mathbf{z}$ for some $\mathbf{z} \in \mathbb{R}^n$ (it's possible because $\mathbf{B}$ is fullrank, so its columns span $\mathbb{R}^{n}$).

Let $\mathbf{t} = \mathbf{z} - \lfloor \mathbf{z} \rfloor$, so $\mathbf{t} \in [-1, 1)^n$ and $\mathbf{x} = \mathbf{B}(\mathbf{t} + \lfloor\mathbf{z} \rfloor)$.

Thus,

$f_\mathbf{B}(\mathbf{x}) = \mathbf{x} - \mathbf{B} \lfloor\mathbf{B}^{-1} \mathbf{B}(\mathbf{t} + \lfloor\mathbf{z} \rfloor) \rfloor = \mathbf{x} - \mathbf{B} \lfloor \mathbf{t} + \lfloor \mathbf{z} \rfloor \rfloor = \mathbf{x} - \mathbf{B} \lfloor \mathbf{z} \rfloor = \mathbf{B}\mathbf{t}$

and $\mathbf{B}\mathbf{t} \in \mathcal{P}(\mathbf{B})$ by definition of $\mathcal{P}(\mathbf{B})$.

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