DISCRETE LOGARITHMS

IN QUASI-POLYNOMIAL TIME

IN FINITE FIELDS OF SMALL CHARACTERISTIC

Benjamin Wesolowski

ECC 2019: 23rd Workshop on
Elliptic Curve Cryptography
December 2019
Bochum, Germany

Based on a joint work withThorsten Kleinjung

RIGOROUS ORHEURISTIC
If it seems to work, is it
good enough?

RIGOROUS ALGORITHMS FOR DLP
Discrete logarithm problem (DLP) in finite fields of fixedcharacteristic (𝔽pn with p fixed and n → ∞… think 𝔽2n):‣ Given a generator g of 𝔽p×n and an arbitrary element h, find aninteger m such that h = gm

➡ Pomerance (1987) proved complexity Lpn(1/2)➡ We prove it can be done in quasi-polynomial time

For constant p:
Lpn(α) = eO((log pn)α (log log pn)1 – α)quasi-poly(log pn) = e(log log pn)O(1)=enO(1)O(1)log(n)=eRIGOROUS ALGORITHMS FOR DLP
Discrete logarithm problem (DLP) in finite fields of fixedcharacteristic (𝔽pn with p fixed and n → ∞… think 𝔽2n):‣ Given a generator g of 𝔽p×n and an arbitrary element h, find aninteger m such that h = gm

➡ Pomerance (1987) proved complexity Lpn(1/2)➡ We prove it can be done in quasi-polynomial time
Theorem: Given any prime number p and any positive integer n,×
the discrete logarithm problem in the group 𝔽pn can be solved in

expected time (pn)2log2(n) + O(1)1922

KRAITCHIKNO COMPLEXITYTIMELINE
1968

MILLER, WESTERN1976

DIFFIE, HELLMAN

1979

ADLEMAN1982

HELLMAN, REYNERI

L(1/2)

1984

COPPERSMITH

L(1/3)

1987

POMERANCE

L(1/2)NO COMPLEXITY
BEST KNOWN O(Q1/2)
L(1/2) IN LARGE CHAR.

...

...

2013

JOUX

2013

BARBULESCU, GAUDRY, JOUX, THOMEQUASI-POLY

2014

GRANGER, KLEINJUNG, ZUMBRAGELQUASI-POLY2019

THIS WORK (KLEINJUNG, W.)

QUASI-POLY

L(1/4)A RIGOROUS
ALGORITHM

Finely crafted and analysedby Pomerance in 1987

AN INDEX CALCULUS ALGORITHM‣×𝔽pn = 𝔽p[x]/(J), generator g ∊ 𝔽pn‣ Factor base 𝔉 = { f ∊ 𝔽p[x] | deg(f) ≤ B, monic, irred.} ∪ {g}‣ Index calculus:➡ Relation collection: collect relations of the form

∑ ef logg f = r (mod pn – 1)f∊𝔉

