Ideal lattice problems shown as hard as generic lattice problems
NP-hardness of ideal lattice problems
Computational Complexity
Summary
Certain problems involving ideal lattices, which are special mathematical structures, are as difficult to solve as their more general lattice counterparts. The authors found a way to transform these general lattice problems into ideal lattice problems without making them easier to solve, using an efficient and deterministic method. This means that breaking these ideal lattice problems is at least as hard as breaking the generic ones, which is important in cryptography and computational theory. They also consider quantum computing scenarios for related constructions.
What this means in practice
- •For cryptography developers: Design new cryptographic schemes based on ideal lattices with confirmed hardness equivalent to generic lattice challenges.
- •For security engineers: Assess the security assumptions of cryptographic protocols built on ideal lattices by relating them to well-studied general lattice problems.
A theory result. No direct application yet.
Authors
Daniel E. Martin
Abstract
We establish the worst-case hardness of several ideal lattice problems (including SVP and CVP) in the $\ell_2$ norm by providing a dimension-preserving, deterministic polynomial time reduction from their generic lattice versions. The reduction constructs an ideal lattice in the canonical embedding of a number field that approximates some input lattice up to scaling and orthogonal transformation. The integers defining the ideal and the ambient number ring, in particular its discriminant, are all polynomial in bit length relative to the generic input lattice. Furthermore, the ideal is invertible, the ring is monogenic, and the number field is totally real. If the number ring is also required to be a full ring of integers, the reduction conjecturally succeeds in bounded-error quantum polynomial time.