SerpApi.Org
Cryptographers Dimitri Koshelev, a postdoctoral researcher at the Universitat de Lleida's Cryptography and Graphs group who also holds an affiliation with the Institute of Mathematics at the National Academy of Sciences of Belarus, and Francesc Sebé of the Universitat de Lleida's Department of Mathematics, published a paper today on the IACR Cryptology ePrint Archive presenting a hybrid hash function whose collision resistance rests simultaneously on two independent computational hardness assumptions: the discrete logarithm problem (DLP) over elliptic curves, and the short integer solution (SIS) problem from lattice mathematics. The paper, approved as ePrint 2026/1459, frames the construction as a formally analyzed and concretely parametrized bridge primitive for post-quantum migration — one whose security survives a breach of either underlying assumption alone.
That distinction matters more now than it did two years ago. In August 2024, NIST finalized its first three post-quantum cryptographic standards — FIPS 203 (ML-KEM), FIPS 204 (ML-DSA), and FIPS 205 (SLH-DSA) — after an eight-year international evaluation process. Two of those three standards rest on module-lattice problems: the hardness of finding short vectors in high-dimensional structured integer lattices. The third, SLH-DSA, relies on hash functions. This means the cryptographic infrastructure the world is currently migrating toward concentrates most of its security on a single mathematical family — module lattices — for which no known quantum algorithm poses an efficient threat, but whose relative youth compared to RSA or elliptic-curve cryptography leaves the community alert to surprises. A hybrid hash function that independently invokes both classical DLP and quantum-resistant SIS hardness is, among other things, a primitive-level hedge against exactly that scenario.
Two Locks on One Door
The central idea threads two well-understood but distinct mechanisms into a single construction. The Pedersen hash, long used in zero-knowledge proof systems and commitment schemes on blockchains including Zcash and Monero, derives its collision resistance from the hardness of the discrete logarithm problem: given an elliptic curve group and a set of generator points, recover the integer combination used to compute a given point. No efficient classical or general quantum-resistant algorithm for this problem exists on large prime-order curves — though Shor's algorithm solves it in polynomial time on a sufficiently large fault-tolerant quantum computer, making the Pedersen hash a cryptographic liability once such machines exist.
The Ajtai hash, introduced in a 1996 paper that launched lattice-based cryptography as a field, achieves collision resistance from the SIS problem: given a random matrix A over integers modulo q, find a short nonzero vector x such that Ax ≡ 0 (mod q). Miklós Ajtai's key contribution was a worst-case to average-case reduction showing that solving this problem on average is at least as hard as approximating the Shortest Vector Problem in the worst case — a guarantee that has anchored lattice-based cryptographic constructions ever since. No known quantum algorithm solves the SIS problem efficiently, which is why module-lattice variants underpin two of NIST's three new standards.
The Koshelev-Sebé construction threads both mechanisms into a single function via the theory of relation lattices — integer linear combinations of elliptic curve group elements that sum to the identity. Controlling such relations is equivalent to what makes the discrete logarithm hard on elliptic curves. By embedding SIS structure into the same algebraic object, the construction simultaneously inherits collision hardness from both parent traditions. An attacker who finds a collision in the hybrid has thereby solved at least one of the two problems — and, critically, must solve both to guarantee a collision regardless of which assumption eventually weakens. The full technical details are documented in ePrint 2026/1459.
Why Concentration Risk in NIST's Standards Matters
When NIST finalized its post-quantum standards in August 2024, the field's direction appeared settled: retire classical number-theoretic problems, replace them with lattice-based ones. But the case for maintaining some classical hardness as a hedge has grown more pointed in the intervening period, not less.
In April 2024, a preprint by researcher Yilei Chen proposed a quantum algorithm claiming to solve certain lattice problems efficiently. The claim was subsequently found to contain a flaw and was retracted, but the episode demonstrated that the research community regards lattice hardness as an active frontier rather than a settled matter — and that even a single preprint can temporarily shake confidence in an entire family of post-quantum standards. By mid-2026, cryptographic agility had become a recognized requirement at the organizational level, not just an academic consideration, driven in part by a June 2026 executive order accelerating federal civilian migration timelines.
Koshelev and Sebé address this directly. The paper characterizes the construction as a hedge: if elliptic-curve discrete logarithms eventually fall to a sufficiently powerful quantum computer, the SIS component still holds; if a classical or quantum breakthrough unexpectedly weakens SIS, the DLP component still holds. An adversary must win on both fronts simultaneously. The authors describe the result as a "reincarnation of curve-based cryptography whose development has been severely and unfairly undermined by the potential but still unrealized threat of quantum computing" — a pointed remark about how rapidly the field pivoted away from classical hardness before quantum computers capable of exploiting it actually existed.
What a Hybrid Hash Function Actually Does Differently
Hash functions are foundational: they appear as subroutines inside digital signatures, commitment schemes, zero-knowledge proof systems, key derivation functions, and Merkle trees. The Pedersen hash has been widely deployed precisely because its algebraic structure is efficient inside zero-knowledge circuits — computing it involves elliptic curve point arithmetic, which is native to the ZK proof environment. The Ajtai hash achieves similar collision-resistance properties but from a completely different mathematical direction.
The practical difference in a hybrid construction is not merely philosophical. When a security engineer deploys a commitment scheme backed by the Pedersen hash, that scheme inherits the Pedersen hash's quantum vulnerability: a future quantum adversary who can break elliptic-curve discrete logarithms can forge commitments. A hybrid scheme that also requires the adversary to break SIS changes the attack surface: now the adversary must simultaneously break a classical problem (which, absent a sufficiently large fault-tolerant quantum computer, remains hard) and a lattice problem (which, absent a currently-unknown mathematical breakthrough, also remains hard). Neither assumption's failure alone is sufficient.
The authors positioned the current paper as a foundation layer for a broader research program. They explicitly stated their intention to explore how the hybrid hash "can be used for constructing more complex and important hybrid cryptographic schemes" — a signal that commitment schemes, Merkle-tree-based constructions, and ZK proof systems built on this primitive are among the envisioned applications.
Concrete Parameters for a Primitive Treated as Folklore
The paper describes itself as a "short note," but it includes concrete parametrization — a detail that distinguishes it from purely theoretical proposals. The parameters provided achieve the standard 128-bit security level for the SIS lattice component using a 256-bit module, a benchmark aligned with current NIST security category recommendations for post-quantum primitives.
The authors noted in the abstract that no prior work had explicitly analyzed the hybrid version of this construction, despite it being a "folklore but little-known" combination of the two classical primitives. Providing usable parameters alongside the formal analysis is significant because hybrid constructions often meet a practical objection: the overhead of combining two distinct mathematical structures can inflate key sizes, computation costs, or both. The authors acknowledged the result is "probably prone to significant further optimizations by applying many tricks from elliptic curve and lattice cryptographies," signaling that today's parametrization is an opening position on which follow-on work is invited.
Whether the hybrid proves computationally competitive with purely lattice-based alternatives will be determined by community analysis. The paper's publication on IACR ePrint opens that conversation formally.
How Relation Lattices Connect Elliptic Curves and SIS
The technical core of the construction draws on relation lattices — a formalism that connects elliptic curve group structure to lattice geometry. The keywords attached to the paper trace the conceptual lineage: discrete logarithm problem, hashing to elliptic curves, hybrid cryptography, relation lattices, short integer solutions.
Koshelev has specialized in efficient hashing to elliptic curves. His work published at AFRICACRYPT 2025 generalized the SwiftEC hash-to-curve construction to any elliptic curve over any finite field of characteristic greater than three — an advance that brought the theory of elliptic curve hash functions to a new level of generality. Sebé, a faculty member in the Department of Mathematics at the Universitat de Lleida, brings expertise in privacy-preserving cryptographic systems and applied cryptographic protocol design.
The collaboration reflects the dual focus of the paper: the elliptic-curve and lattice traditions require distinct mathematical tools, and threading them into a single object required expertise in both. The Universitat de Lleida's Cryptography and Graphs group, where Koshelev holds his postdoc position, lists researchers across both algebraic geometry and applied cryptography — the combination of skills the hybrid construction requires.
What This Means for Protocol Designers Navigating the Migration
For protocol designers and security architects managing the post-quantum migration, the construction points toward a middle path between two uncomfortable extremes: abandoning classical hardness assumptions prematurely on the basis of a quantum threat that had not materialized at cryptographic scale as of July 2026, or delaying migration until lattice assumptions are more thoroughly battle-tested.
A hash function whose security simultaneously invokes both mathematical traditions can underpin protocols that remain secure across a wider range of adversarial scenarios — including the scenario where one family of assumptions is weakened by advances not yet foreseen. The 2030 federal deadline for key establishment and 2031 deadline for digital signatures in federal civilian high-value systems, established by a June 2026 executive order, creates urgency for engineers who must make concrete migration decisions now while maintaining cryptographic agility.
The practical question the paper leaves open is optimization. Today's parameters impose overhead from combining two mathematical structures. Follow-on analysis will determine whether that overhead is acceptable for deployment in commitment schemes, ZK circuits, or key derivation pipelines — or whether further engineering work is required before the primitive competes on performance grounds with purely lattice-based alternatives. That analysis begins with the paper's publication on IACR ePrint today.
Frequently Asked Questions
What is a hybrid hash function, and why does the DLP-SIS combination matter?
A hybrid hash function combines two independent hardness assumptions in a single construction, so that forging a collision requires breaking both problems simultaneously. The discrete logarithm problem (DLP) on elliptic curves has decades of cryptanalytic scrutiny and remains hard for classical computers, but falls to Shor's quantum algorithm. The short integer solution (SIS) problem from lattice mathematics appears hard for quantum computers as well as classical ones, but is newer and less battle-tested. A hash function requiring an adversary to break both simultaneously survives attacks that defeat either assumption alone — which is precisely the risk profile of the next decade of post-quantum transition.
Does this paper address a specific weakness in NIST's post-quantum standards?
Not a weakness in the sense of a known attack — but it addresses a structural concentration. Two of NIST's three finalized post-quantum standards (ML-KEM and ML-DSA) rest on module-lattice problems: if that mathematical family were unexpectedly weakened, both standards would be affected simultaneously. A hybrid primitive that also relies on classical elliptic-curve hardness provides a fallback that does not share the same failure mode. The Koshelev-Sebé construction is not a replacement for NIST standards; it is a foundation for protocols that hedge against the possibility that betting on a single mathematical family turns out to be premature.
Is the Pedersen hash quantum-resistant, and can the new construction replace it?
The Pedersen hash is not quantum-resistant: Shor's algorithm breaks the discrete logarithm problem on elliptic curves in polynomial time on a sufficiently large fault-tolerant quantum computer. Systems that rely on Pedersen hashes in commitment schemes or zero-knowledge circuits face a long-term quantum risk. The Koshelev-Sebé hybrid construction is a direct upgrade path: it generalizes the Pedersen hash by adding SIS-based hardness alongside the existing DLP hardness, so the result survives a quantum adversary who can solve elliptic-curve DLP — as long as SIS remains hard, which current evidence supports.
What does cryptographic agility mean, and how does a hybrid hash function support it?
Cryptographic agility is the principle that systems should be designed so that their underlying algorithms can be swapped without architectural overhaul. NIST has published guidance on achieving cryptographic agility as a core recommendation for the post-quantum transition. A hybrid hash function that independently embeds two hardness assumptions provides agility at the primitive level: rather than replacing the hash function when one assumption weakens, the combined construction continues to hold as long as the other assumption stands. This is distinct from protocol-level agility, where two separate algorithms run in parallel and their outputs are combined — the Koshelev-Sebé approach integrates both assumptions into a single mathematical object.
Related Articles