➡ Linear algebra: the relations form a linear system withunknowns logg f. Solve it, recover the values logg f➡ Individual logarithm: given h ∊ 𝔽pn, compute logg hINDEX CALCULUS FROM DESCENTh = ∏ f eff∊𝔉{‣×Descent: given h ∊ 𝔽pn find integers ef, for f in 𝔉, such thatdescent(h)➡ Relation collection: generate random r ∊ [1, pn – 1],r = logg(descent(gr)) = ∑ ef logg ff∊𝔉

➡ Individual logarithm: given h,logg h = logg(descent(h)) = ∑ ef logg ff∊𝔉

SUMMARYEFFICIENT DESCENT ALGORITHM

ISE
RE
HT:EC
POMERANOFTNECSED/2)
1(LYTIXCOMPLEEFFICIENT ALGORITHM FORCOMPUTING LOGARITHMS

AVEL
OS
NA
CSO ONE2)/1(LEMI
DLP IN T

A ZIGZAG
DESCENT

Descending one
step at a time

A HEURISTIC QUASI-POLYNOMIAL ALGORITHM
Theorem (Granger, Kleinjung, Zumbrägel): the DLP in fixedcharacteristic can be solved in expected quasi-poly. time in fields
that admit a suitable representation‣ Suitable representation? Field 𝔽q4[x]/(J) where J is anirreducible polynomial in 𝔽q4[x] such thatxq ≡ h0/h1 mod J
with h0 and h1 polynomials in 𝔽q4[x] of degree at most 2‣ Expected time qlog2(deg(J))

A DESCENT IS SUFFICIENT
A descent algorithm is suﬃcient‣ Fix the factor base 𝔉 = { linear polynomials in 𝔽q4[x] }‣ Descent: Given any polynomial Q in 𝔽q4[x] find integers ef, for fin 𝔉, such thatQ ≡ ∏ f ef mod J.
f∊𝔉‣ Main ingredient of the descent, degree 2 to 1 elimination:
given a degree 2 polynomial over an extension k of 𝔽q4, rewrite
it as a product of degree 1 polynomials over k

ZIGZAG DESCENTThe zigzag descent: transform the degree 2 to 1 elimination into afull descent algorithm
Deg re e 2 to 1 el im in ati on𝔽q4·2e – 1

12𝔽q4·2e – 2

1No r m2
22

Fac
qua tor is adrat ic s t io n i n
too ver𝔽q d2 e –12𝔽q8

12122𝔽q42e

ZIGZAG DESCENTThe zigzag descent: transform the degree 2 to 1 elimination into afull descent algorithm
Deg re e 2 to 1 el im in ati on𝔽q4·2e – 112𝔽q4·2e – 21No r m222Fac
qua tor is adrat ic s t io n i ntoo ver𝔽
q d2 e –12𝔽q8

122𝔽q412Q in 𝔽q4[x]of degree DD2eRewrite as
irreducibleof degree 2eSUMMARY
DEGREE 2 TO 1 ELIMINATIONDESCENT ALGORITHM

EFFICIENT ALGORITHM FORCOMPUTING LOGARITHMS

GKZ’S
DEGREE 2 TO 1ELIMINATIONA building blockPOLYNOMIALS WITH HIGHER SPLITTING PROBABILITY
Fix an extension k of 𝔽q4, and let Q an irred. quadratic in k[x]‣ Key idea (from [GGMZ13]): polynomials of the form

αxq + 1 + βxq + γx + δin k[x]have a high probability to split over k (around q–3)

‣ Let V be the vector space of dimension 4 of these polynomials,i.e., V = span(xq + 1, xq, x, 1) ⊂ k[x]Göloğlu, Granger, McGuire, and Zumbrägel. On the function field sieve and the impact of highersplitting probabilities. CRYPTO 2013.

SMOOTH RELATIONS‣ V = span(xq + 1, xq, x, 1) ⊂ k[x]‣ We have xq ≡ h0/h1 mod J, so
αxh0 + βh0 + γxh1 + δh1
αxq + 1 + βxq + γx + δ ≡mod Jh1

Sp lit s wi th high prob abilit ynumerat or of degree 3‣ Consider the vector subspace VQ of dimension 2 in V, where Q
divides the right-hand side:
VQ = {αxq + 1 + βxq + γx + δ | αxh0 + βh0 + γxh1 + δh1 ≡ 0 mod Q}

THE DEGREE 2 TO 1 ELIMINATION‣ For any f = αxq + 1 + βxq + γx + δ in VQ,
h1f ≡ αxh0 + βh0 + γxh1 + δh1 mod J‣ The quotient L0 = (αxh0 + βh0 + γxh1 + δh1)/Q is linear
h1f ≡ L0Q mod J‣ If f splits into linears L1,…,Lq + 1 in k[x], then–1
Q ≡ h1 L0 L1 … Lq + 1 mod J‣ Algorithm: choose random f ∊ VQ until it splits over k

SUMMARY
DEGREE 2 TO 1 ELIMINATIONEAVAHEWGNIM!
UDLSSEIAF,EETH
DON
ROFL
E
MODE
L
B
A
TI
SUDESCENT ALGORITHM

ALGORITHM FOR COMPUTINGDISCRETE LOGARITHMSELLIPTICCURVE MODEL

A convenient modelfor the finite field

HEURISTIC MODEL‣ Model 𝔽q4[x]/(J) used in heuristic algorithms‣ Good: the relation xq ≡ h0/h1, i.e., the Frobenius is congruent
to a small degree rational map‣ Bad: we cannot prove this model always exists‣ For our new rigorous algorithm: other model that always exists
and has a ‘small degree’ Frobenius?

FINITE FIELDS FROM ELLIPTIC CURVES‣ Construct a model for 𝔽qn where the q-Frobenius is congruent toa small degree rational map…

‣ Use elliptic curves!

FINITE FIELDS FROM ELLIPTIC CURVES‣ Construct a model for 𝔽qn where the q-Frobenius is congruent toa small degree rational map…

‣ Let E/𝔽q be an elliptic curve such that E(𝔽q) has a point Q oforder n‣ Let S ∊ E such that S (q) = S + Q. Then
S (qi) = S (qi – 1) + Q = S (qi – 2) + 2Q = … = S + iQ

‣ Q of order n implies (qn) is the first Frobenius fixing S‣ 𝔽qn = residue field of S over 𝔽q?

FINITE FIELDS FROM ELLIPTIC CURVES‣ 𝔽qn = residue field of S over 𝔽q?

‣ ‘Coordinate ring of E’ = 𝔽q[E] = 𝔽q[x,y] / (y2 – x3 – ax – b)
‣ ‘Residue field of S’ = 𝔽q[E]/∼ wheref ∼ g ⟺ f(S) = g(S)FROBENIUS AS A SMALL DEGREE MAP‣ Let φq : E → E : P ↦ P (q) be the q-Frobenius‣ For R ∊ E let τR : E → E : P ↦ P + R be the translation by R‣ For any f ∊ 𝔽q[E]/∼ = 𝔽qn, we havef ∘ φq ∼ f ∘ τQ"Qybniotlasnart=siun"Fro b eq ≡ h0/h1 m o d J "x"is th e ne w
f ∘ φq(S) = f (S(q)) = f (S+Q) = f ∘ τQ(S)PROVABLE MODEL‣ We want to solve DLP in 𝔽qn: find E/𝔽q with a point of order n‣ Theorem (Waterhouse, 1969): For any integer t coprime to q
such that |t| ≤ 2q1/2, there is an ordinary elliptic curve E/𝔽q
such that |E(𝔽q)| = q + 1 − t.

‣ If n2 ≤ 2q1/2, there exists E/𝔽q that contains a point of order n‣ To solve DLP in 𝔽pn, solve it in a small extension 𝔽qn such thatn2 ≤ 2q1/2

NEWELIMINATIONS

Eliminations in the elliptic
curve modelDEGREESFix an extension k of 𝔽q‣ k(E) = k(x,y) / (y2 – x3 – ax – b)
‣ ‘Degree of f ∊ k(E)’ = number of solutions of f(P) = 0, P ∊ E‣ x ∊ k(E) has degree 2t wo po int s (0, y) wi th y2 = b

SPLITTING POLYNOMIALSFix an extension k of 𝔽q‣ V = span(xq + 1, xq, x, 1) ⊂ k(E)‣ Random f ∊ V splits with high probability into ‘linear factors’
L1,…,Lq + 1 defined over k‣ Each Li is of the form x – a, they are of degree 2…
‣ No ‘degree 2 to 1’ elimination… Can we do ‘3 to 2’ ?
‣ Let D in k(E) of degree 3

A FIRST ATTEMPT…
‣ Let
Y = {αxq+1 + βxq + γx + δ | α(x∘τQ)x + β(x∘τQ) + γx + δ ≡ 0 mod D} ⊂ ℙ(V)‣ For any f ∊ Y(k),War ning: ha nd-wav yg = (α(x∘τQ)x + β(x∘τQ) + γx + δ)/Dhas degree 4 – 3 = 1‣ Suppose f = L1 … Lq+1 where each Li is linear in k[x] (so Li hasdegree 2 in k(E))
de gree s 1 an d 2
D ≡ L1 … Lq+1 g –1

‣ Algorithm: choose random f ∊ Y(k) until f splits over k
De gree 3 to de gree 2 eli mi natio n??

A FIRST ATTEMPT…
Y = {αxq+1 + βxq + γx + δ | α(x∘τQ)x + β(x∘τQ) + γx + δ ≡ 0 mod D} ⊂ ℙ(V)‣ Y = ℙ(ker(V → ‘k(E)/D’))‣ V has dimension 4, ‘k(E)/D’ has dimension deg(D) = 3, thekernel is expected to have dimension 1: Y is a single point‣ Bad: Y is too small, we need a curve…

AN EXTRA DEGREE OF FREEDOMFix an extension k of 𝔽q, and let D in k(E) of degree 3‣ V = span(xq + 1, xq, x, 1) ⊂ k(E)‣ For any P ∊ E let
ψP : V → k(E) :{1↦1x↦ x ∘ τPxq
↦ x ∘ τQ+P(q)xq + 1 ↦ (x ∘ τP)(x ∘ τQ+P(q))‣ For any f ∊ V, f ∘ τP ≡ ψP(f)De gree 4
Sp lit s wi th high prob abilit y int o de gree 2’s

DEGREE 3 TO DEGREE 2 ELIMINATION
X = {(f,P) | ψP(f) ≡ 0 mod D} ⊂ ℙ(V) × EWar ning: ha nd-wav y‣ For any (f, P) ∊ X(k), g = ψP(f)/D has degree 4 – 3 = 1‣ Suppose f = L1 … Lq+1 where each Li is linear in k[x]D = ψP(f) g –1 ≡ (L1 ∘ τP) … (Lq+1 ∘ τP) g –1de gree s 1 an d 2‣ Algorithm: choose random (f, P) ∊ X(k) until f splits over k
De gree 3 to de gree 2 eli mi natio nICTSIRU
DEGREE 2 TO 1 ELIMINATIONHEZIG-ZAGDESCENTDESCENT ALGORITHM

ALGORITHM FOR COMPUTINGDISCRETE LOGARITHMS

SUO
R DEGREE 3 TO 2 ELIMINATIONOGRI

ZIG-ZAGDESCENTDESCENT ALGORITHM

ALGORITHM FOR COMPUTINGDISCRETE LOGARITHMS

RIGOROUS DEGREE 4 TO 3 ELIMINATION +DEGREE 3 TO 2 ELIMINATIONSUORRIGO

DEGREE 4 TO 2 ELIMINATIONZIG-ZAGDESCENTDESCENT ALGORITHM

ALGORITHM FOR COMPUTINGDISCRETE LOGARITHMSS!
UORORIGPROOFSTRATEGY
Irreducible covers

WHAT REMAINS TO BE PROVED?

‣ Algorithm: choose random (f, P) ∊ X(k) until f splits over k‣ For how many (f,P) ∊ X(k) does f split over k?

IRREDUCIBLE CURVESA CURVE IS IRREDUCIBLE IF IT IS NOT A UNION OF TWO SUB-CURVES

C1C2C1 AND C2 ARE BOTH IRREDUCIBLE

IRREDUCIBLE CURVESA CURVE IS IRREDUCIBLE IF IT IS NOT A UNION OF TWO SUB-CURVES

C1 U C2C1 AND C2 ARE BOTH IRREDUCIBLE
C1 U C2 IS NOT IRREDUCIBLE

IRREDUCIBLE CURVESA CURVE IS IRREDUCIBLE IF IT IS NOT A UNION OF TWO SUB-CURVES

C1 U C2A CURVE IS ABSOLUTELY IRREDUCIBLE IF IT IS IRREDUCIBLE OVER
THE ALGEBRAIC CLOSURE OF THE FIELD OF DEFINITIONCURVES AND MORPHISMS‣ A morphism of curves is a map C → D described bypolynomials in the coordinates‣ A morphism between absolutely irreducible curves is either
constant or surjective over the algebraic closure

PROOF STRATEGY
For how many (f,P) ∊ X(k) does f split over k?

‣ Construct a curve C defined over k, and a surjective morphism
θ : C → X such that
➡ For any point z in C(k), the polynomial in θ(z) splits over k➡ C is absolutely irreducible

Has se-Weil bou nds:
abso lute ly irre duci ble curves
have a lot of rati ona l poin ts‣ By the absolute irreducibility, C(k) has a lot of points, therefore
a lot of polynomials in X(k) split over k
Method from: Kleinjung, Wesolowski. A new perspective on the powers of two descent for discrete
logarithms in finite fields. ANTS–XIII, 2018.

OPENQUESTIONSA DETERMINISTIC ALGORITHM?
?
MHTIROGLAEMITLA
IM
ONYLA POIS SMALL-CHAR-DLP IN P?
?
ICTIS
RETCA
RA
HCE
GRAL
DNA
MEDIUM

DISCRETE LOGARITHMS

IN QUASI-POLYNOMIAL TIME

IN FINITE FIELDS OF SMALL CHARACTERISTIC

Benjamin Wesolowski

ECC 2019: 23rd Workshop on
Elliptic Curve Cryptography
December 2019
Bochum, Germany

Based on a joint work withThorsten Kleinjung