Ideal-SVP is hard forsmall-norm uniform prime idealsJoël Felderhoff, Alice Pellet-Mary, Damien Stehlé, Benjamin Wesolowski

Benjamin Wesolowski, CNRS and ENS de Lyon — TCC 2023, December 2, 2023, Taipei, Taiwan

Ideal-SVP• Any basis (b1, …, bn) of a vector space describes a lattice L = ℤb1 + … + ℤbn
Basis

Origin2

Ideal-SVP• Any basis (b1, …, bn) of a vector space describes a lattice L = ℤb1 + … + ℤbn
Basis

Origin2

Ideal-SVP• Any basis (b1, …, bn) of a vector space describes a lattice L = ℤb1 + … + ℤbn• SVP: ind the non-zero point in L closest to the origin (up to approx. factor…)
BasisShortest vector
Originf2

• Some lattices have "something extra"...
• K = ℚ[X] / (Xn + 1) is a ield, and a ℚ-vector space of dimension n = 2r
• = ℤ[X] / (Xn + 1) is a lattice in K… and a subring!
• An ideal lattice is a lattice ⊂ K such that ⊂𝔞𝔞𝓞𝔞3

f

𝓞

Ideal-SVP• Some lattices have "something extra"...
• K = ℚ[X] / (Xn + 1) is a ield, and a ℚ-vector space of dimension n = 2r
• = ℤ[X] / (Xn + 1) is a lattice in K… and a subring!
• An ideal lattice is a lattice ⊂ K such that ⊂• An ideal lattice is integral if ⊂𝔞𝔞𝓞𝓞𝔞𝔞3

f

𝓞

Ideal-SVP• Some lattices have "something extra"...
• K = ℚ[X] / (Xn + 1) is a ield, and a ℚ-vector space of dimension n = 2r
• = ℤ[X] / (Xn + 1) is a lattice in K… and a subring!
• An ideal lattice is a lattice ⊂ K such that ⊂• An ideal lattice is integral if ⊂• An integral ideal is prime if it is not a product of other integral ideals

𝔞𝔞𝓞𝓞𝔞𝔞3f

𝓞Ideal-SVP• Some lattices have "something extra"...
• K = ℚ[X] / (Xn + 1) is a ield, and a ℚ-vector space of dimension n = 2r
• = ℤ[X] / (Xn + 1) is a lattice in K… and a subring!
• An ideal lattice is a lattice ⊂ K such that ⊂• An ideal lattice is integral if ⊂• An integral ideal is prime if it is not a product of other integral ideals• Any ideal lattice is of the form = ∏ ie where i ⊂ is prime and ei ∈ ℤi𝓞𝔞𝖕𝔞𝓞𝖕

𝓞𝔞𝔞𝔞

3

f𝓞

Ideal-SVP

Ideal-SVP• Ideal lattices are important:• Led to the irst fully homomorphic encryption scheme [Gentry09]• Simplest case of module lattices, used in real world (KYBER, DILITHIUM)

f4

Ideal-SVP• Ideal lattices are important:• Led to the irst fully homomorphic encryption scheme [Gentry09]• Simplest case of module lattices, used in real world (KYBER, DILITHIUM)• Ideal lattices are special: is SVP as hard?
• There are speci ic algorithms for SVP in ideal lattices• Ideal-SVP still considered hard, but one can reach better approximation
factors than SVP in generic lattices

ff

4

Average-case Ideal-SVP

Is Ideal-SVP hard on average?

5

Average-case Ideal-SVP

Is Ideal-SVP hard on average?
• We want random self-reducibility: if Ideal-SVP can be solved for random
instances, then Ideal-SVP can be solved for any instance…

5

Average-case Ideal-SVP

Is Ideal-SVP hard on average?
Fo r w h at dist r i butio n?

• We want random self-reducibility: if Ideal-SVP can be solved for randominstances, then Ideal-SVP can be solved for any instance…

5

Average-case Ideal-SVP• Previous work, random self-reducibility for two distributions:6Average-case Ideal-SVP• Previous work, random self-reducibility for two distributions: P -1-Idea l-SV P• [Gentry09] Inverse of uniformly random prime ideal of small norm
• Non-integral… works for [Gentry09]’s purpose

6

Average-case Ideal-SVP• Previous work, random self-reducibility for two distributions: P -1-Idea l-SV P• [Gentry09] Inverse of uniformly random prime ideal of small norm
• Non-integral… works for [Gentry09]’s purpose• [BDPW20] Uniform ideals for the Haar measure of large norm
Ha a rGeometrically canonical, rich theory! but large norms…
•Ide a lSV P

6Average-case Ideal-SVP• Previous work, random self-reducibility for two distributions: P -1-Idea l-SV P• [Gentry09] Inverse of uniformly random prime ideal of small norm
• Non-integral… works for [Gentry09]’s purpose• [BDPW20] Uniform ideals for the Haar measure of large norm
Ha a rGeometrically canonical, rich theory! but large norms…
•Ide a lSV P
P-Ide a l-SV
• This work: uniformly random prime ideal of small norm
P
• Integral, unlike [Gentry09], and small, unlike [BDPW20]• Composes with NTRU reductions! Links NTRU to worst-case Ideal-SVP6

