In short

The discrete-logarithm problem (DLP) is: given a cyclic group G = \langle g\rangle of order N and an element h \in G, find the integer x \in \{0, 1, \ldots, N-1\} with g^x = h. Classically it is sub-exponential hard for integer groups (best algorithm: a GNFS variant) and square-root hard for elliptic curves (Pollard rho, O(\sqrt N)). ECC-256 provides roughly 128-bit classical security — which is why it underlies TLS key exchange, UPI transaction signatures, Aadhaar eSign, Bitcoin, and Ethereum. Shor's 1994 paper included a second algorithm — alongside factoring — that solves DLP in polynomial time on a fault-tolerant quantum computer. The construction is a two-register phase-estimation circuit: one register for the exponent of g, one for the exponent of h, followed by a QFT on each. A measurement yields a pair (c, d) with c \cdot x + d \equiv 0 \pmod N, and one linear Diophantine solve recovers x. Resource-wise, breaking 256-bit ECC takes roughly 2330 logical qubits and \sim 10^{10} T gates (Roetteler-Naehrig-Svore-Lauter 2017) — actually cheaper than breaking RSA-2048. The post-quantum response: lattice-based KEMs (Kyber), lattice signatures (Dilithium), hash-based signatures (SPHINCS+). India's CERT-In has published crypto-agility guidelines aligned with NIST's 2024 standards; Aadhaar and UPI migrations are in progress.

Open the https://www.npci.org.in site. Look at the lock icon. Behind that lock, your browser and the NPCI server just finished a handshake called TLS 1.3, which begins with an Elliptic-Curve Diffie-Hellman key exchange. The same mechanism runs when you tap Pay on Google Pay, when you sign an Aadhaar e-document on DigiLocker, when your Signal app rings a friend. The security of every one of those handshakes rests on a single problem: find x such that g^x = h in a particular cyclic group. Classically, the best known algorithms for this problem have been sub-exponential (for integer groups) or square-root (for elliptic curves) since the 1970s.

In 1994, the same paper that gave the world Shor's factoring algorithm gave the world a second algorithm — one that solves discrete logarithm in polynomial time on a fault-tolerant quantum computer. Most people never hear about it, because "RSA is dead" is a simpler headline than "DLP is dead." But DLP is actually the more consequential casualty: elliptic-curve cryptography is used in more places than RSA, and breaking ECC on a quantum computer is, by current resource estimates, cheaper than breaking RSA.

This chapter puts the second half of Shor's paper in front of you. You will see the problem stated precisely, the classical cost, the quantum construction as a two-register phase estimation, the worked toy example, and the honest resource estimate for breaking cryptographically relevant ECC. The hype and the timeline are both calibrated; the post-quantum migration story is the same story you saw in the RSA chapter, but with a different set of affected protocols.

The discrete-logarithm problem

A cyclic group is a set of elements, a rule for combining them, and one special element g (the generator) whose powers g^0, g^1, g^2, \ldots produce every element in the set before cycling back to g^0. The size of the group — how many distinct powers you get before the cycle closes — is the order N.

The discrete-logarithm problem is the inverse question:

Discrete logarithm problem (DLP)

Given a cyclic group G = \langle g\rangle of order N and a target element h \in G, find the unique integer x \in \{0, 1, \ldots, N-1\} satisfying

g^x = h.

The name is an analogy to ordinary logarithms. If g and h were real numbers, x = \log_g h — a continuous function computed by taking a logarithm on a calculator. In a finite cyclic group the exponents are integers, there is no continuous logarithm, and the only honest algorithm is a search.

Two families of groups matter in cryptography:

The discrete-logarithm problemA diagram with a generator element g on the left, an arrow labelled exponentiation easy running to the right ending at an element h equals g to the x, and an arrow going back labelled discrete log hard, asking for x given g and h. Below, two example group families are labelled: multiplicative mod p for Diffie-Hellman, and elliptic curve groups for ECC in TLS, UPI, Bitcoin.generatorgpublic, known to alltargeth = g^xpublic, visible on wireeasy: exponentiaterepeated squaring, O(log N) operationshard: find xno classical poly-time algorithm known$\mathbb{Z}_p^*$ (mod-p ints): Diffie-Hellman, ElGamalp typically 2048-3072 bitselliptic curve: ECDH, ECDSA (Aadhaar, UPI, Bitcoin)curves typically 256-384 bits
The DLP trapdoor. Exponentiating $g$ to any power is fast (repeated squaring, $O(\log N)$ multiplications). Recovering the exponent from the result is classically hard. Diffie-Hellman and ElGamal use integer groups; modern TLS, UPI, and Aadhaar signatures use elliptic-curve groups — faster and smaller, but identically hard under classical analysis.

