Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
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.
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) $$
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.