MethodWo rst-c ase
Ide al-SV P[Gentry09]≤New
1
P -Ideal-SVP

7≤

P-Ideal-SVP

MethodWo rst-c ase
Ide al-SV P[Gentry09]≤New
1
P -Ideal-SVP

pol y-t ime given afactor ing ora cle
7≤

P-Ideal-SVP

P -Ideal-SVP reduces to P-Ideal-SVP-1• Input: an ideal = −1 with• Output: x ∈ small

uniform prime of bounded norm

𝖕𝖕𝔞𝔞8

• Input: an ideal = −1 with• Output: x ∈ small
1. Let s ∈uniform prime of bounded normsmall (solve P-Ideal-SVP for , uniform prime of bounded norm);

2. Let ( , y) ← SampleIdeal( , s )is a uniform integral ideal of bounded norm, and y ∈ (➡
3. Ifsmall (solve P-Ideal-SVP for , uniform prime of bounded norm);

5. Return s ·y ∈ ·()−1 =−1𝖕𝔟𝖕𝔟𝖕𝖕𝖕𝖕𝖕𝔟𝔞𝔟𝔞𝖕𝔟8𝔟)−1 is small

is not prime, abort;

4. Let s ∈𝔟𝔟

P -Ideal-SVP reduces to P-Ideal-SVP-1

• Input: an ideal = −1 with• Output: x ∈ small
1. Let s ∈uniform prime of bounded normsmall (solve P-Ideal-SVP for , uniform prime of bounded norm);

2. Let ( , y) ← SampleIdeal( , s )3. IfNe e d f ac t o r ing o rac leis a uniform integral ideal of bounded norm, and y ∈ (➡

small (solve P-Ideal-SVP for , uniform prime of bounded norm);

5. Return s ·y ∈ ·()−1 =−1𝖕𝔟𝖕𝔟𝖕𝖕𝖕𝖕𝖕𝔟𝔞𝔟𝔞𝖕𝔟8𝔟)−1 is small

is not prime, abort;

4. Let s ∈𝔟𝔟

P -Ideal-SVP reduces to P-Ideal-SVP-1

• Input: an ideal = −1 with• Output: x ∈ small
1. Let s ∈uniform prime of bounded normsmall (solve P-Ideal-SVP for , uniform prime of bounded norm);

2. Let ( , y) ← SampleIdeal( , s )Ne e d f ac t o r ing o rac leis a uniform integral ideal of bounded norm, and y ∈ (➡

4. Let s ∈small (solve P-Ideal-SVP for , uniform prime of bounded norm);

5. Return s ·y ∈ ·()−1 =−1𝖕𝔟𝖕𝔟𝖕𝖕𝖕𝖕𝖕𝔟𝔞𝔟𝔞𝖕𝔟8𝔟)−1 is small

is not prime, abort; s u c c e s s p r o b a = de n s it y o f p r ime s

3. If𝔟𝔟

P -Ideal-SVP reduces to P-Ideal-SVP-1

• Input: an ideal = −1 with• Output: x ∈ small
1. Let s ∈uniform prime of bounded norm

small (solve P-Ideal-SVP for , uniform prime of bounded norm);

2. Let ( , y) ← SampleIdeal( , s )Ne e d f ac t o r ing o rac leis a uniform integral ideal of bounded norm, and y ∈ (➡

4. Let s ∈small (solve P-Ideal-SVP for , uniform prime of bounded norm);

5. Return s ·y ∈ ·()−1 =−1s sm a ll a n d y sm a ll s o s y sm a ll𝖕𝔟𝖕𝔟∙𝖕𝖕𝖕𝖕𝖕𝔟𝔞𝔟𝔞𝖕𝔟8𝔟)−1 is small

is not prime, abort; s u c c e s s p r o b a = de n s it y o f p r ime s

3. If𝔟𝔟

P -Ideal-SVP reduces to P-Ideal-SVP-1

Application to NTRU
• [PS21] gives a Karp reduction from Ideal-SVP to NTRU [HPS96]

9

Application to NTRU
• [PS21] gives a Karp reduction from Ideal-SVP to NTRU [HPS96]• New NTRU distribution DNTRU: sample uniform small prime , and create NTRU
instance (and trapdoor) via the [PS21] reduction𝖕9

Application to NTRU
• [PS21] gives a Karp reduction from Ideal-SVP to NTRU [HPS96]• New NTRU distribution DNTRU: sample uniform small prime , and create NTRU
instance (and trapdoor) via the [PS21] reduction[PS21]≥≥

P-Ideal-SVP

9𝖕NTR
NT RU for D U

NewWorst-case
Ideal-SVP

Application to NTRU
• [PS21] gives a Karp reduction from Ideal-SVP to NTRU [HPS96]• New NTRU distribution DNTRU: sample uniform small prime , and create NTRU
instance (and trapdoor) via the [PS21] reduction[PS21]NTR
NT RU for D U

≥

New≥

P-Ideal-SVP

Worst-case
Ideal-SVP• First distribution over NTRU instances with a polynomial modulus whosehardness is supported by a worst-case lattice problem• Caveat: sampling DNTRU needs factoring oracle𝖕9