The cryptographic move is exactly the same as RSA's factoring move: multiplication is easy, but inverting it is hard. Here "multiplication" is the repeated-squaring algorithm that computes g^x from x in O(\log N) group operations, and "inverting" is recovering x from g^x.

How Diffie-Hellman uses DLP

Two parties, Alice in Bengaluru and Bob in Mumbai, want to agree on a shared secret key over a public network. Classical Diffie-Hellman (1976):

  1. Alice and Bob agree publicly on g and the group G (published in the RFC).
  2. Alice picks a random private integer a, computes A = g^a, sends A to Bob.
  3. Bob picks a random private integer b, computes B = g^b, sends B to Alice.
  4. Alice computes B^a = g^{ab}. Bob computes A^b = g^{ab}. Both arrive at the same shared secret.

An eavesdropper sees g, A = g^a, B = g^b on the wire — but not a or b. To compute g^{ab}, she would need to recover a from A (or b from B), which is exactly the discrete-log problem. Break DLP, and you break the handshake.

TLS 1.3 uses the elliptic-curve version, ECDH, over a specific curve (Curve25519 or NIST P-256). Same algebra, different group. UPI, Aadhaar eSign, Signal, WhatsApp, iMessage — every modern handshake in Indian digital infrastructure — ends up calling ECDH at some layer.

The classical cost

How hard is DLP classically? The answer depends on the group.

\mathbb{Z}_p^* (integer mod-prime groups). The best classical algorithm is a number-field-sieve variant specialised for DLP. Cost: sub-exponential, in the same L_p[1/3, c] family as GNFS for factoring. A 3072-bit prime gives roughly 2^{128} classical security. This is why classical Diffie-Hellman typically uses 2048-3072 bit primes.

Elliptic curves. The mod-prime tricks do not transfer: the best classical algorithm is Pollard's rho adapted to the curve group, with cost O(\sqrt N). For an n-bit curve, that is O(2^{n/2}) — exponential in the bit size, unlike the sub-exponential RSA/DH case. This is why ECC-256 (a 256-bit curve) is believed to give \sim 128-bit classical security, matching the RSA-3072 and DH-3072 bars but with vastly smaller keys.

That is the practical reason ECC won: at the same classical security level, ECC-256 keys are 12× smaller than RSA-3072 keys. Every TLS handshake saves bandwidth. Every mobile app saves battery verifying ECDSA instead of RSA. Aadhaar-eSign uses ECDSA over NIST P-256 for the same reason.

Classical security level RSA key size DH prime size ECC curve size
2^{80} 1024 bits 1024 bits 160 bits
2^{112} 2048 bits 2048 bits 224 bits
2^{128} 3072 bits 3072 bits 256 bits
2^{192} 7680 bits 7680 bits 384 bits

Why ECC sizes are half the "bit-equivalent" of RSA: the cost of classical factoring (GNFS) grows as \exp(\tilde O(n^{1/3})), while Pollard rho on an elliptic curve grows as \exp(n/2). Setting those equal gives RSA n \approx 12 \cdot (\text{ECC } n) at the relevant security levels, which is the rule of thumb.

Now — and this is the twist of the quantum story — ECC's classical win turns into a disadvantage under Shor. Quantum DLP runs in polynomial time regardless of the group. A smaller group takes fewer qubits to represent, fewer gates to exponentiate in, fewer operations to attack. ECC is classically strong, quantumly weak-per-qubit.

The quantum construction

Here is Shor's 1994 quantum algorithm for DLP, adapted to a cyclic group G = \langle g\rangle of known order N. You want x with g^x = h. The trick is phase estimation on a two-register operator that encodes both g and h simultaneously.

The factoring version (ch. 77) used one register to hold an exponent a and phase-estimated the eigenvalue of U_g|y\rangle = |gy \bmod N\rangle. For DLP, you need two exponents — one for g, one for h — because the secret x links them. Two registers, two Hadamard towers, two QFTs, one joint modular exponentiation.

