Coppersmith's methodのお気持ちと実装

#yoshicamp2020winter

hellmanのPh.D 資料

Coppersmith-Aleksei-Udovenko.pdf

到達目標

Coppersmith's methodのお気持ちがわかる
univariateな多項式に対してのCoppersmith's methodが実装できる
multivariateな多項式に対してのCoppersmith's methodが実装できる

なぜわざわざ学ぶのか

→拡張・改造できるようになるため

Multivariateな多項式のsmall_rootsを求める効率の良い方法は、式の形によって異なる（らしい）

お気持ちパート

e_shiho氏の katagaitai workshop 2018 winter ベースです

まずは1変数多項式（univariate polynomial）から

問題: monicな1変数多項式 $f(x)$ について、 $f(x_0) \equiv 0 \mod N$ を満たす小さい $x_0$ を求めたい

🤔小さいとは……

Coppersmith Thm. (May03)

monicな1変数 $d$ 次多項式 $f$ の、 $f(x_0) \equiv 0 \mod b$ を満たす $|x_0| < N^{\beta^2 / d}$ を $\log N, d$ の多項式時間で求めることができる
ここで $b$ は $N$ の因数かつ $N^\beta \le b$

おきもち(1)

modular多項式を解くのは難しい
ただの整数係数多項式なら簡単

→modular多項式を整数係数多項式にうまく変換できれば解けるのでは？

modular多項式が整数係数多項式に変換できているとは？ 🤔
$f(x) \equiv 0 \mod N$ の解 $x_0$ を用いた等式 $f(x_0) - kN = 0$ で、 $k = 0$ のとき
$k = 0$ となるような条件を表すのが Howgrave-Graham's Lemma

Howgrave-Graham's Lemma

略（そんなに難しくないけどややこしいし、中身に興味がない。詳しくはe_shihoさんの発表資料を見て）
主張：多項式の係数が小さいと良い

お気持ち(2)

多項式 $f$ を、根は変えないまま変形して、小さい係数を持つようにしたい
- 線型結合
- LLL
方程式を増やして係数行列を LLL で簡約する

方程式を増やす

そのままでは方程式を増やすのは難しいので $\mod N^m$ の世界に持ち上げて増やす
具体例
$N^m, xN^m, \dots, x^{d-1}N^m$
$N^{m-1}f, xN^{m-1}f, \dots, x^{d-1}N^mf$
$Nf^{m-1}, xNf^{m-1}, \dots, x^{d-1}Nf^{m-1}$
更に
$f^m, xf^m, \dots, x^{t-1}f^{m}$
↑↑↑↑
定式化すると
適当な整数kを用いて $f(x_0) = kN$ 。両辺 $i$ 乗して $f^i = k^i N^i$
$g_{i,j}(x) = N^{m-i}x^{j} f^{i}$ とすると、 $f^i$ 展開して $N^{m-i}x^{j}k^i N^i = N^m x^{j}k^i$
なので、 $g_{i,j}(x_0) \equiv 0 \mod N^m$

LLLで小さい係数を探す

$\begin{pmatrix} g_{0,0}(xX) \ g_{0,1}(xX) \ \vdots \ g_{0,d-1}(xX) \ g_{1,0}(xX) \ \vdots \ g_{m-1,d-1}(xX) \ h_0(xX) \ \vdots \ h_{t-1}(xX) \end{pmatrix}$

（縦ベクトルに見えるけど実際は $(dm + t) \times (dm+t)$ 次の係数行列）

（ $X$ は $|x_0| < X$ を満たすBound）

整数方程式の根を求める

LLLの結果得られた小さい係数の関数がHowgrave-Graham's Lemmaを満たしているか調べて、満たしていれば整数方程式を解く

復習

多項式を増殖させて
LLLして
整数方程式を解く

実装パート

def small_roots(f, X, m, t):
  M = f.parent().modulus()
  d = f.degree()

  f = f.change_ring(ZZ)
  x = f.parent().gen()

  """
  方程式を増やすパート
  """
  g = []
  ...

  """
  係数を行列にするパート
  """
  B = matrix(ZZ, ...)

  """
  LLL
  """
  B = B.LLL()

  for row in B:
    if row.is_zero():
      continue

    # Howgrave-Graham's theorem
    if RR(row.norm()) >= RR(M^m / sqrt(len(row))):
      continue

    """
    方程式を復元する
    """
    poly = ...
    roots = poly.roots()
    if roots:
        return roots[0][0]


