up:: Classical Cryptography MOC

Pairing-Based Cryptography

Pairing-based cryptography is the family of public-key schemes built on bilinear pairings, a special operation that takes two points on an elliptic curve and maps them into a third mathematical group while preserving a multiplication-like structure. That extra structure builds things ordinary elliptic-curve cryptography cannot: BLS signatures that aggregate thousands of signers into one short signature, identity-based encryption where your email address is your public key, and much of the zero-knowledge proof machinery behind modern rollups. It is quantum-broken. Every pairing-based scheme inherits its security from the elliptic-curve discrete logarithm problem, which is precisely the problem Shor’s algorithm solves in polynomial time, so a capable quantum computer recovers the private keys directly and forges signatures at will.

Source: D. Boneh, B. Lynn, H. Shacham, “Short Signatures from the Weil Pairing,” ASIACRYPT 2001, IACR.

The short version:

• A pairing is a bilinear map e(P, Q) that takes two elliptic-curve points and outputs an element of a third group, and its defining property e(aP, bQ) = e(P, Q)^(ab) is what lets pairing schemes do their tricks.
• It powers BLS signatures (short, aggregatable), identity-based encryption, attribute-based encryption, and pairing-based SNARKs like Groth16 that verify a computation in a few group elements.
• Its security rests on the elliptic-curve discrete logarithm problem and related pairing assumptions, all of which live inside elliptic-curve groups.
• Shor’s algorithm solves the elliptic-curve discrete logarithm in polynomial time, so a quantum computer recovers the secret scalar behind any pairing public key and the whole family falls.
• The replacements are the standardized post-quantum schemes: ML-DSA and SLH-DSA for signatures, hash-based STARKs for proofs, and lattice constructions for the advanced-encryption use cases.

Picture two clockmakers who each pick a secret number of gear teeth and mesh their gears through a shared master wheel. The master wheel spins to a position that depends on both secrets multiplied together, and either clockmaker can reach that same position knowing only their own secret and the other’s public gear. That shared, multiplicative meeting point is what a pairing gives you: a way to combine two hidden numbers into one checkable value without either party revealing their number. The catch is the same catch that sinks all elliptic-curve cryptography. Reading the secret number of teeth off a public gear is the discrete logarithm, easy for a quantum computer, so the moment one arrives the master wheel stops keeping anyone’s secret.

What is pairing-based cryptography?

Pairing-based cryptography is public-key cryptography built on a bilinear pairing, an efficiently computable map that takes a point from one elliptic-curve group and a point from a second and produces an element in a third target group. Written formally, the pairing is a function e: G1 x G2 -> GT with the bilinearity property that e(aP, bQ) = e(P, Q)^(ab) for any scalars a and b. That single algebraic property, that scalars slide out of the points and multiply together in the exponent of the output, is the entire source of the family’s power. It lets a scheme check a relationship between two secret scalars without ever seeing either one.

Source: IETF, “BLS Signatures,” draft-irtf-cfrg-bls-signature, datatracker.ietf.org.

Pairings run on special elliptic curves called pairing-friendly curves, the most widely deployed being BLS12-381, chosen because it makes the pairing fast while keeping the underlying discrete-log problem hard classically. Ordinary elliptic-curve cryptography uses one group and the discrete logarithm inside it. Pairing-based cryptography adds the bilinear map across groups, which is strictly more machinery and strictly more capability, at the cost of using curves whose structure has to be chosen with extra care. That added structure does not change the quantum verdict, because the hard problem underneath is still the elliptic-curve discrete logarithm.

What is pairing-based cryptography used for?

Pairings unlock several constructions that plain elliptic-curve cryptography cannot express, and most of them have become load-bearing in modern systems, especially in blockchain and privacy infrastructure. The common jobs:

1. BLS signatures. A Boneh-Lynn-Shacham signature is a single elliptic-curve point, and its standout feature is aggregation: many signatures on many messages combine into one short signature that verifies in a couple of pairing operations. This is why proof-of-stake blockchains use BLS to compress the votes of thousands of validators into one object.
2. Identity-based encryption (IBE). A pairing lets a system use an arbitrary string, an email address or a username, directly as a public key, with a trusted authority deriving the matching private key. It removes the need to distribute and look up certificates for every recipient.
3. Attribute-based and functional encryption. Pairings support encrypting so that only holders of a certain set of attributes (a role, a clearance, a policy) can decrypt, which underpins fine-grained access control on encrypted data.
4. Pairing-based SNARKs. A large share of succinct zero-knowledge proof systems, Groth16 and KZG-based PLONK among them, rely on pairings to make a proof tiny and its verification a single pairing-product check. These are the proofs behind many privacy coins and validity rollups.

