4
$\begingroup$

There are some questions here concerning lattice-based cryptography and this kind of cryptography seems to be especially useful if quantum computers are assumed to exist.

When reading such questions I always asked myself: "What is a lattice?"

And now I'm asking here:

  • How is a lattice defined?
  • What's the most common operation performed on / with a lattice? (like doubling and adding in ECC)

If you need assumptions on what knowledge is available:
Solid knowledge on most non-quantum resistant cryptography, like teached in the HAC.

$\endgroup$
  • $\begingroup$ en.wikipedia.org/wiki/Lattice_problem and en.wikipedia.org/wiki/Lattice_%28group%29 are probably good starting points for background information. $\endgroup$ – Aleph Jun 28 '15 at 20:07
  • 2
    $\begingroup$ What research/self-study have you done? We expect you to do some research on your own before asking. See crypto.stackexchange.com/help/how-to-ask. Your question is covered in many standard places, e.g., textbooks and Wikipedia. If your question is answered in the obvious place on Wikipedia, you probably haven't done enough research before asking. $\endgroup$ – D.W. Jun 29 '15 at 0:45
  • $\begingroup$ @SEJPM Could you clarify the last part of your question? I don't understand what you mean $\endgroup$ – cygnusv Jun 29 '15 at 7:17
  • $\begingroup$ @cygnusv, the last part should explain how much of background knowledge can be assumed for any answer. You hit the spot perfectly. $\endgroup$ – SEJPM Jun 29 '15 at 21:38
  • $\begingroup$ Really fascinating: I just noticed my question got 2 downvotes and three upvotes, so it seems to be some sort of borderline question. $\endgroup$ – SEJPM Jun 29 '15 at 21:43
11
$\begingroup$

How is a lattice defined?

A lattice $\mathcal L(B)$ is the set of all integer combinations of the basis $B = \{b_1, ..., b_n\}$ of $n$ linearly independent vectors. That is, lattice $\mathcal L(B)$ is defined as: \begin{equation} \mathcal L(B) = \{ B \cdot z \;: \; z \in \mathbb Z^n\} \end{equation}

In cryptography, we are interested on integer lattices, i.e., those where $B \in \mathbb Z^{n\times n}$, and, specially, on $q$-ary lattices, which are the modular version of integer lattices.

What's the most common operation performed on / with a lattice? (like doubling and adding in ECC)

As you see, elements in a lattice are simply vectors in the space where the matrix is defined. In the case of integer lattices, the space is $\mathbb Z^{n\times n}$, so elements of the lattice are just integers vectors. For this reason, lattice-based schemes usually operate with vectors and matrices, so the basic operations are the usual: vector/matrix addition, inner product, etc.

For the sake of illustration, the following is the main step during the encryption function of the CCA1-secure cryptosystem from Micciancio and Peikert [1]: \begin{equation} b^t = 2(s^t A_u \mod q) + e^t + (0, \operatorname{encode}(m))^t \mod 2q \end{equation}

where $b$ is the ciphertext, $s$ and $e$ are random vectors and $A_u$ is the public key (or more accurately, derived from the public key). You can see that everything is very simple from the point of view of the actual operations that are performed: $b, s$, and $e$ are vectors, and $A_u$ is a matrix, and the operations performed are additions and multiplications. The only "special" part here is the encoding of the message from a bit-string to a lattice point.

[1] Micciancio, D., & Peikert, C. (2012). Trapdoors for lattices: Simpler, tighter, faster, smaller. In Advances in Cryptology–EUROCRYPT 2012 (pp. 700-718). Springer Berlin Heidelberg (PDF).

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