PRIME_SIZE = 512
KNOWN_SIZE = 270

p = random_prime(1<<PRIME_SIZE)
q = random_prime(1<<PRIME_SIZE)
n = p * q

MOD = 1<<KNOWN_SIZE
low_p = p % MOD
PR.<x> = PolynomialRing(Zmod(n))
f = low_p + x*MOD
f = f.monic()

set_verbose(2)
print(small_roots(f, X=2^(PRIME_SIZE - KNOWN_SIZE), m=13, t=39))

事前課題で解いた問題を自作small_rootsで解き直してみよう

multivariateへの拡張

当然multivariateへと拡張したくなる
考えることは色々ある
- MultivariateでもHowgrave-Graham's Lemmaのような定理が成り立つのか
- 整数係数多変数多項式が求められたとして、その小さい根はどのように求めるのか
- どうやって式を増やして、小さい係数の多項式にするのか
実装するのは大変だし説明できないこともたくさんあるので気持ちだけ

MultivariateのHowgrave-Graham's Lemma

成り立つ

Multivariate polynomialの根

一般的に解ける方法はない
のでHeuristicに、多くの場合に解ける方法でやる
- 終結式（Resultant; 古くは消去式(eliminant)とも）という考えを使う
ある多項式の組 $f_1(x,y), f_2(x,y)$ の共通根を探す。 $r(x) := res_y(f_1, f_2)$ とかいて２つの2変数多項式から1変数多項式を作れる。1変数多項式なら解けるのでこれを解く

多項式の増やし方

$f(x,y)$ に対して $g_{i,j,k}(x,y) = N^{m-i}x^{j}y^{k}f^i(x,y)$ というようにやるとできる

参考文献

実践パート

def small_roots(f, X, m, t):
  M = f.parent().modulus()
  d = f.degree()

  f = f.change_ring(ZZ)
  x = f.parent().gen()

  g = [x^j * M^(m-i) * f^i for i in range(m) for j in range(d) ]
  g.extend([x^i * f^m for i in range(t)]) # h
  max_degree = max(gi.degree() for gi in g)
  B = matrix(ZZ, len(g), max_degree + 1)
  for i in range(B.nrows()):
      for j in range(g[i].degree()+1 ):
          B[i,j] = g[i][j]*X^j

  # g = []
  # for j in range(d):
  #   for i in range(m):
  #     g.append((x*X)^j * M^(m-i) * f(x*X)^i)
  # for i in range(t):
  #   g.append((x*X)^i * f(x*X)^m)
  # max_degree = max(gi.degree() for gi in g)
  # B = matrix(ZZ, len(g), max_degree + 1)
  # for i in range(B.nrows()):
  #     for j in range(g[i].degree()+1 ):
  #         B[i,j] = g[i][j]

  B = B.LLL()

  all_roots = set()
  for row in B:
    if row.is_zero():
      continue

    if RR(row.norm()) >= RR(M^m / sqrt(len(row))):
      continue

    poly = sum(ZZ(row[i] / X^i) * x^i for i in range(len(row)))
    roots = poly.roots()
    for r in roots:
      all_roots.add(r[0])

    return all_roots


PRIME_SIZE = 512
KNOWN_SIZE = 270

p = random_prime(1<<PRIME_SIZE)
q = random_prime(1<<PRIME_SIZE)
n = p * q

MOD = 1<<KNOWN_SIZE
low_p = p % MOD
PR.<x> = PolynomialRing(Zmod(n))
f = low_p + x*MOD
f = f.monic()

set_verbose(2)
print(small_roots(f, X=2^(PRIME_SIZE - KNOWN_SIZE), m=13, t=39))

メモ

Coppersmith Thm. 4
 monicな1変数d次多項式 f(x) について、 f(x_0) ≡ 0 mod N を満たす 小さい |x_0| < N^{1/d} を効率良く求めることができる

Coppersmith Thm. 5
 monicな1変数1次多項式 f(x) について、 f(x_0) ≡ 0 mod b を満たす小さい |x_0| < N^{beta^2} を効率よく求めることができる
 ただし、 b >= N^{beta} かつ b | N

 剰余の法がわからなくても剰余の法を因数に持つ合成数がわかっていればよい

Coppersmith Thm. 6
 monicな1変数d次多項式 f(x) について、 f(x_0) ≡ 0 mod b を満たす小さい |x_0| < N^{beta^2 / d} を log N, dの多項式時間で求めることができる
 ただし、 b >= N^{beta} かつ b|N

 Thm. 5がd次多項式に拡張された