The pattern across all of these is that a pairing buys expressiveness: it lets a scheme verify a multiplicative relationship between hidden values, which is the exact primitive aggregation, identity-based keys, and succinct proofs all need. That expressiveness is also why the family is worth cataloguing separately in a migration. A team that has inventoried its RSA and ECDSA and thinks it is done can still be sitting on BLS validators or Groth16 verifiers that are just as quantum-exposed and far less obvious.

Source: D. Boneh, B. Lynn, H. Shacham, “Short Signatures from the Weil Pairing,” ASIACRYPT 2001, IACR.

Is pairing-based cryptography quantum-safe?

No. Pairing-based cryptography is quantum-broken, and it breaks for exactly the same reason elliptic-curve cryptography breaks: its security rests on the elliptic-curve discrete logarithm problem. The security of a pairing scheme comes from the fact that recovering the secret scalar a from a public point aP is believed infeasible classically, and every pairing assumption in use, the computational and decisional Diffie-Hellman variants and their bilinear cousins, is built on top of that same discrete-log hardness inside the pairing groups.

Source: NIST, “Recommendations for Discrete Logarithm-Based Cryptography, Elliptic Curve Domain Parameters,” SP 800-186, February 2023, NIST.

Shor’s algorithm solves the elliptic-curve discrete logarithm in polynomial time on a capable quantum computer, so it recovers the secret scalar behind any pairing public key. Once that scalar is known, the private key is exposed, and the attacker can forge BLS signatures, derive identity-based decryption keys, and produce fraudulent SNARK proofs, all without touching the pairing itself. The pairing was never the hard part. The discrete logarithm inside the elliptic-curve groups was the only thing keeping the secret, and that is the thing Shor’s algorithm dissolves.

Source: P. W. Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer,” SIAM Journal on Computing, 1997, SIAM.

Two points sharpen the verdict. Bigger curves do not save it, because Shor’s cost grows only polynomially with the size of the group, the same reason resizing does not rescue RSA or ordinary ECC. And the threat is Shor’s rather than Grover’s: Grover’s quadratic search speedup weakens symmetric ciphers and hashes but leaves the discrete logarithm untouched, so it is Shor’s that ends pairing-based cryptography, and it ends it completely.

Pairing use case	What it builds	Rests on	Quantum verdict	Replace with
BLS signatures	Short, aggregatable signatures	EC discrete log	Broken by Shor’s	ML-DSA / SLH-DSA
Identity-based encryption	Email/username as public key	EC discrete log	Broken by Shor’s	Lattice-based IBE
Attribute-based encryption	Policy-gated decryption	EC discrete log	Broken by Shor’s	Lattice-based constructions
Pairing-based SNARKs (Groth16, KZG-based PLONK)	Succinct verifiable proofs	EC discrete log	Broken by Shor’s	Hash-based STARKs

Why does pairing-based cryptography fall while hash-based schemes survive?

It comes down to what the security rests on. A pairing scheme borrows all of its hardness from the elliptic-curve discrete logarithm, a structured number-theoretic problem with the hidden periodicity Shor’s algorithm is built to find. The pairing adds capability on top, but it adds no new hardness that would resist a quantum attacker. When Shor’s algorithm collapses the discrete logarithm, everything resting on it collapses at the same time, which is why pairing schemes fall together with RSA, ECDSA, and Ed25519.

Hash-based and lattice-based constructions rest on entirely different foundations. A hash-based scheme leans only on the one-way, collision-resistant behavior of a hash function like SHA-3, which has no number-theoretic structure for Shor’s to exploit and faces only Grover’s mild quadratic pressure. A lattice-based scheme rests on the hardness of geometry problems in high-dimensional grids, again with no periodic structure Shor’s can grab. This is the whole logic of the migration: the goal is to move the advanced constructions off the discrete logarithm and onto a foundation a quantum computer cannot dismantle.

Source: NIST, “Report on Post-Quantum Cryptography,” NISTIR 8105, April 2016, NIST.

What replaces pairing-based cryptography after quantum?

The replacement depends on which job the pairing was doing, because pairings cover several use cases and no single post-quantum primitive covers all of them at once. The mapping by function:

1. For signatures, including the aggregation that BLS provided, use ML-DSA or SLH-DSA. These are the finalized NIST post-quantum signature standards. Compact post-quantum aggregation is an active research area rather than a solved, standardized feature, so systems that leaned on BLS aggregation face a genuine engineering rework, not a one-line swap.
2. For pairing-based SNARKs, move to hash-based STARKs. A STARK rests only on the security of a hash function, so it is post-quantum secure while a Groth16-style pairing SNARK is not. The tradeoff is larger proof sizes, which is the cost of dropping the discrete-log dependency.
3. For identity-based and attribute-based encryption, the answer is lattice-based constructions. The advanced-encryption capabilities that pairings enabled are being rebuilt on the same lattice hardness that underpins ML-KEM, though this corner of the field is younger and less standardized than the signature and KEM lines.

Source: NIST, “NIST Releases First 3 Finalized Post-Quantum Encryption Standards,” August 13, 2024, NIST.

The practical takeaway for a migration is that pairing-based cryptography is a hidden pocket of quantum exposure that a naive inventory misses. It does not show up as “RSA” or “ECDSA” in a scan, it shows up as BLS, IBE, Groth16, or a validator aggregation scheme, and it is exactly as broken. Finding it is part of a real cryptographic inventory, and swapping it out cleanly is what crypto-agility is for.

Common misconceptions

• “Pairing-based cryptography is a newer, stronger kind of elliptic-curve crypto, so it’s more quantum-resistant.” It is more capable, not more quantum-resistant. It rests on the same elliptic-curve discrete logarithm as ordinary ECC and falls to Shor’s algorithm the same way.
• “BLS signatures are safe because they’re used in modern blockchains.” Being modern and widely deployed says nothing about quantum resistance. BLS rests on the elliptic-curve discrete logarithm and is quantum-broken, which is why proof-of-stake chains are actively researching hash-based replacements.
• “A quantum computer would have to break the pairing itself to forge a BLS signature.” It only has to solve the discrete logarithm inside the elliptic-curve group, which recovers the private scalar directly. The pairing is never the obstacle.
• “All zero-knowledge proofs are quantum-safe because they hide information.” Hiding information is a different property from resting on quantum-hard math. Pairing-based SNARKs like Groth16 are quantum-broken, while hash-based STARKs survive.
• “If I’ve inventoried my RSA and ECDSA, I’ve found all my quantum-exposed cryptography.” Pairing-based schemes hide under names like BLS, IBE, and Groth16 rather than under RSA or ECDSA, so a scan that only looks for the obvious algorithms leaves them in place.

Questions people ask

Is pairing-based cryptography quantum-safe? No. Every pairing scheme rests on the elliptic-curve discrete logarithm problem, which Shor’s algorithm solves in polynomial time, so a capable quantum computer recovers the private keys and the whole family breaks. It is quantum-vulnerable for the same reason ordinary elliptic-curve cryptography is.

Are BLS signatures broken by quantum computers? Yes. BLS signatures are built on pairing-friendly elliptic curves, and their security is the hardness of the elliptic-curve discrete logarithm. A quantum computer running Shor’s algorithm recovers the secret scalar and forges signatures, which is why blockchains that use BLS for validator aggregation are researching hash-based alternatives.

What is a bilinear pairing in simple terms? It is an operation that takes two points on an elliptic curve and combines them into a value in a third group, with the property that any secret multipliers on the two points slide out and multiply in the result. That lets a scheme check a multiplicative relationship between two hidden numbers without seeing either one, which is what makes short aggregatable signatures and identity-based encryption possible.

Are pairing-based zero-knowledge proofs quantum-safe? Pairing-based SNARKs such as Groth16 and KZG-based PLONK are not, because they inherit the discrete-log dependency of the pairing (a PLONK instantiated with a hash-based FRI commitment, as in Plonky2, is post-quantum secure). Hash-based STARKs are post-quantum secure because they rest only on a hash function. Which kind of proof a system uses decides its quantum exposure.

What replaces pairing-based cryptography in a post-quantum world? ML-DSA and SLH-DSA replace pairing-based signatures, hash-based STARKs replace pairing-based proofs, and lattice constructions are being built for the identity-based and attribute-based encryption use cases. There is no single drop-in replacement, so migrating off pairings is real engineering work rather than a parameter change.

Why is pairing-based cryptography easy to miss in a migration? Because it does not appear in an inventory as RSA or ECDSA. It shows up as BLS aggregation, identity-based encryption, or a Groth16 verifier, and a team that scans only for the household-name algorithms leaves these quantum-exposed constructions untouched.

---

Everything here is the map, given freely. When your team needs its own pairing-based footprint, the BLS validators, IBE deployments, and SNARK verifiers, found and sequenced for replacement, that’s what an alignment briefing is for.

Last verified 2026-07-12 · Maintained by Addie LaMarr, LaMarr Labs.