What is a "lattice" in cryptography? 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.
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., &amp; Peikert, C. (2012). Trapdoors for lattices: Simpler, tighter, faster, smaller. In Advances in Cryptology–EUROCRYPT 2012 (pp. 700-718). Springer Berlin Heidelberg (PDF).