CryptoBook
  • CryptoBook
  • Book Plan
  • Style Guide
    • Sample Page
  • Contributors
  • Fundamentals
    • Mathematical Notation
    • Division and Greatest common divisor
      • Euclidean Algorithm
    • Modular Arithmetic
      • Theorems of Wilson, Euler, and Fermat
        • Fermat's Little Theorem in Detail
        • Euler's Theorem in Detail
      • Quadratic Residues
    • Continued Fractions
  • Number Theory
  • Ideals
  • Polynomials With Shared Roots
  • Integer Factorization
    • Pollard rho
    • Sieves
  • Abstract algebra
    • Groups
      • Another take on groups
      • Discrete Log Problem
    • Rings
    • Fields
    • Polynomials
  • Elliptic Curves
    • Untitled
  • Lattices
    • Introduction
    • LLL reduction
      • Gram-Schmidt Orthogonalization
      • Lagrange's algorithm
      • LLL reduction
    • Lattice reduction
      • Minkowski reduced
      • HKZ reduced
      • LLL reduced
    • Applications
      • Coppersmith algorithm
      • Extensions of Coppersmith algorithm
    • Hard lattice problems
    • Lattices of interest
    • Cryptographic lattice problems
      • Short integer solutions (SIS)
      • Learning with errors (LWE)
      • Ring-LWE
      • NTRU
    • Interactive fun
    • Resources and notations
  • Asymmetric Cryptography
  • RSA
    • Proof of correctness
    • RSA application
    • Low Private Component Attacks
      • Wiener's Attack
      • Boneh-Durfee Attack
    • Common Modulus Attack
    • Recovering the Modulus
  • Diffie-Hellman
    • MITM
  • Elliptic Curve Cryptography
  • Symmetric Cryptography
    • Encryption
    • The One Time Pad
    • AES
      • Rijndael Finite Field
      • Round Transformations
  • Hashes
    • Introduction / overview
    • The Birthday paradox / attack
  • Isogeny Based Cryptography
    • Introduction to Isogeny Cryptography
    • Isogenies
    • Isogeny and Ramanujan Graphs
  • Appendices
    • Sets and Functions
    • Probability Theory
Powered by GitBook
On this page
  • Polynomials in lattices
  • Achieving the bound
  • Exercises

Was this helpful?

Export as PDF
  1. Lattices
  2. Applications

Coppersmith algorithm

This algorithm solves for small roots of polynomials modulo any integer, meaning given some polynomial f(x)∈Z[x]f(x)\in\mathbb Z[x]f(x)∈Z[x]of degree dddand any integer NNN, then if f(x0)=0(modN),∣x0∣<N1df(x_0)=0\pmod{N},|x_0|<N^{\frac1d}f(x0​)=0(modN),∣x0​∣<Nd1​, this algorithm can findx0x_0x0​with time polynomial in log⁡N\log NlogNand ddd. The key idea behind this algorithm is to construct a polynomialg(x)g(x)g(x)such that g(x0)=0g(x_0)=0g(x0​)=0in R\mathbb RR. As roots of polynomials over the reals can be found easily, this gives an easy way to find x0x_0x0​. We shall introduce the Coppersmith algorithm in a few iterations, with each iteration approaching the N1dN^{\frac1d}Nd1​bound.

Polynomials in lattices

We first consider a criteria for a root of a polynomial moduloNNNto exists over the reals as well. Supposef(x)=∑i=0dfixif(x)=\sum_{i=0}^df_ix^if(x)=∑i=0d​fi​xiis a polynomial of degreeddd. Define the ℓ2\ell_2ℓ2​norm∥f(x)∥2\left\lVert f(x)\right\rVert_2∥f(x)∥2​ of a polynomial to be ∑i=0dfi2\sqrt{\sum_{i=0}^df_i^2}∑i=0d​fi2​​. Given ∣x0∣<B,f(x0)=0(modN)|x_0|<B,f(x_0)=0\pmod N∣x0​∣<B,f(x0​)=0(modN), if

∥f(Bx)∥2=∑i=0d(fiBi)2≤Nd+1\left\lVert f(Bx)\right\rVert_2=\sqrt{\sum_{i=0}^d\left(f_iB^i\right)^2}\leq\frac N{\sqrt{d+1}}∥f(Bx)∥2​=i=0∑d​(fi​Bi)2​≤d+1​N​

then f(x0)=0f(x_0)=0f(x0​)=0 in R\mathbb RR. The proof is a relatively straightforward chain of inequalities:

