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
  • Unknown modulus
  • Exercises

Was this helpful?

Export as PDF
  1. Lattices
  2. Applications

Extensions of Coppersmith algorithm

PreviousCoppersmith algorithmNextHard lattice problems

Last updated 4 years ago

Was this helpful?

The Coppersmith algorithm can be made even more general. There are two main extensions, first to an unknown modulus, then to multivariate polynomials.

Unknown modulus

This extension of Coppersmith allows one to find small roots modulo an unknown some unknown factor of a number. More specifically, suppose that we have some unknown factorbbbofNNNsuch that b<Nβb<N^\betab<Nβand some monic polynomialfffof degreedddsuch that f(x0)=0(modb)f(x_0)=0\pmod bf(x0​)=0(modb)for some x0<Nβ2dx_0<N^{\frac{\beta^2}d}x0​<Ndβ2​. Then we can findx0x_0x0​in time polynomial in log⁡N,d\log N,dlogN,d.

One key reason why this is possible is because we dont need to explicitly know the modulus to determine if a small root exists, i.e. ∥f(Bx)∥2≤bd+1≤Nβd+1\left\lVert f(Bx)\right\rVert_2\leq\frac b{\sqrt{d+1}}\leq\frac{N^{\beta}}{\sqrt{d+1}}∥f(Bx)∥2​≤d+1​b​≤d+1​Nβ​is sufficient for a root less thanBBBto exist. The algorithm here is extremely similar to the Coppersmith algorithm, except we add more polynomials into the lattice. The polynomials that we will use are

gi,j(x)=Nh−jf(x)jxi0≤i<d,0≤j<hgi,h(x)=f(x)hxi0≤i<t\begin{align*} g_{i,j}(x)&=N^{h-j}f(x)^jx^i&0\leq i<d,0\leq j<h\\ g_{i,h}(x)&=f(x)^hx^i&0\leq i<t \end{align*}gi,j​(x)gi,h​(x)​=Nh−jf(x)jxi=f(x)hxi​0≤i<d,0≤j<h0≤i<t​

The latticeLLLgenerated by these polynomials would have

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

As we require the shortest vector to have length at most Nβhn\frac{N^{\beta h}}{\sqrt{n}}n​Nβh​, repeating the computations from the previous section, we obtain

B<4δ−14(1n)1n−1N2βhn−1−dh(h+1)n(n−1)B<\sqrt{\frac{4\delta-1}4}\left(\frac1n\right)^{\frac1{n-1}}N^{\frac{2\beta h}{n-1}-\frac{dh(h+1)}{n(n-1)}}B<44δ−1​​(n1​)n−11​Nn−12βh​−n(n−1)dh(h+1)​

Exercises

It turns out that the maxima of 2βhn−1−dh(h+1)n(n−1)\frac{2\beta h}{n-1}-\frac{dh(h+1)}{n(n-1)}n−12βh​−n(n−1)dh(h+1)​is β2d\frac{\beta^2}ddβ2​as n,h→∞n,h\to\inftyn,h→∞. One way to achieve this is by settingn=dβhn=\frac d\beta hn=βd​hand we obtain

B<4δ−14(1n)1n−1N(h−1)β2dh−βB<\sqrt{\frac{4\delta-1}4}\left(\frac1n\right)^{\frac1{n-1}}N^{\frac{(h-1)\beta^2}{dh-\beta}}B<44δ−1​​(n1​)n−11​Ndh−β(h−1)β2​

and this indeed achieves the O(Nβ2d)O\left(N^{\frac{\beta^2}d}\right)O(Ndβ2​)bound. Similar to the Coppersmith algorithm, one chooses a sufficiently big h,nh,nh,nsuch that the remainding bits can be brute forced in constant time while the algorithm still remains in polynomial time.

1) We show that the maximum of2βhn−1−dh(h+1)n(n−1)\frac{2\beta h}{n-1}-\frac{dh(h+1)}{n(n-1)}n−12βh​−n(n−1)dh(h+1)​is indeed β2d\frac{\beta^2}ddβ2​. We can assume that d≥2,h≥1,0<β≤1,n≥2d\geq2,h\geq1,0<\beta\leq1,n\geq2d≥2,h≥1,0<β≤1,n≥2. Since hn−1(2β−dh+1n)\frac h{n-1}\left(2\beta-d\frac{h+1}{n}\right)n−1h​(2β−dnh+1​)and hn−1<h+1n\frac h{n-1}<\frac{h+1}nn−1h​<nh+1​, the maximum occurs when h,n→∞h,n\to\inftyh,n→∞and hn−1,h+1n→x\frac h{n-1},\frac{h+1}n\to xn−1h​,nh+1​→x, hence we have reduced this to maximizing 2βx−dx22\beta x-dx^22βx−dx2which achieves its maximum of β2d\frac{\beta^2}ddβ2​ at x=βdx=\frac\beta dx=dβ​.