🔢 mathematics

Notes on the LVP and CVP in $p$ -adic Fields

This paper presents a polynomial-time algorithm for solving the Longest and Closest Vector Problems in $p$ -adic fields by leveraging non-Archimedean properties, maximal orders, and $p$ -radicals to efficiently construct orthogonal bases and characterize norms.

Original authors: Chi Zhang, Mingqian Yao

Published 2026-04-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Chi Zhang, Mingqian Yao

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Cracking a Digital Safe

Imagine you are trying to build an unbreakable digital safe (a cryptographic system) to protect secret messages. To do this, you need a mathematical puzzle that is easy to set up but impossible to solve without a special key.

For decades, mathematicians have used puzzles based on Euclidean geometry (the kind of geometry you learned in school with triangles and circles). These puzzles involve finding the "shortest" or "closest" path in a grid of points.

However, this paper introduces a new type of puzzle based on p-adic fields. Think of p-adic fields not as a flat map, but as a strange, multi-layered universe where the rules of distance are completely different. In this universe, the "Longest Vector Problem" (LVP) and "Closest Vector Problem" (CVP) are the new challenges.

The authors of this paper, Chi Zhang and Mingqian Yao, have discovered a master key. They found a fast, step-by-step method to solve these puzzles in this strange universe. This means that any digital safe built using these specific p-adic puzzles is now considered unsafe.

The Setting: A World with Different Rules of Distance

To understand their discovery, we first need to understand the "world" they are working in.

The Analogy: The Onion vs. The Ruler

Normal Math (Euclidean): Imagine measuring distance with a ruler. If you walk 1 mile north and 1 mile east, you are $\sqrt{2}$ miles away. The distance grows steadily.
p-adic Math: Imagine an onion with many layers. In this world, the "distance" between two points is determined by how many layers they share.
- If two numbers share a deep, inner layer, they are considered "very close" (distance is tiny).
- If they differ even slightly in a deep layer, they are "very far apart."
- The Golden Rule: In this world, if you take two steps, the total distance is never the sum of the steps. It is simply the larger of the two steps. (This is called the non-Archimedean property).

Because the rules are so different, the "grids" (lattices) in this world look very different. In normal grids, finding the shortest path is hard. In these p-adic grids, the authors found that if you know how to peel the onion correctly, the path becomes obvious.

The Problem: The "Longest" and "Closest" Vectors

The paper focuses on two specific problems:

The Longest Vector Problem (LVP): In a grid of points, find the point that is "furthest" out in a specific sense.
The Closest Vector Problem (CVP): You are given a target point floating in space. Find the point in the grid that is closest to it.

In the world of cryptography, these problems are supposed to be the "locks" that keep hackers out. If you can't solve them quickly, the lock is secure.

The Discovery: The "Orthogonal" Key

The authors' breakthrough is finding a way to organize the grid so that the problems become trivial. They call this an Orthogonal Basis.

The Analogy: The Tangled Yarn vs. The Straight Lines
Imagine a ball of tangled yarn (the p-adic lattice).

The Old Way: To find the longest string or the closest knot, you have to untangle the whole mess. It takes forever (exponential time).
The New Way: The authors found a way to re-arrange the yarn into perfectly straight, non-intersecting lines (an orthogonal basis).
- Once the yarn is straight, finding the longest string is just looking at the ends.
- Finding the closest knot is just dropping a perpendicular line.

They achieved this by using tools from algebraic number theory:

Maximal Orders: They found the "perfect container" for the numbers in this field.
Uniformizers: They found a special "unit of measurement" (like a standard ruler) that fits perfectly into the layers of the onion.
Residue Fields: They looked at the "skin" of the onion to understand the structure underneath.

By combining these tools, they built a polynomial-time algorithm. In plain English: "We found a shortcut that solves the puzzle in seconds, even for very large grids, whereas before it would take millions of years."

The Impact: Breaking the Locks

The paper has a very serious implication for cryptography:

The Attack: Because the authors can solve the LVP and CVP so quickly, any encryption system or digital signature scheme that relies on these specific p-adic puzzles is broken.
The History: Previous researchers thought these puzzles were hard. In 2021, new schemes were built based on them. This paper proves those schemes are insecure if the underlying math (the "minimal polynomial") is known.
The Counter-Attack: The authors suggest that to make these systems safe again, we might need to hide the "rules of distance" completely. Instead of giving the formula for the distance, we should only give a "black box" (an oracle) that tells you the distance when you ask. If we can't see the formula, we can't build the "straight lines" (orthogonal basis) to solve the puzzle.

Summary

Think of this paper as a group of locksmiths who found a flaw in a new type of lock.

They studied a strange new world (p-adic fields) where distance works differently.
They realized that the "locks" (LVP/CVP) in this world rely on the grid being messy.
They invented a machine (the algorithm) that instantly straightens out the messy grid.
Once the grid is straight, the lock opens immediately.

The takeaway: If you are building a digital safe using these specific p-adic puzzles, do not use them. The authors have shown that the "secret" is not secret enough. However, their work also points the way forward: if we can hide the rules of the game even better, we might still be able to build secure systems in this strange mathematical universe.

1. Problem Statement

The paper addresses the computational complexity of two fundamental lattice problems within the context of $p$ -adic fields:

Longest Vector Problem (LVP): Given a lattice $L$ , find a vector $v \in L$ with the second largest norm (specifically, the largest norm strictly less than the maximum norm of the lattice).
Closest Vector Problem (CVP): Given a lattice $L$ and a target vector $t$ , find a lattice vector $v \in L$ that minimizes the distance $|t - v|_p$ .