Nd+1≥∑i=0d(fiBi)2≥∑i=0d(fix0i)2≥1d+1∑i=0d∣fix0i∣≥1d+1∣∑i=0dfix0i∣\begin{align*} \frac N{\sqrt{d+1}}&\geq\sqrt{\sum_{i=0}^d\left(f_iB^i\right)^2}\\&\geq\sqrt{\sum_{i=0}^d\left(f_ix_0^i\right)^2}\\ &\geq\frac1{\sqrt{d+1}}\sum_{i=0}^d\left|f_ix_0^i\right|\\ &\geq\frac1{\sqrt{d+1}}\left|\sum_{i=0}^df_ix_0^i\right|\\ \end{align*}d+1​N​​≥i=0∑d​(fi​Bi)2​≥i=0∑d​(fi​x0i​)2​≥d+1​1​i=0∑d​​fi​x0i​​≥d+1​1​​i=0∑d​fi​x0i​​​

and since f(x0)=0(modN)f(x_0)=0\pmod Nf(x0​)=0(modN)implies f(x0)=kNf(x_0)=kNf(x0​)=kNfor some k∈Zk\in\mathbb Zk∈Z, we know that kkkmust be000to satisfy the inequality above.

With this, if we can find some polynomials fif_ifi​such that fi(x0)=0(modN)f_i(x_0)=0\pmod Nfi​(x0​)=0(modN), then if we can find some cic_ici​such that ∥∑icifi(x)∥2≤Nd+1\left\lVert\sum_ic_if_i(x)\right\rVert_2\leq\frac N{\sqrt{d+1}}∥∑i​ci​fi​(x)∥2​≤d+1​N​, then we can find x0x_0x0​easily. This gives a brief idea as to why lattices would be useful in such a problem.

