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$
3
  • $\begingroup$ I think your correction fits the text $\endgroup$ Commented Apr 5, 2018 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$ Commented Apr 5, 2018 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$ Commented Apr 9, 2018 at 1:59

1 Answer 1

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 and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.