Hawgrave-Graham Lemma
 整数係数多項式g(x) \in Z[x] に対して g(x_0) ≡ 0 mod M の小さい解 |x_0| < X について、  |g(xX)| < M / sqrt(w) なら、 g(x_0) = 0 という整数方程式が成立する（ただし w はgの項の数で、 |g(x)| = sqrt( sum g_i ^2 )）

 g(x) ≡ 0 mod M の係数が十分小さく、解もそれなりに小さい時なんかいい感じになる
 mod 方程式と整数方程式で解が同じになる部分があるけど、その部分に解があるかを調べている（？）

Lemma 9.
 f(x_0) ≡ 0 mod Mであるようなf(x)について、 g_{i,j}(x) = M^{m-i}x^{j}f^{i}(x) ( i <= m, j <= l) とすると、 g_{i,j}(x_0) ≡ 0 mod M^m

 証明:
  適当な整数kを用いて f(x_0) = kM . 両辺 i乗して f^i = k^i M^i .
  g_{i,j}(x_0) = M^{m-i}x_0^{j} f^{i} = M^{m-i}x_0^{j}k^i M^i = M^m x_0^{j}k^i
  なので、 mod M^m とると
  g_{i,j}(x_0) ≡ 0 mod M^m

---

Coppersmith
 適当なパラメータ: m, l （heuristicに選んだりなんか理論をもって選んだりする）
 入力: mod M, monic な d次多項式 f(x), bound X
 出力: f(x_0) ≡ 0 mod M , |x_0| < X を満たす x_0

 方針：
  - 方程式を増やす
  - 方程式を組み合わせて、特定の条件を満たす方程式を作る
   + f(x_0) = 0 + kM で k = 0となるような感じにしたい
   + 方程式の係数が小さくなる方向に変形したい
  - 解く

 やること：
  - Lemma 9. を用いて同じ根を持つ方程式を増殖させる（ここでパラメータm, lを使う）
  - 同じ根を持つ方程式同士の線型結合は同じ根を持つ方程式を作る
  - 係数を小さくするためにLLLする
   + 増殖した g_{i,j}の係数行列を使う
   + ここで単に係数を使ってはだめで、 xの代わりにxXを使う（後でHowgrave Grahamで評価するときにはこっちを使うので）
  - LLLで係数が小さくなった方程式をHowgrave Grahamでチェックして、良さげなら解を探索する


=== ここからMultivariate === 

Howgrave Graham for Bivariate Polynomial
 整数係数2変数多項式g(x,y) ∈ Z[x,y] について、 g(x_0, y_0) ≡ 0 mod M を満たす |x_0| < X, |y_0| < Y が |g(xX, yY)| < M / sqrt(w) を満たす時、g(x_0, y_0) = 0 が整数方程式として成立する

Howgrave Graham for Multivariate Polynomial
 整数係数n変数多項式g(x_1, x_2, ..., x_n) ∈ Z[x_1, x_2, ..., x_n] について、 g(x_1', x_2', ..., x_n') ≡ 0 mod M を満たす |x_1'| < X_1, |x_2| < X_2, ..., |x_n| < X_n が |g(x_1X_1, x_2X_2, ..., x_nX_n)| < M / sqrt(w) を満たす時、g(x_1, x_2, ..., x_n) = 0 が整数方程式として成立する

多項式の増やし方
 f(x,y)に対して g_{i,j,k}(x,y) = M^{m-i}x^{j}y^{k}f^i(x,y) というようにやる

係数が小さい多変数多項式を見つけられたとして……？
 消去式と言うものがあり、線形独立かつ共通の根を持つf(x,y)とg(x,y) から h(x) = Res_y(f,g) や g(y) = Res_x(f,g)といった一変数多項式を作ることができる。同様にf(x,y,z)とg(x,y,z)に対して h(x,y) = Res_z(f,g) みたいな感じになる

Unravelled linearization
 愚直に多項式を増やしていると項も増えるし係数も増えるので大変なので、変数変換を用いた手法で抑制していく。例えば xy+1+Ax ≡ 0 mod M を u + Ax ≡ 0 mod M に変換する（ここで非線形項を置き換えている。係数の大小の影響が小さいので）。そして多項式を増やす時は g_{i,j,k}(u,x,y) = M^{m-k}x^{i}y^{j}f^k(u, x) として、 uについて増やさず、xとyについて増やしている