To use lattices, notice that we can encode the polynomial f(x)=∑i=0dfixif(x)=\sum_{i=0}^df_ix^if(x)=∑i=0d​fi​xias the vector with components fif_ifi​. In this way, adding polynomials and multiplying polynomials by numbers still makes sense. Lets suppose that f(x0)=0(modN),x0<Bf(x_0)=0\pmod N,x_0<Bf(x0​)=0(modN),x0​<Band fd=1f_d=1fd​=1(otherwise multiplyfffby fd−1(modN)f_d^{-1}\pmod Nfd−1​(modN). Consider the polynomials gi(x)=Nxig_i(x)=Nx^igi​(x)=Nxiand consider the latticeLLLgenerated by f(Bx)f(Bx)f(Bx)and gi(Bx)g_i(Bx)gi​(Bx), 0≤i≤d−10\leq i\leq d-10≤i≤d−1. As a matrix, the basis vectors are

B=(N00…000NB0…0000NB2…00⋮⋮⋮⋱⋮⋮000…NBd−10f0f1Bf2B2…fd−1Bd−1Bd)\mathcal B=\begin{pmatrix} N&0&0&\dots&0&0\\ 0&NB&0&\dots&0&0\\ 0&0&NB^2&\dots&0&0\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&0&\dots&NB^{d-1}&0\\ f_0&f_1B&f_2B^2&\dots&f_{d-1}B^{d-1}&B^d\\ \end{pmatrix} B=​N00⋮0f0​​0NB0⋮0f1​B​00NB2⋮0f2​B2​………⋱……​000⋮NBd−1fd−1​Bd−1​000⋮0Bd​​

As every element in this lattice is some polynomial g(Bx)g(Bx)g(Bx), if f(x0)=0(modN)f(x_0)=0\pmod Nf(x0​)=0(modN), theng(x0)=0(modN)g(x_0)=0\pmod Ng(x0​)=0(modN). Furthermore, if ∣x0∣<B|x_0|<B∣x0​∣<Band a short vectorv(Bx)v(Bx)v(Bx)has length less than Nd+1\frac N{\sqrt{d+1}}d+1​N​, then we have v(x0)=0v(x_0)=0v(x0​)=0in R\mathbb RR.

The volume of this lattice is NdBd(d+1)2N^dB^{\frac{d(d+1)}2}NdB2d(d+1)​and the lattice has dimension d+1d+1d+1. By using the LLL algorithm, we can find a vector v(Bx)v(Bx)v(Bx) with length at most

∥v(Bx)∥2=(44δ−1)d4⏟cδ,dvol(L)1d+1=cδ,dNdd+1Bd2\left\lVert v(Bx)\right\rVert_2=\underbrace{\left(\frac4{4\delta-1}\right)^{\frac d4}}_{c_{\delta,d}}\text{vol}(L)^\frac1{d+1}=c_{\delta,d}N^{\frac d{d+1}}B^{\frac d2}∥v(Bx)∥2​=cδ,d​(4δ−14​)4d​​​vol(L)d+11​=cδ,d​Nd+1d​B2d​

As long as cδ,dNdd+1Bd2<Nd+1c_{\delta,d}N^{\frac d{d+1}}B^{\frac d2}<\frac N{\sqrt{d+1}}cδ,d​Nd+1d​B2d​<d+1​N​, then by the above criteria we know that this vector has x0x_0x0​has a root over R\mathbb RR. This tells us that

B<N2d(d+1)(cδ,dd+1)−2dB<N^{\frac2{d(d+1)}}\left(c_{\delta,d}\sqrt{d+1}\right)^{-\frac 2d}B<Nd(d+1)2​(cδ,d​d+1​)−d2​

While this isn't the N1dN^{\frac1d}Nd1​bound that we want, this gives us an idea of what we can do to achieve this bound, i.e. add more vectors such that the length of the shortest vector decreases.

Achieving the N1dN^{\frac1d}Nd1​bound

One important observation to make is that any coefficients in front ofNxN^xNxdoes not matter as we can simply brute force the top bits of our small root in O(1)O(1)O(1)time. Hence we only need to getB=kN1dB=kN^{\frac1d}B=kNd1​for some fixed constantkkk.

In order to achieve this, notice that if f(x0)=0(modN)f(x_0)=0\pmod Nf(x0​)=0(modN), then f(x0)h=0(modNh)f(x_0)^h=0\pmod{N^h}f(x0​)h=0(modNh). This loosens the inequality required for a polynomial to have x0x_0x0​as a small root as our modulus is now larger. With this in mind, consider the polynomials

gi,j(x)=Nh−jf(x)jxi0≤i<d,0≤j<hg_{i,j}(x)=N^{h-j}f(x)^jx^i\quad0\leq i<d,0\leq j<hgi,j​(x)=Nh−jf(x)jxi0≤i<d,0≤j<h

where we will determinehhhlater. Here gi,j(x0)=0(modNh)g_{i,j}(x_0)=0\pmod{N^h}gi,j​(x0​)=0(modNh), hence we shall consider the lattice LLL generated by gi,j(Bx)g_{i,j}(Bx)gi,j​(Bx). As an example, if we have

f(x)=x3+2x2+3x+4h=3f(x)=x^3+2x^2+3x+4\quad h=3f(x)=x3+2x2+3x+4h=3

the basis vectors of our lattice would look like

(N3000000000BN3000000000B2N30000004N23BN22B2N2B3N20000004BN23B2N22B3N2B4N20000004B2N23B3N22B4N2B5N200016N24BN25B2N20B3N10B4N4B5NB6N00016BN24B2N25B3N20B4N10B5N4B6NB7N00016B2N24B3N25B4N20B5N10B6N4B7NB8N)\footnotesize{\left(\begin{array}{rrrrrrrrr} N^{3} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & B N^{3} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & B^{2} N^{3} & 0 & 0 & 0 & 0 & 0 & 0 \\ 4 \, N^{2} & 3 \, B N^{2} & 2 \, B^{2} N^{2} & B^{3} N^{2} & 0 & 0 & 0 & 0 & 0 \\ 0 & 4 \, B N^{2} & 3 \, B^{2} N^{2} & 2 \, B^{3} N^{2} & B^{4} N^{2} & 0 & 0 & 0 & 0 \\ 0 & 0 & 4 \, B^{2} N^{2} & 3 \, B^{3} N^{2} & 2 \, B^{4} N^{2} & B^{5} N^{2} & 0 & 0 & 0 \\ 16 \, N & 24 \, B N & 25 \, B^{2} N & 20 \, B^{3} N & 10 \, B^{4} N & 4 \, B^{5} N & B^{6} N & 0 & 0 \\ 0 & 16 \, B N & 24 \, B^{2} N & 25 \, B^{3} N & 20 \, B^{4} N & 10 \, B^{5} N & 4 \, B^{6} N & B^{7} N & 0 \\ 0 & 0 & 16 \, B^{2} N & 24 \, B^{3} N & 25 \, B^{4} N & 20 \, B^{5} N & 10 \, B^{6} N & 4 \, B^{7} N & B^{8} N \end{array}\right)}​N3004N20016N00​0BN303BN24BN2024BN16BN0​00B2N32B2N23B2N24B2N225B2N24B2N16B2N​000B3N22B3N23B3N220B3N25B3N24B3N​0000B4N22B4N210B4N20B4N25B4N​00000B5N24B5N10B5N20B5N​000000B6N4B6N10B6N​0000000B7N4B7N​00000000B8N​​

We have the following immediate computations of LLL:

dim⁡(L)=dhvol(L)=Ndh(h+1)2B(dh−1)dh2\dim(L)=dh\quad\text{vol}(L)=N^{\frac{dh(h+1)}2}B^{\frac{(dh-1)dh}2}dim(L)=dhvol(L)=N2dh(h+1)​B2(dh−1)dh​

hence when using the LLL algorithm, the shortest LLL basis vectorv(Bx)v(Bx)v(Bx)has length

∥v(Bx)∥2=(44δ−1)dim⁡(L)−14vol(L)1dim⁡(L)=(44δ−1)dh−14Nh+12Bdh−12\begin{align*} \left\lVert v(Bx)\right\rVert_2&=\left(\frac4{4\delta-1}\right)^{\frac{\dim(L)-1}4}\text{vol}(L)^{\frac1{\dim(L)}}\\ &=\left(\frac4{4\delta-1}\right)^{\frac{dh-1}4}N^{\frac{h+1}2}B^{\frac{dh-1}2}\\ \end{align*}∥v(Bx)∥2​​=(4δ−14​)4dim(L)−1​vol(L)dim(L)1​=(4δ−14​)4dh−1​N2h+1​B2dh−1​​

and we need ∥v(Bx)∥2<Nhdh\left\lVert v(Bx)\right\rVert_2<\frac{N^h}{\sqrt{dh}}∥v(Bx)∥2​<dh​Nh​for v(x0)=0v(x_0)=0v(x0​)=0. Hence we have

B<4δ−14(1dh)1dh−1Nh−1dh−1B<\sqrt{\frac{4\delta-1}4}\left(\frac1{dh}\right)^{\frac1{dh-1}}N^{\frac{h-1}{dh-1}}B<44δ−1​​(dh1​)dh−11​Ndh−1h−1​

Since lim⁡h→∞h−1dh−1=1d\lim_{h\to\infty}\frac{h-1}{dh-1}=\frac1dlimh→∞​dh−1h−1​=d1​, this will achieve the N1dN^{\frac1d}Nd1​bound that we want. However as for big hhh, the LLL algorithm would take a very long time, we typically choose a suitably largehhhsuch that the algorithm is still polynomial in log⁡N,d\log N,dlogN,dand brute force the remaining bits.

Exercises

1) We often see h=⌈max⁡(d+dε−1d2ϵ,7d)⌉h=\left\lceil\max\left(\frac{d+d\varepsilon-1}{d^2\epsilon},\frac7d\right)\right\rceilh=⌈max(d2ϵd+dε−1​,d7​)⌉in literature. We shall now show where this mysterious7d\frac7dd7​comes from. The other term will appear in the next exercise. Typically, one sets δ=34\delta=\frac34δ=43​to simplify calculations involving the LLL algorithm as 44δ−1=2\frac4{4\delta-1}=24δ−14​=2. Suppose we want B>12Nh−1dh−1B>\frac12N^{\frac{h-1}{dh-1}}B>21​Ndh−1h−1​, show that this gives us dh≥7dh\geq7dh≥7.

