Simultaneous Approximation for Lattice-Based Cryptography

1. Problem Statement and Motivation

Context: Lattice-based cryptography is a leading candidate for post-quantum security due to its average-case to worst-case hardness reductions and homomorphic encryption capabilities. However, standard lattice schemes often suffer from large public key sizes.
The Gap:

• Ideal Lattices: Introduced to reduce key sizes, but recent cryptanalysis suggests their instances may not be as hard as general lattice instances (weaker security guarantees).
• Simultaneous Approximation (SA) Lattices: A specific class of lattices defined by $n+1$ integers (rather than $n^2$ for general lattices) that naturally arise from the Simultaneous Diophantine Approximation problem.
• The Challenge: While previous work (Martin, 2020) showed that solving the Shortest Vector Problem (SVP) in SA lattices is equivalent to the general SVP, the reductions used resulted in significant "integer inflation" (growth in the bit-length of numbers). This inflation threatens the practicality of SA lattices for cryptography because it forces larger parameters to maintain security, negating the key-size benefits.

Goal: The paper aims to define new SA lattice problems corresponding to the Shortest Independent Vector Problem (SIVP) and the Closest Vector Problem (CVP), and to provide optimal, dimension- and gap-preserving reductions from general lattice problems to these SA problems with significantly reduced integer inflation.

2. Methodology

2.1 New Problem Definitions

The author defines two new problems within the SA lattice framework:

1. SIAP (Shortest Independent Approximation Problem): The SA-lattice equivalent of SIVP. Given $x \in \mathbb{Q}^n$, find integers $b_1, \dots, b_n$ such that the fractional parts $\{b_i x\}$ are linearly independent and bounded by $\gamma \lambda_n$.
2. CAP (Closest Approximation Problem): The SA-lattice equivalent of CVP. Given $x \in \mathbb{Q}^n$ and a target $t$, find an integer $b_0$ such that $\{b_0 x - t\}$ is close to the target within a factor $\gamma$.

2.2 Core Algorithm: Approximating General Lattices with SA Lattices

The central technical contribution is Algorithm 1, which transforms a general lattice $L = M\mathbb{Z}^n$ into an SA lattice that approximates it.

• Mechanism: The algorithm constructs a matrix $\tilde{M} = c \cdot \text{adj}(M) + A$, where $A$ is a perturbation matrix with small integer entries.
• Construction Logic:
  • It ensures that the columns of $\tilde{M}$ (along with a specific vector $b$) generate $\mathbb{Z}^n$.
  • This is achieved by iteratively adjusting diagonal entries of sub-matrices to ensure their determinants are coprime (using properties related to Bézout's identity and Jacobsthal's function).
  • The resulting SA lattice is generated by the identity matrix $I_n$ and a vector $x = \tilde{M}^{-1} M b$.
• Key Innovation: Unlike Martin's previous work which used polynomial rings (leading to $O(n^4 \log(nk))$ inflation), this algorithm uses integer arithmetic and carefully bounds the perturbation size using Jacobsthal's function ($j(n) = O(\log^2 n)$).

2.3 Reductions

The paper presents three deterministic polynomial-time reductions:

1. SVP $\to$ SAP: Reducing general SVP to the Simultaneous Approximation Problem.
2. SIVP $\to$ SIAP: Reducing general SIVP to the new SIAP problem.
3. CVP $\to$ CAP: Reducing general CVP to the new CAP problem (involving a transformation of the target vector).

All reductions rely on the output of Algorithm 1 to map the general lattice instance to an SA instance, solve the SA problem, and map the solution back.

3. Key Contributions and Results

3.1 Improved Integer Inflation Bounds

The most significant quantitative result is the improvement in the bit-length of the input numbers required for the SA lattice.

• Previous Bound (Martin): $O(n^4 \log(nk))$.
• New Bound (Vanlandingham): $O(n^2 \log(nk))$.
• Significance: This reduction in "integer inflation" is critical. In lattice cryptography, the size of the public key is directly related to the bit-length of the lattice parameters. A lower inflation factor means SA lattices can offer smaller key sizes for the same security level compared to previous constructions.

3.2 Hardness Proofs (NP-Hardness)

The paper proves that the new SA problems are as hard as their general counterparts:

• Theorem 1.2:
  • SIAP and CAP are NP-hard for any constant approximation factor $\gamma$ under $\ell_1, \ell_2,$ and $\ell_\infty$ norms.
  • SAP is NP-hard under $\ell_\infty$ for any constant $\gamma$. Under $\ell_1$ and $\ell_2$, it is NP-hard under randomized reductions for $\gamma < 2$ and $\gamma < 2^{1/2}$, respectively.
• Implication: This confirms that SA lattices do not suffer from the "weakness" issues sometimes associated with ideal lattices; solving problems in SA lattices is as difficult as solving them in general lattices.

3.3 Optimality of the Reduction

The author proves that the $O(n^2 \log(nk))$ bound on integer inflation is optimal for polynomial-time reductions that preserve the gap.

• Theorem 3.14: If a reduction existed with sub-quadratic integer inflation (e.g., $O(n^{2-\epsilon})$), it would imply a sub-exponential approximation algorithm for SVP, which is currently believed to be impossible. Thus, the proposed algorithm is the best possible within the current complexity landscape.

3.4 Complexity Analysis

• The reductions are deterministic and run in polynomial time and space.
• The time complexity for the reductions (Algorithms 2, 3, and 4) is $O(n^5 \log^3(nk))$, dominated by the integer operations in Algorithm 1.

4. Significance and Impact

1. Cryptographic Viability of SA Lattices: The paper establishes SA lattices as a robust foundation for lattice-based cryptography. They offer the potential for smaller key sizes (due to the $n+1$ integer description) without sacrificing the worst-case hardness guarantees found in general lattices.
2. Resolution of the "Ideal Lattice" Trade-off: It addresses the specific weakness of ideal lattices (potential structural vulnerabilities) by providing a class of lattices (SA) that are provably as hard as general lattices but still possess structural properties that could lead to efficiency gains.
3. Optimization of Parameters: By proving the integer inflation bound is optimal, the paper sets a theoretical limit for how much key size can be compressed using this specific reduction technique, guiding future cryptosystem design.
4. New Hardness Targets: The introduction of SIAP and CAP expands the landscape of lattice problems available for cryptographic construction, potentially enabling new schemes based on SIVP and CVP in restricted lattice settings.

In summary, Vanlandingham's work bridges the gap between theoretical hardness and practical efficiency in lattice cryptography. It demonstrates that Simultaneous Approximation lattices are a secure, hard-to-solve alternative to general lattices, with optimized parameters that make them a promising candidate for next-generation cryptographic standards.