From Orientations to $\ell$-adic Period Vectors

1. Problem Statement and Motivation

The paper addresses the need for new post-quantum cryptographic primitives that leverage the rich arithmetic and combinatorial structures of supersingular elliptic curves, distinct from existing isogeny-based schemes (like CSIDH or SQISign) and lattice-based schemes (like SIS/LWE).

• The Gap: While isogeny-based cryptography relies on finding paths in supersingular isogeny graphs, and lattice cryptography relies on finding short vectors in lattices, there is a lack of primitives that bridge the gap between oriented supersingular curves and discrete $\ell$-adic data via modular forms.
• The Core Challenge: The author proposes a new hard problem: Modular Symbol Inversion (MSI). The problem is to recover a "short" homology representative (a path in a combinatorial graph) given only its truncated $\ell$-adic period vector. The difficulty lies in the exponential size of the path space and the lack of known subexponential attacks.

2. Methodology

The paper constructs an algebraic-analytic pipeline that maps oriented supersingular elliptic curves to truncated vectors in $(\mathbb{Z}/\ell^m\mathbb{Z})^d$. The methodology proceeds in three main stages:

A. From Orientations to Homology Classes

The authors establish a correspondence between the ideal class group of an imaginary quadratic order $\mathcal{O}$ and the relative homology of a modular curve $X_0(N)$.

1. Oriented Curves: An orientation is defined as an embedding $\iota: \mathcal{O} \hookrightarrow \text{End}(E)$ of an order $\mathcal{O}$ into the endomorphism ring of a supersingular curve $E$. The set of such curves forms a torsor for the ideal class group $\text{Pic}(\mathcal{O})$.
2. Three Equivalent Constructions: The paper proves that three different approaches yield the same homology class $\gamma \in H_1(X_0(N), \mathcal{C}; \mathbb{Z})$ (where $\mathcal{C}$ is the set of cusps):
   • Brandt Module: Using the Jacquet–Langlands correspondence to map ideal classes to Hecke operators acting on a Brandt module, which is isomorphic to a subspace of modular forms.
   • Heegner Points: Using complex multiplication (CM) to define points on the modular curve and connecting them via geodesic paths (geometric cycles).
   • Bruhat–Tits Trees: Using the $\ell$-adic uniformization (Cerednik–Drinfeld) where ideal classes correspond to paths on the Bruhat–Tits tree associated with $PGL_2(\mathbb{Q}_\ell)$.
3. Result: An ideal class $[a] \in \text{Pic}(\mathcal{O})$ (representing an oriented curve) is mapped to a specific homology class $\gamma([a])$.

B. From Homology to $\ell$-adic Period Vectors

Once a homology class $\gamma$ is obtained, it is evaluated against weight-2 cusp forms to produce numerical data.

1. Coleman Integration: The authors utilize Coleman integration, a theory of $\ell$-adic line integrals on curves. This allows the computation of periods $\langle f, \gamma \rangle_\ell$ for weight-2 cusp forms $f$ without requiring an explicit algebraic model of the curve $X_0(N)$.
2. Efficient Computation: They employ the algorithm by Chen, Kedlaya, and Lau, which computes these integrals directly from $q$-expansions of modular forms and rigid-analytic uniformization.
3. The Map: For a fixed basis of cusp forms $\{f_1, \dots, f_d\}$, the map is defined as:
   $$\Pi_m(\gamma) = (\langle f_1, \gamma \rangle_\ell, \dots, \langle f_d, \gamma \rangle_\ell) \pmod{\ell^m} \in (\mathbb{Z}/\ell^m\mathbb{Z})^d$$
   This yields a truncated vector of $\ell$-adic periods.

C. The Modular Symbol Inversion (MSI) Problem

The core cryptographic assumption is formulated as follows:

• Input: A vector $y \in (\mathbb{Z}/\ell^m\mathbb{Z})^d$ known to be the image of a "short" homology class $\gamma^*$ (where "short" means a path of bounded length $L$ in the underlying combinatorial graph).
• Output: Find any short homology class $\gamma$ such that $\Pi_m(\gamma) = y$.
• Hardness: The problem is conjectured to be hard because the number of valid paths grows exponentially with length $L$, while the output space size $\ell^{md}$ must be large enough to avoid collisions. The structure of the solution space (sparse, valid paths) prevents standard lattice reduction attacks (like SIS) from being directly applicable.

3. Key Contributions

1. New Bridge: The paper creates a novel theoretical link between oriented supersingular elliptic curves and modular symbols/$\ell$-adic periods, unifying arithmetic geometry with combinatorial path problems.
2. Equivalence of Constructions: It rigorously proves that the homology classes derived from Brandt modules, Heegner points, and Bruhat–Tits trees are equivalent in the rational homology space, validating the use of any of these perspectives for computation.
3. Definition of MSI: It formally defines the Modular Symbol Inversion (MSI) problem, distinguishing it from existing isogeny path problems and lattice problems.
   • Unlike Isogeny Path Problems: The graph is implicit (homology paths) rather than explicit curves.
   • Unlike SIS/LWE: The relation is exact (no noise), but the solution space is combinatorially constrained (sparse paths).
4. Cryptographic Primitives: The author sketches concrete cryptographic applications based on MSI:
   • Identification Protocols: A zero-knowledge proof system where the secret is a short homology path.
   • Pseudorandom Functions (PRFs): Constructing PRFs keyed by short homology classes using iterated period mappings.

4. Results and Analysis

• Computational Feasibility: The paper demonstrates that the forward direction (Curve $\to$ Period Vector) is computationally efficient using existing algorithms for Coleman integration and modular symbols.
• Hardness Heuristics: The authors provide a heuristic security analysis. They argue that if the output space size $\ell^{md}$ is significantly larger than the square of the number of paths ($\approx B^{2L}$), the map is injective with high probability.
• Attack Resistance:
  • Brute Force: Requires exponential time $O(B^L)$.
  • Meet-in-the-Middle: Requires $O(B^{L/2})$.
  • Lattice Attacks: Standard lattice reduction (LLL) is unlikely to succeed because the solution must satisfy strict combinatorial path constraints (validity in the graph), which standard lattice solvers do not enforce.
  • Quantum: Grover's algorithm offers only a quadratic speedup, leaving the problem exponential in $L$.

5. Significance and Future Work

• Post-Quantum Diversity: This work expands the landscape of post-quantum cryptography beyond the current reliance on isogeny graphs and lattices. It introduces a problem that sits at the intersection of algebraic topology, number theory, and combinatorics.
• Theoretical Depth: It leverages deep results from the theory of modular forms (Eichler–Shimura, Jacquet–Langlands) and $p$-adic geometry (Coleman integration) to construct a practical cryptographic primitive.
• Future Directions: The paper identifies several areas for future research:
  • Implementing the scheme and optimizing parameters ($N, \ell, m, L$).
  • Analyzing structural attacks specific to the modular symbol space.
  • Investigating the injectivity of the map from orientations to homology classes more deeply to ensure no information leakage.

In summary, Colò proposes a new cryptographic paradigm where the security relies on the difficulty of inverting a map from combinatorial paths in modular homology to $\ell$-adic period vectors, offering a promising alternative for post-quantum security.