Context:
While the Shortest Vector Problem (SVP) and CVP are central to the security of Euclidean lattice-based cryptography, their $p$ -adic analogs (LVP and CVP) were recently proposed as the basis for new post-quantum cryptosystems (Deng et al., 2018; 2021). These schemes rely on the assumption that finding orthogonal bases in $p$ -adic lattices is computationally hard. Previous attacks (Zhang, 2025) broke these schemes only under specific conditions (totally ramified fields). This paper aims to provide a general polynomial-time attack for any $p$ -adic field defined by a minimal polynomial.

2. Methodology

The authors leverage the non-Archimedean property of $p$ -adic norms (the ultrametric inequality: $|x+y|_p \leq \max(|x|_p, |y|_p)$ ) to develop a deterministic polynomial-time algorithm. The core methodology involves three main stages:

A. Computing the Maximal Order

To solve lattice problems, one must first understand the algebraic structure of the field extension $K = \mathbb{Q}_p(\theta)$ .

The authors utilize the Round 2 and Round 4 algorithms to compute the maximal order $\mathcal{O}_K$ of the field $K$ .
Starting from a known order (e.g., $\mathbb{Z}_p[\theta]$ ), they iteratively enlarge the ring using the $p$ -radical ( $I_p = \{x \in \mathcal{O} \mid \exists m, x^m \in p\mathcal{O}\}$ ).
By computing the kernel of specific linear maps derived from the Frobenius homomorphism and the action of the ring on the $p$ -radical, they construct the maximal order efficiently.

B. Constructing an Orthogonal Basis

A critical theoretical insight is that unlike Euclidean lattices, $p$ -adic lattices always admit an orthogonal basis. The authors construct this basis using:

Uniformizers: Finding an element $\pi \in \mathcal{O}_K$ with maximal $p$ -adic absolute value (a uniformizer) from the $p$ -radical.
Residue Field Basis: Computing a basis $\{s_1, \dots, s_f\}$ for the residue field $k = \mathcal{O}_K / \pi \mathcal{O}_K$ over $\mathbb{F}_p$ .
Tensor Product Construction: Combining these to form the set $\{s_i \pi^j \mid 1 \leq i \leq f, 0 \leq j \leq e-1\}$ , where $e$ is the ramification index and $f$ is the residue degree.

Theorem 4.3 proves that this set forms an orthogonal basis for the field $K$ over $\mathbb{Q}_p$ . This means the norm of any linear combination is simply the maximum of the norms of its components.

C. Solving LVP and CVP

Once an orthogonal basis is established, the LVP and CVP reduce to trivial subproblems:

LVP Algorithm: By rearranging the basis vectors and lattice generators according to their norms, the algorithm identifies the vector with the second largest norm in polynomial time.
CVP Algorithm: Using the orthogonal basis, the algorithm performs a greedy reduction (similar to a coordinate-wise projection) to find the closest lattice vector to the target $t$ .
Both algorithms run in deterministic polynomial time relative to the degree of the extension ( $n$ ) and $\log p$ .

3. Key Contributions

General Polynomial-Time Algorithm: The paper presents the first general deterministic polynomial-time algorithm to solve LVP and CVP in $p$ -adic fields given by a minimal polynomial. This generalizes previous attacks that were limited to totally ramified fields.
Orthogonal Basis Construction: The authors provide a constructive proof and algorithm for generating orthogonal bases in $p$ -adic fields using maximal orders and residue field extensions, a property that does not hold in Euclidean spaces.
Characterization of Norms: The paper introduces Theorem 7.1, which characterizes all norms on finite-dimensional vector spaces over $\mathbb{Q}_p$ . It shows that any such norm can be represented by an invertible matrix and a set of positive real numbers. This highlights that if the transformation matrix is known, the "hidden" orthogonal basis is easily recoverable, rendering the norm insecure for cryptography.
Practical Validation: A concrete example over $\mathbb{Q}_2(\sqrt[3]{5})$ (using the polynomial $X^3 - 3X^2 + 3X - 5$ ) demonstrates the step-by-step computation of the maximal order, uniformizer, and the resulting orthogonal basis.

4. Results

Complexity: The proposed algorithms for computing the maximal order, finding the uniformizer, and solving LVP/CVP are all polynomial time in terms of the input size ( $n$ and $\log p$ ).
Security Implication: The existence of this efficient algorithm implies that public-key encryption and signature schemes based on $p$ -adic lattices (as proposed by Deng et al.) are insecure if the underlying field is fully specified by a minimal polynomial. The "hardness" assumption relied upon by these schemes is false in the general case.
Limitation of Previous Patches: The paper notes that while previous work suggested using fields with large residue degrees to patch these schemes, the current algorithm remains effective regardless of the residue degree, provided the field is known.

5. Significance

Cryptographic Impact: This work fundamentally undermines the security of a specific class of post-quantum cryptographic proposals based on $p$ -adic lattices. It demonstrates that the non-Archimedean geometry, while offering unique algebraic structures, does not provide the same level of computational hardness for lattice problems as Euclidean geometry does.
Theoretical Advancement: The paper bridges algebraic number theory (maximal orders, ramification) and computational complexity. It clarifies the structural differences between Euclidean and $p$ -adic lattices, specifically regarding the existence of orthogonal bases.
Future Directions: The authors suggest that for $p$ -adic cryptography to be viable, one must move away from defining the field via a minimal polynomial. Instead, they propose using norm oracles where the norm is computable but the underlying orthogonal basis (the "trapdoor") remains hidden. They pose the open question of whether finding the parameters of such a norm (Theorem 7.1) is hard when the basis is unknown.

In conclusion, the paper establishes that LVP and CVP in $p$ -adic fields are tractable problems, effectively breaking the security assumptions of current $p$ -adic lattice-based cryptosystems and redirecting future research toward norm oracles and hidden basis structures.