4
$\begingroup$

In Gentry's paper on fully homomorphic encryption using ideal lattices, he finds the values of vectors modulo a certain basis. For instance:

$\psi \leftarrow \psi' \mod B$

Taken from page 69 of Gentry's thesis.

What does it mean to evaluate a vector modulo a basis?

$\endgroup$
5
$\begingroup$

Examining the definition provided by A. Sakzad, I now have the intuition for what this means which I'll explain through an example.

In the diagram below, the red dots are a lattice, and the two red arrows represent a basis, $B$, for this lattice. We have a green vector, $ψ'$ = [2, 2]. We might ask which point on the lattice $ψ'$ is closest to. If we are just looking at this in the grid reference frame, $ψ'$ is equidistant from [3, 1] and [3, 3]. But within the reference frame of basis $B$, which is shown by the red parallelograms, $ψ'$ is closest to (3, 3). The value of $B⋅⌈B^{−1}ψ′⌋$ is the point in the lattice to which $ψ'$ is closest in the reference frame of $B$. $ψ=ψ′(\mod B)=ψ′−B⋅⌈B^{−1}ψ′⌋$ is the vector from $B⋅⌈B^{−1}ψ′⌋$ to the original vector. It could be viewed as the error or remainder when $ψ′$ is approximated by a point on the lattice. In the diagram below, $ψ$ is the blue arrow.

Calculating a vector modulo a basis

Since the basis vectors are [3, 1] and [0, 2] the basis matrix is: $$ B = \left( \begin{array}{ccc} 3 & 0\\ 1 & 2 \end{array} \right) $$ Doing the math we find that (3, 3) is indeed the value of $B⋅⌈B^{−1}ψ′⌋$: $$ B⋅⌈B^{−1}ψ′⌋ =B⋅⌈1/6 \left( \begin{array}{ccc} 2 & 0\\ -1 & 3 \end{array} \right) \left( \begin{array}{ccc} 2\\ 2 \end{array} \right)⌋ $$ $$ = B⋅⌈\left( \begin{array}{ccc} 2/3\\ 2/3 \end{array} \right)⌋ = \left( \begin{array}{ccc} 3 & 0\\ 1 & 2 \end{array} \right) \left( \begin{array}{ccc} 1\\ 1\end{array} \right) = \left( \begin{array} {ccc} 3\\ 3\end{array} \right) $$ Therefore the remainder of $ψ′$ modulo the basis is: $$ ψ=ψ′(modB)=ψ′−B⋅⌈B^{−1}ψ′⌋ = \left( \begin{array} {ccc} -1 \\ -1 \end{array} \right) $$

$\endgroup$
2
$\begingroup$

It can be defined as follows: $$\psi = \psi' \pmod{\bf B} = \psi'-{\bf B}\cdot\lceil{\bf B}^{-1}\psi'\rfloor,$$ where $\lceil\cdot\rfloor$ denotes the round operation to the nearest integer.

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