New Approach to Quantum Lower Bounds in Generic Algorithms

A New Approach to Generic Lower Bounds: Classical/Quantum MDL, Quantum Factoring, and More Minki Hhan UT Austin 2025/05/06

Motivations & Summary and an important related work

Actual runtime of Shors algorithm? [Gidney & Eker 21] Shor s algorithm solves Elliptic curve DLP (and RSA2048/DL modulo prime) in about one day! (cf. classically about 700~800-bit in 5000 core years) Better algorithm? Assuming nice scalability, nicely behave error correcting, Some (quantum) circuit optimizations Some algorithm improvements (reduces constant factors) [HYamYun 24] Quantum generic lower bound for DL That is, Shor s algorithms is optimal wrt group operations

More questions Quantum factoring lower bound? Adversary s goals may be to find, given 3 DL instances ?,??1,??2,??3 (3-DL) all solutions ?1,?2,?3 (1-out-of-3 DL) one solution among ?1,?2, ?3 (One-more DL) all 3 solutions with 2 DL queries

More questions Quantum factoring lower bound? Adversary s goals may be to find, given 3 DL instances ?,??1,??2,??3 (3-DL) all solutions ?1,?2,?3 (1-out-of-3 DL) one solution among ?1,?2, ?3 (One-more DL) all 3 solutions with 2 DL queries What about quantum lower bound? m-DL has slightly better algorithm [HYY 24] and related to pqPAKE Classical lower bounds [Yun 15] [YK 17,AGK 20] [BFP 21]

Resolves two questions in [HYY24] [HYY24] algorithm is optimal Tight for composite order Results 1. Quantum multiple DL lower bounds wrt group operations 2. Quantum factoring lower bounds wrt ring operations (*conditional) 3. Alternative classical proofs using the same tool! (bonus: preprocessing classical OMDL lower bound, which is new!) cf. previous proofs Lower bounds Proof technique DL,CDH,... Schwartz-Zippel lemma MDL, OM-DL, Search-by-hyperplane Preprocessing DL, Compression, bit-fixing, Quantum DL Simulation (It s simple!) Refs [Shoup,Maurer, ] [Yun,YK,AGK,BFP] [GK,CDG,AHP] [HYY24] *It is unavoidable. We will talk about it if time permits.

Proof ideas for classical MDL

DL in (Classical) Generic group model (GGM) Algorithm accesses elements of group ? in a black-box way (We use additive group by default) It is ??= ??+ ?? ??= ??+ ?? ?? ?0= ? ?1= ? ? ?? Gop query: What is ??+ ??? Oracle Equality query: Is ??= ??? b=1 if ??= ?? b=0 if ?? ?? ? Alice the algorithm

Simulated game for DL in GGM All group elts are stored by Challenger and Alice stores polynomials ?0= ? ?1= ? ? ?? ?? ??= = ??? + ?? = ??? + ?? ??= ?0= 1 ?1= ? ??? + ?? ? ??? + ?? ? What is (?-th)+(?-th)? ??= ??+ ?? ??= ??+ ?? Charlie the challenger Simulated Alice

Simulated game for DL in GGM Compassion lemma (roughly): If Charlie sends ? 0,1?to Alice whp, Charlie must send ?(?) bits whatever Alice does, protocol is, etc. I want to send random x Let s assume Alice is deterministic and makes ?(?) queries There are ? ?2pairs of (?,?) ?? = ??? + ?? = ??? + ?? ?? ?0= 1 ?1= ? Alice find (first) equality ??= ?? What is (?-th)+(?-th)? Compassion lemma for DL (roughly): ? ? is log|?| bits ??= ??+ ?? (?,?) is represented by 2log? bits So, ????? ???|?| must hold (?,?) ? = ?? ?? ?? ?? to solve DL with q-query ? ?0= ? ?1= ? ? Is ??= ??? ? Charlie the challenger Simulated Alice Yes only if ?,? = (?,?)

Simulated game for ?-DL in GGM I want to send random x1, .,xm with some work the same proof works! ?1= ?1 Alice find m equalities ???= ??? for k=1,..m ?0= 1 Compassion lemma for MDL (roughly): ?1, ,?? ? is ? log|?| bits ?1,?1, ,(??,??) is represented by log?2 So, to solve m-DL with q-query, it must holds ? ??= ?m ?2 ? bits ? log ? ?1,?1, ,(??,??) ?1= ?1 ? ? ? ?0= ? ??= ?? ? Charlie the challenger Simulated Alice

Proof ideas for quantum MDL (and factoring)

Quantum generic group operation Control bit (controlled) Quantum gop: ?,? ?? ??,?? ? ?,? ?? ??+ ???,??? Assume (i,j) s are always classical ??,?? ? and (?,?) ?? Gop query: What is (?-th)+(?-th)?

Quantum generic group operation Control bit (controlled) Quantum gop: ?,? ?? ??,?? ? ?,? ?? ??+ ???,??? Assume (i,j) s are always classical ??,?? ??+ ???,??? ? and (?,?) ?? Gop query: What is (?-th)+(?-th)?

Quantum generic group operation Control bit (controlled) Quantum gop: ?,? ?? ??,?? ? ?,? ?? ??+ ???,??? Assume (i,j) s are always classical ??,?? ??+ ???,??? ? and (?,?) ?? Gop query: What is (?-th)+(?-th)?

DL in QGGM In group operation query, Oracle sends 1 qubit (for controlled bit b) In equality query, Oracle sends 1 bit to Alice Quantum interactive compassion lemma (roughly): If Charlie sends ? 0,1?to Alice through any interactive protocol whp, Charlie must send ?(?)qubits whatever Alice does, protocol is, etc. Oracle wants to send ? ?, which is log|?| bits 1 query requires 1 qubits from Oracle to Alice To solve DL with q queries, ? log |?|

m-DL in QGGM (with coherent indices) ?,??,??? ???, ,??? for 1 ?,? ? Oracle wants to send ?1, ,?? ? of ? log|?| bits 1 quantum gop requires log2?2qubits from Oracle to Alice To solve DL with q quantum gop queries, ? log(2?2) ? log |?| ? ?,??,??? ???+ ???, ,??? 1+2 log M = log(2M2) qubit ? Faster m-DL algorithm like [HYY24] requires QRAM access

Factoring in quantum generic ring model? Ring elements are stored in black box, and only accessible via oracle The same proof works ? ? = /? for product of two primes ? = ?? Final operation: computing gcd(?? 1,?) is NOT in the model! We prove: 1) Order finding requires (log?) quantum ring op (Shor s) (w/o gcd) 2) lifted factoring also requires (log?) quantum ring op if it has some smallness property (which is essential for Regev s speed-up) Find r s.t. ?? 1 ??? ? N must not be given! gcd(?,?) > 1 is computed at the end and ? is somewhat small

Open problems 1. CDH or Decisional lower bounds? high degree like CDH must require some algebraic geometry as in [AGK20] DDH time-space lower bounds is recently resolved [ABGXY24] 2. Our tool for QROM or other model lower bounds? 3. Qcircuit lower bound for Shor/Regev-like factoring algorithms? If approxSVP is easy, there is ?(log?) size quantum circuit [Reg25]

Thanks!