mirror of
https://github.com/lux-apps/papers.git
synced 2026-11-03 05:07:46 +00:00
zeekay
abf99d05fc
Restructured from flat .tex/.pdf files into per-paper subdirectories. Added Antje Worring as co-author on all papers. Synced PDFs to pdfs/ for download site.
48 lines
2.0 KiB
TeX
48 lines
2.0 KiB
TeX
\section{What Is a Lattice}
|
|
|
|
|
|
\begin{definition}[Lattice]
|
|
A lattice $\Lambda$ in $\mathbb{R}^n$ is the set of all integer linear combinations of
|
|
a set of linearly independent vectors $\mathbf{b}_1, \ldots, \mathbf{b}_n \in \mathbb{R}^n$:
|
|
\[
|
|
\Lambda = \left\{ \sum_{i=1}^n z_i \mathbf{b}_i \;:\; z_i \in \mathbb{Z} \right\}
|
|
\]
|
|
The vectors $\{\mathbf{b}_i\}$ form a \emph{basis} for $\Lambda$.
|
|
\end{definition}
|
|
|
|
Think of a lattice as a grid---a regular arrangement of points in space. In two dimensions,
|
|
it looks like graph paper tilted and stretched. The crucial property: the grid is
|
|
\emph{discrete} (points are separated by gaps) but \emph{infinite} (it extends in all
|
|
directions).
|
|
|
|
\subsection{Why Lattices for Cryptography}
|
|
|
|
Classical public-key cryptography (RSA, elliptic curves) relies on the hardness of
|
|
factoring or discrete logarithms. Shor's algorithm solves both in polynomial time on a
|
|
quantum computer. Lattice problems---finding short vectors in high-dimensional
|
|
lattices---resist all known quantum algorithms.
|
|
|
|
The two fundamental hard problems:
|
|
|
|
\begin{definition}[Shortest Vector Problem (SVP)]
|
|
Given a lattice basis $\mathbf{B}$, find the shortest nonzero lattice vector.
|
|
\end{definition}
|
|
|
|
\begin{definition}[Closest Vector Problem (CVP)]
|
|
Given a lattice basis $\mathbf{B}$ and a target point $\mathbf{t}$, find the lattice
|
|
vector closest to $\mathbf{t}$.
|
|
\end{definition}
|
|
|
|
Both are NP-hard in their exact forms, and the best known algorithms (classical or
|
|
quantum) for approximate versions run in exponential time in the lattice dimension $n$.
|
|
|
|
\subsection{The Geometry of Hard Problems}
|
|
|
|
In low dimensions ($n = 2, 3$), finding short vectors is easy---look at the basis and
|
|
reduce it. In high dimensions ($n = 256, 512, 1024$), the geometry becomes pathological:
|
|
the shortest vector is exponentially shorter than the basis vectors, but finding it
|
|
requires exploring an exponentially large search space. This is the core intuition:
|
|
lattice cryptography works because high-dimensional geometry is hard.
|
|
|
|
%% ============================================================
|