2) We show that we can indeed find small roots less thanN1dN^{\frac1d}Nd1​in polynomial time. In the worse case, the longest basis vector cannot exceed O(Bdh−1Nh)O\left(B^{dh-1}N^h\right)O(Bdh−1Nh). Hence the LLL algorithm will run in at mostO(d6h6(d+h)2log⁡2N)O(d^6h^6(d+h)^2\log^2N)O(d6h6(d+h)2log2N)time.

Let

ε=1d−h−1dh−1h=d+dε−1d2ϵ≈1dε\varepsilon=\frac1d-\frac{h-1}{dh-1}\quad h=\frac{d+d\varepsilon-1}{d^2\epsilon}\approx\frac1{d\varepsilon}ε=d1​−dh−1h−1​h=d2ϵd+dε−1​≈dε1​

and choose ε=1log⁡N\varepsilon=\frac1{\log N}ε=logN1​, then NεN^\varepsilonNεis a constant hence the number of bits needed to be brute forced is a constant. This gives us the approximate run time of O((d+1dlog⁡N)2log⁡8N)O((d+\frac1d\log N)^2\log^8N)O((d+d1​logN)2log8N).

3) We shall show that this is the best bound we can hope for using lattice methods. Suppose there exists some algorithm that finds roots less than O(N1d+ϵ)O\left(N^{\frac1d+\epsilon}\right)O(Nd1​+ϵ)in polynomial time. Then consider the case whenN=p2N=p^2N=p2and f(x)=x2+pxf(x)=x^2+pxf(x)=x2+px. Show that this forces the lattice to have a size too big for the algorithm to run in polynomial time, assuming the algorithm finds all small roots.

PreviousApplicationsNextExtensions of Coppersmith algorithm

Last updated 4 years ago

Was this helpful?