The circuit at a glance

Three registers on the quantum computer:

  1. Register A — t = \lceil 2\log_2 N\rceil qubits. Will hold the first exponent, a.
  2. Register B — t qubits. Will hold the second exponent, b.
  3. Register C — n = \lceil\log_2 |G|\rceil qubits. Will hold the group element g^a \cdot h^b.

The five steps:

  1. Prepare register A in |0\rangle^{\otimes t}, register B in |0\rangle^{\otimes t}, register C in |1\rangle (the identity element of G).
  2. Apply H^{\otimes t} to both A and B. Now both are in uniform superposition over all 2^t exponents.
  3. Compute g^a \cdot h^b into register C, with a and b read from A and B. This is two parallel modular-exponentiation ladders, one controlled by A (raising g), one controlled by B (raising h).
  4. Apply the inverse QFT to register A and, separately, to register B.
  5. Measure A and B. You get two integers c \in \{0, 1, \ldots, 2^t - 1\} and d \in \{0, 1, \ldots, 2^t - 1\}.
Quantum DLP circuit — two-register phase estimationA circuit diagram with three register groups. Register A at top: t ancillas starting ket zero, Hadamards, then controlled g-to-the-a modular exponentiation, then inverse QFT, then measurement yielding integer c. Register B in middle: t ancillas starting ket zero, Hadamards, then controlled h-to-the-b modular exponentiation, then inverse QFT, then measurement yielding integer d. Register C at bottom in accent: n data qubits initialised to ket one, used as target for both controlled exponentiations, left untouched at the end. A bracket labels the joint modular exponentiation g to the a times h to the b.Quantum DLP circuit (two-register phase estimation)|0⟩|0⟩⋮|0⟩|0⟩⋮|1⟩Reg A (a): tReg B (b): tReg C: n dataHHHHg^a · h^b mod |G|joint modular exponentiationQFT⁻¹QFT⁻¹cdMeasured pair (c, d) satisfies c + d·x ≡ 0 (mod N)
Two-register quantum DLP. Registers A and B each hold one exponent in superposition; register C receives the joint product $g^a \cdot h^b$. An inverse QFT on each ancilla register extracts a pair of integers whose ratio encodes the secret exponent $x$. The circuit structurally mirrors Shor's factoring circuit, but with two phase-estimation registers in place of one.

Why this produces x

Follow the state through. After step 2, register A \otimes B is the uniform superposition

\frac{1}{2^t}\sum_{a, b} |a\rangle|b\rangle|1\rangle.

After step 3 the joint exponentiation sends |a\rangle|b\rangle|1\rangle \to |a\rangle|b\rangle|g^a h^b\rangle.

Why register C ends up encoding a linear combination of a and b: because h = g^x, you have g^a h^b = g^a (g^x)^b = g^{a + bx}. The exponent in register C is a + bx \pmod N, which is the linear function of a and b whose coefficients reveal x. Phase estimation on the A,B registers will read off those coefficients.

Now the amplitude in A,B is no longer uniform — it has a structure. Group together all (a, b) pairs that produce the same y = a + bx \bmod N in register C; they form a single hyperplane in the (a, b) lattice. After the inverse QFT on each register, the standard phase-estimation argument tells you that a measurement of (c, d) is concentrated, with high probability, on pairs satisfying

\frac{c}{2^t} + \frac{d}{2^t} \cdot x \;\equiv\; 0 \pmod 1

which, multiplied through by 2^t and rounded, becomes

c + d \cdot x \;\equiv\; 0 \pmod N.

This is a linear congruence in the single unknown x. Compute d^{-1} \bmod N using the extended Euclidean algorithm (requiring \gcd(d, N) = 1; if not, take a second run to get a (c', d') with d' coprime to N), then

x \;\equiv\; -c \cdot d^{-1} \pmod N.

One linear solve, one modular inverse, and you have x.

Complexity

Gate count: the joint modular exponentiation is the dominant cost, exactly as in Shor's factoring. For an n-bit group order, O(n^2) Toffolis per controlled multiplication, O(n) multiplications in each exponentiation ladder, and two such ladders — total O(n^3) Toffolis. The two QFTs contribute O(n^2) each with Coppersmith approximation reducing them to O(n \log n). Same O(n^3) complexity class as Shor's factoring, with slightly larger constants.

Qubit count: three registers of roughly n qubits each plus modular-arithmetic scratch — \sim 6n logical qubits total, marginally more than the \sim 5n of Shor's factoring.

Worked example: DLP on a small group

Run the whole thing on a group small enough to check by hand. Take G = \mathbb{Z}_{11}^*, the multiplicative group modulo the prime 11. Its order is \varphi(11) = 10. Check that g = 2 is a generator by listing its powers:

2^0, 2^1, 2^2, \ldots, 2^9 \pmod{11} \;=\; 1, 2, 4, 8, 5, 10, 9, 7, 3, 6.

All ten non-zero residues appear, so g = 2 generates the full group.

Example 1: find $x$ with $2^x = 9 \pmod{11}$

Setup. g = 2, h = 9, group order N = 10. By inspection from the list above, x = 6. The task: show how Shor's quantum DLP algorithm arrives at the same x through the circuit, step by step.

Step 1. Choose t with 2^t \ge N^2 = 100, so t = 7 gives 2^t = 128. Registers A and B have 7 qubits each; register C has \lceil\log_2 10\rceil = 4 qubits. Total: 18 qubits. Why 2^t \ge N^2: phase estimation needs enough resolution to distinguish fractions with denominator up to N, so t must satisfy 2^{-t} \lesssim 1/N^2, giving t \ge 2\log_2 N.

Step 2. Initialise A in |0\rangle^{\otimes 7}, B in |0\rangle^{\otimes 7}, C in |0001\rangle (the binary encoding of 1, the identity element). Apply H^{\otimes 7} to A and B.

Step 3. Run the joint modular exponentiation. The state becomes

\frac{1}{128}\sum_{a, b = 0}^{127} |a\rangle|b\rangle|\,2^a \cdot 9^b \bmod 11\,\rangle.

Rewrite 9 = 2^6, so 2^a \cdot 9^b \equiv 2^{a + 6b} \pmod{11}, and because the order of 2 is 10, this equals 2^{(a + 6b)\bmod 10} \pmod{11}. Why rewriting in terms of 2: register C now encodes a pure function of the single combination a + 6b \bmod 10. That collapses the double sum into ten slices, one per residue class, which is what makes the phase-estimation interference work.

Step 4. Apply \text{QFT}^{-1} to A and to B. Standard phase-estimation analysis: the resulting probability distribution on outcomes (c, d) is sharply peaked on pairs satisfying

c + 6d \equiv 0 \pmod{10}.

Step 5. Measure. Suppose the measurement returns (c, d) = (4, 1). (Concrete values a simulator can verify: 4 + 6 \cdot 1 = 10 \equiv 0 \pmod{10}. Other likely outcomes: (8, 2), (2, 3), (6, 4), all satisfying c + 6d \equiv 0.)

Step 6. Classical post-processing. Solve c + x d \equiv 0 \pmod{10} for x:

4 + x \cdot 1 \equiv 0 \pmod{10} \implies x \equiv -4 \equiv 6 \pmod{10}.

Need d^{-1} \bmod 10 — here d = 1, trivially its own inverse. For d = 3 you would compute 3^{-1} = 7 \pmod{10} and recover x = -c \cdot 7 \bmod 10.

Step 7. Verify. 2^6 = 64 = 5 \cdot 11 + 9 \equiv 9 \pmod{11}. Match.

Result. x = 6. The quantum circuit performed one run (18 qubits, \sim 200 Toffoli gates) and the classical post-processing took one linear solve.

DLP on Z_11 star: worked traceFlow diagram of the worked example. Step one: set up, g equals two, h equals nine, N equals ten. Step two: quantum circuit returns measured pair c equals four d equals one. Step three: solve four plus six times d equivalent zero mod ten. Step four: x equals six. Step five: verify two to the six equals sixty-four equals nine mod eleven.Trace: solve 2^x = 9 (mod 11)Step 1: setupg = 2, h = 9group Z_11*, order N=10Step 2 (Q)t = 7 ancillas18 qubits totalmeasure: (c, d) = (4, 1)Step 3: solve linearc + x · d ≡ 0 (mod N)4 + x · 1 ≡ 0 (mod 10)x ≡ −4 ≡ 6 (mod 10)x = 6Step 4: verify2^6 = 6464 = 5·11 + 9≡ 9 (mod 11) ✓secret exponent recovered
End-to-end trace of quantum DLP for $g = 2, h = 9$ in $\mathbb{Z}_{11}^*$. The two-register phase estimation measures a linear congruence; one classical solve produces $x = 6$. On a real simulator this runs in milliseconds; on a real quantum computer this particular example has not yet been demonstrated end-to-end without compile-time shortcuts, for the same reasons that honestly factoring $15$ is hard.

What this shows. The algorithm has the same shape as Shor's factoring: a quantum core doing phase estimation, a classical core doing one linear solve. For a 2-bit group order, the circuit uses 18 qubits; for a 256-bit curve, it will use thousands of logical qubits — and millions of physical qubits after error correction.

Resource estimate: breaking ECC-256

Everything above is the theory. How much quantum hardware does it take to run the algorithm on a real cryptographic target? The answer — for ECC-256, the curve underneath TLS 1.3, Aadhaar eSign, and Bitcoin — is surprisingly modest by Shor standards, and cheaper than breaking RSA-2048.

Example 2: resource estimate for ECC-256

Setup. NIST curve P-256: a 256-bit elliptic curve over a prime field of \sim 2^{256} elements. Group order N \approx 2^{256}. Classical security: \sim 128 bits (Pollard rho).

Logical qubits. The Roetteler-Naehrig-Svore-Lauter 2017 analysis (arXiv:1706.06752) gives a detailed count: about 9n logical qubits for a naive implementation, optimised down to 6n + \text{scratch} with careful reversible arithmetic. For n = 256: \approx 2330 logical qubits. Why more than the theoretical 6n minimum: elliptic-curve point addition is computationally richer than integer multiplication. Each point addition requires several modular inversions (field-element inverses), and each inversion needs its own scratch register. That overhead pushes the count above Shor-factoring's tighter 5n + 4.

T-gate count. Roetteler et al. count \sim 1.4 \times 10^{10} T gates for the whole algorithm, dominated by reversible modular inversion during point addition. Compare: Shor's factoring of RSA-2048 needs \sim 10^{10} T gates after Gidney-Ekerå's windowed arithmetic, and uses \sim 6000 logical qubits — more logical qubits than ECC-256, for similar T-count.

Physical qubits under surface code. Each logical qubit encoded in a d \times d surface-code patch at distance d \approx 25 costs \sim 700 physical qubits. Magic-state distillation for the 10^{10} T gates costs another \sim 10^6 physical qubits across several parallel factories. Total: roughly

2330 \cdot 700 \;+\; 10^6 \;\approx\; 2.6 \times 10^6 \text{ physical qubits}.

Call it \sim 20 million physical qubits with realistic pipelining and buffer overhead — roughly the same order as RSA-2048.

Runtime. On superconducting hardware with 1\,\mu\text{s} surface-code cycles and pipelined magic-state consumption, Roetteler et al. estimate \sim 10 hours for the full run, in the same order-of-magnitude neighbourhood as Gidney-Ekerå's 8 hours for RSA-2048.

Result. Breaking 256-bit ECC takes roughly 2330 logical qubits and \sim 20 million physical qubits under surface code — fewer logical qubits than RSA-2048 needs (6000 for RSA), although the physical-qubit ceiling is similar after distillation. Put differently: if a quantum computer capable of breaking RSA is ever built, it is automatically capable of breaking ECC too, usually a little faster.

RSA-2048 vs ECC-256 quantum resource comparisonA two-bar comparison chart. Left group: RSA-2048 logical qubits six thousand, ECC-256 logical qubits two thousand three hundred and thirty. Right group: physical qubits both about twenty million. A horizontal line marks the current hardware ceiling of roughly one thousand physical qubits.Quantum resource comparison (log scale)10³10⁴10⁵10⁶10⁷qubit countLogical qubitsRSA-2048~6000ECC-2562330Physical qubits (SC, d≈25)RSA-20482×10⁷ECC-256~2×10⁷current hardware ceiling (~10³ physical)
Comparing the quantum cost of breaking RSA-2048 (Gidney-Ekerå 2021) and ECC-256 (Roetteler et al. 2017). ECC-256 needs fewer logical qubits (2330 vs 6000) because the group is smaller, though the physical-qubit ceiling after error correction lands in the same tens-of-millions range. Both sit four orders of magnitude above today's largest machines.

What this shows. The asymmetry of the classical world — where ECC-256 matches RSA-3072 on security per bit — does not survive the quantum transition. Quantum DLP scales polynomially in the group-order bit-length, so a 256-bit curve is fundamentally cheaper to attack than a 2048-bit RSA modulus. Every protocol that migrated to ECC for performance reasons is, against a fault-tolerant adversary, slightly less secure than the legacy RSA variant it replaced. This is not an argument for reverting to RSA — both are broken by Shor. It is an argument for moving past both, to post-quantum schemes that Shor cannot touch.

Hype check. "Shor breaks Diffie-Hellman and ECC" is a true statement that is regularly overclaimed. What is not true: quantum computers existing today can break any of these. The best publicly demonstrated end-to-end quantum factoring is N = 21 (with compile-time shortcuts that do not generalise). Breaking real ECC-256 or RSA-2048 requires thousands of logical qubits encoded on millions of physical qubits, and that hardware is a decade-plus away under optimistic roadmaps.

What is true, and policy-relevant: harvest now, decrypt later. An adversary can record an ECDH key-exchange transcript today — on a public network, at a coffee shop, or at a backbone tap — and decrypt it fifteen years from now when the quantum computer exists. If the session key protected content that matters in 2040 (Aadhaar biometric templates, state-level diplomatic traffic, long-lived signed medical records), the risk clock is already ticking. This is why NIST standardised post-quantum KEMs and signatures in 2024 and why CERT-In published crypto-agility guidance the same year: the migration must be done now, even though the threat remains years away.

What is not threatened by Shor: symmetric encryption (AES-256 remains secure with a 2\times key-length hit from Grover), hash-based signatures (SPHINCS+), lattice-based cryptography (Kyber, Dilithium, Falcon), and code-based cryptography (Classic McEliece). The transition is underway and the toolkit is ready.

Common confusions

Going deeper

The material above is the complete quantum DLP algorithm plus the ECC resource estimate. The "going deeper" material below covers the original Shor 1994 construction, the isogeny-based detour that failed, India's post-quantum-crypto migration specifics, and the linear-Diophantine solve in more detail.

Shor's 1994 DLP paper — the exact statement

Peter Shor's paper (Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, arXiv:quant-ph/9508027) presented DLP first in \mathbb{Z}_p^* and then remarked that the same algorithm works for any cyclic group with an efficient group-operation circuit. The remark is load-bearing: it is what lets the same algorithm attack elliptic curves a decade before Roetteler et al. worked out the detailed resource count.

The paper's complexity claim: if the group operation and its inverse can be computed by G(n) quantum gates on an n-bit register, then DLP runs in O(n^2 G(n)) gates. For integer groups G(n) = O(n^2), giving O(n^4). For elliptic curves G(n) = O(n^3) because point addition requires modular inversion, pushing DLP to O(n^5). Both are polynomial. Both are what gets extracted in the detailed resource estimates.

The SIKE break — isogeny-based crypto's false dawn

Between 2011 and 2022, a class of post-quantum candidates called supersingular isogeny key encapsulation (SIKE) was under active consideration for NIST standardisation. The idea: use the hardness of computing isogenies (certain maps) between supersingular elliptic curves, a problem believed to resist both classical and quantum attacks.

Then in July 2022, Wouter Castryck and Thomas Decru published a classical polynomial-time attack (eprint 2022/975) that broke SIKE on a laptop in under an hour. Not a quantum attack — a classical mathematical breakthrough exploiting hidden structure in supersingular curves. SIKE was immediately withdrawn from the NIST competition.

The lesson for practitioners: post-quantum hardness is a research-level assumption, and even candidates that survive a decade of review can break. This is why NIST's 2024 standards chose lattice-based schemes (Kyber, Dilithium, Falcon) — the lattice assumptions have had the longest sustained scrutiny without break — and hash-based schemes (SPHINCS+), whose security reduces to hash-function properties that are among the best-understood in cryptography.

Post-quantum replacements, by function

Function Pre-quantum (broken by Shor) Post-quantum (NIST 2024)
Key encapsulation RSA-OAEP, ECDH, DH Kyber (ML-KEM)
Signatures RSA-PSS, ECDSA, EdDSA Dilithium (ML-DSA), Falcon (FN-DSA)
Signatures (hash-based) — SPHINCS+ (SLH-DSA)
Symmetric encryption AES-128, AES-256 AES-256 (unchanged, 128-bit post-quantum)
Hash functions SHA-256, SHA-3 SHA-256, SHA-3 (unchanged)

Kyber key encapsulation produces \sim 1 KB of traffic per handshake versus ECDH's \sim 32 bytes — a 30\times bandwidth hit, tolerable on broadband, noticeable on constrained IoT. Dilithium signatures are \sim 2.5 KB versus ECDSA's \sim 64 bytes — a bigger hit, especially on Aadhaar-style systems that sign millions of transactions a day.

India's post-quantum-crypto posture

India's cryptographic estate touches nearly every citizen:

The National Quantum Mission (₹6003 crore over 8 years, launched April 2023) funds four thematic hubs, one of which — the Quantum Communication hub at C-DOT — has post-quantum-crypto migration as an explicit deliverable. TCS, Infosys, Wipro, and HCL all host PQC practices that are certifying Open Quantum Safe (liboqs) integrations for their enterprise products. IITs at Madras, Bombay, and Kanpur run graduate programmes in PQC; IISc Bangalore hosts the Indian Cryptology Research Society.

The migration calendar — complete by 2030, ahead of the earliest plausible Shor deployment in 2035 — is the intended order. The harvest-now-decrypt-later threat is the reason the clock started in 2024 rather than 2030.

Solving the linear congruence — detail

In the worked example the measurement returned (c, d) and the classical solve was one line. The general case has a subtlety: the measurement concentrates near pairs with c + dx \equiv 0 \pmod N, but the quantum procedure sometimes gives pairs where \gcd(d, N) > 1. When that happens, d has no multiplicative inverse mod N, and you cannot solve for x uniquely from one pair.

The fix is standard: run the circuit two or three times, collect several (c_i, d_i) pairs, and build the system

c_1 + d_1 x \equiv 0 \pmod N, \quad c_2 + d_2 x \equiv 0 \pmod N, \quad \ldots

Use the extended Euclidean algorithm on the coefficients to find \gcd(d_1, d_2, \ldots, N) — with high probability this equals 1 after three or four runs, allowing a Bézout combination to recover x. Shor's original paper proves the expected number of runs is O(1).

For the ECC-256 estimate, Roetteler et al. budget for five total runs as a safety factor. That is the factor of \sim 5 buried inside the \sim 10-hour runtime: the quantum circuit itself executes in a few hours; the runs aggregate to the full wall-clock.

Why the quantum DLP algorithm does not extend to general groups

Shor's algorithm crucially uses the cyclic structure of the group: there is one generator, exponents live in \mathbb{Z}_N, and the QFT on \mathbb{Z}_N extracts them. For non-cyclic abelian groups (direct products of cyclic groups), the algorithm generalises with a QFT over the direct product, and it still runs in polynomial time — this is the abelian hidden subgroup problem.

For non-abelian groups, the story breaks. The quantum Fourier transform on non-abelian groups is more complex (it uses the irreducible representations, which are matrix-valued), and the standard phase-estimation trick does not straightforwardly extract hidden structure. The dihedral hidden subgroup problem and the symmetric group hidden subgroup problem are believed to resist Shor-style attacks — and they are candidates for future post-quantum cryptography.

This is why the post-quantum migration does not use different cyclic groups as a hiding spot: every cyclic group falls to Shor. It uses lattices, hash functions, codes, and multivariate polynomials — structures that do not reduce to hidden-subgroup problems in abelian groups, and therefore sit outside Shor's reach as currently understood.

Where this leads next

References

  1. Peter Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer (1994/1995) — arXiv:quant-ph/9508027. The founding paper; DLP in §5.
  2. Martin Roetteler, Michael Naehrig, Krysta Svore, Kristin Lauter, Quantum resource estimates for computing elliptic curve discrete logarithms (2017) — arXiv:1706.06752. The ECC-256 resource estimate.
  3. Wikipedia, Discrete logarithm.
  4. Wouter Castryck and Thomas Decru, An efficient key recovery attack on SIDH (2022) — eprint 2022/975. The classical attack that ended isogeny-based crypto.
  5. NIST, Post-Quantum Cryptography Standardization — the 2024 standards (FIPS 203, 204, 205).
  6. Wikipedia, Elliptic-curve cryptography.