格子暗号

同義語:格子ベース暗号lattice-based cryptographylattice cryptography

概要

格子暗号(lattice-based cryptography)とは、格子の短いベクトルを見つける問題の難しさを安全性の根拠にする暗号の総称で、雑音を加えた連立 1 次合同式から未知数を求める誤差つき学習問題(LWE)と、合同式の短い整数解を求める短整数解問題(SIS)を中心に組み立てられる。Regev の公開鍵暗号では、誤差の和が法の 4 分の 1 程度より小さければ復号は必ず正しく、LWE の判定版が難しければ暗号文から平文を当てることはできない。LWE の難しさは、量子計算を使う帰着によって格子の問題の最悪の場合の難しさに結びつけられており、その格子の問題には 2016 年の時点で量子計算機でも効率のよい解法が知られていないので、量子計算機の時代の暗号の候補とされる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 公開鍵暗号, 剰余環, 格子(数論)

格子暗号(lattice-based cryptography)は、格子の短いベクトルを見つける問題の難しさを安全性の根拠にする暗号の総称である。中心にあるのは、雑音を加えた連立 1 次合同式から未知数を求める 誤差つき学習問題(learning with errors, LWE)と、合同式の短い解を求める 短整数解問題(short integer solution, SIS)の 2 つで、どちらも「すべての格子で難しいなら、乱数で作った例でも難しい」という型の定理(最悪の場合から平均の場合への帰着)をもつ。
RSA暗号 や離散対数にもとづく暗号は、量子計算機があれば Shor のアルゴリズムで破られる。格子の問題には、2016 年 2 月の概説 Pei16(p. 3、p. 8)の時点で、量子計算機を使っても効率のよいアルゴリズムが知られておらず、量子計算機の時代にも使える暗号の候補になっている。
この記事では LWE と SIS を定義し、Regev の公開鍵暗号を例に、復号が正しいための条件(主定理)、LWE の判定版が難しければ暗号が安全であること、探索版と判定版の関係、SIS と衝突しにくいハッシュ関数の関係を証明する。格子の問題への帰着そのもの(Regev の定理)は証明しない。

定義

$q\ge2$ を整数とし、$\mathbb{Z}_q=\mathbb{Z}/q\mathbb{Z}$ と書く(剰余環)。$x\in\mathbb{Z}_q$ について、$x$ を表す整数のうち絶対値が最小のものの絶対値を $\lvert x\rvert_q$ と書き、$x,y\in\mathbb{Z}_q$ の距離を $\lvert x-y\rvert_q$ とする($\mathbb{Z}_q$ を円周に並べたときの距離)。$\lvert x+y\rvert_q\le\lvert x\rvert_q+\lvert y\rvert_q$ である。

格子と格子の問題

1 次独立な $b_1,\dots,b_n\in\mathbb{R}^n$ について、$\mathcal{L}(B)=\{z_1b_1+\dots+z_nb_n:z_i\in\mathbb{Z}\}$ を 格子、$B=(b_1,\dots,b_n)$ をその 基底 という。$\lambda_1(\mathcal{L})$ を $0$ でない格子の点のノルムの最小値、$\lambda_n(\mathcal{L})$ を「長さ $r$ 以下の 1 次独立な格子の点が $n$ 個とれる」最小の $r$ とする。$\gamma\ge1$ について次の問題を考える。

  1. SVP$_\gamma$:基底が与えられたとき、$0<\|v\|\le\gamma\lambda_1$ をみたす格子の点 $v$ を求める。
  2. GapSVP$_\gamma$:基底と $d>0$ が与えられ、$\lambda_1\le d$ か $\lambda_1>\gamma d$ のどちらかが成り立つとき、どちらかを判定する。
  3. SIVP$_\gamma$:基底が与えられたとき、長さ $\gamma\lambda_n$ 以下の 1 次独立な格子の点を $n$ 個求める。

同じ格子にも短くほぼ直交する基底と、長く平行に近い基底がある(ex-lc-lattice)。悪い基底しか知らない者に短いベクトルを求めさせるのが、格子暗号の考え方の出発点である。

短整数解問題(SIS)

整数 $n,m,q$ と $\beta>0$ を固定する。$\mathbb{Z}_q$ の成分をもつ一様な乱数の $n\times m$ 行列 $A$ が与えられたとき、
$$ Az\equiv0\pmod q,\qquad z\in\mathbb{Z}^m,\qquad 0<\|z\|\le\beta $$
をみたす $z$ を求める問題を $\mathrm{SIS}_{n,q,\beta,m}$ という。

$\Lambda^\perp(A)=\{z\in\mathbb{Z}^m:Az\equiv0\}$ は $q\mathbb{Z}^m$ を含むので $\mathbb{R}^m$ の格子であり、SIS はこの格子の短いベクトルを求める問題である。解の格子の構造、解の存在、LLL で解ける範囲、Ajtai の帰着の核は SIS問題 で扱う。

誤差つき学習問題(LWE)

整数 $n\ge1$、$q\ge2$ と $\mathbb{Z}_q$ 上の確率分布 $\chi$(誤差の分布。$0$ の近くに集中したものをとる)を固定する。$s\in\mathbb{Z}_q^n$ について、$a\in\mathbb{Z}_q^n$ を一様に、$e$ を $\chi$ に従って独立に選び、$(a,\ a\cdot s+e)\in\mathbb{Z}_q^n\times\mathbb{Z}_q$ を出力する分布を $A_{s,\chi}$ と書く。

  1. 探索版:$A_{s,\chi}$ からの独立な標本 $m$ 個が与えられたとき、$s$ を求める。
  2. 判定版:$m$ 個の独立な標本が、$A_{s,\chi}$($s$ は一様な乱数)からのものか、$\mathbb{Z}_q^n\times\mathbb{Z}_q$ の一様分布からのものかを判定する。判定の手続き $D$(出力は $0$ か $1$)の 優位度 を $\lvert\Pr[D(A_{s,\chi}^m)=1]-\Pr[D(U^m)=1]\rvert$ とする($U$ は一様分布)。

標本を並べると $b=A^{\mathsf T}s+e$($A$ は $a_i$ を列とする $n\times m$ 行列)で、誤差 $e$ がなければ Gaussの消去法 で $s$ が求まる(反例の表)。誤差を加えるだけで問題が難しくなると考えられていることが、LWE の要点である。

Regev の暗号

$q$ を素数とし、$n,m,\chi$ を固定する。

  1. 鍵の生成:$s\in\mathbb{Z}_q^n$ を一様に選んで秘密鍵とし、$A_{s,\chi}$ からの標本 $(a_i,b_i)$($i=1,\dots,m$)を公開鍵とする。
  2. 暗号化(平文 $\mu\in\{0,1\}$):$\{1,\dots,m\}$ の部分集合 $S$ を一様に選び、$c=\Bigl(\sum_{i\in S}a_i,\ \sum_{i\in S}b_i+\mu\lfloor q/2\rfloor\Bigr)$ を暗号文とする。
  3. 復号(暗号文 $(a,b)$):$d=b-a\cdot s$ とし、$\lvert d\rvert_q<\lvert d-\lfloor q/2\rfloor\rvert_q$ なら $0$、そうでなければ $1$ を出力する。

公開鍵は $m(n+1)$ 個、暗号文は 1 ビットあたり $n+1$ 個の $\mathbb{Z}_q$ の元である。公開鍵暗号 の定義の形(鍵の生成・暗号化・復号の 3 つの手続き)に当てはまるが、復号の正しさは誤差の大きさによる(主定理)。

公式の表

主張条件結論根拠
復号の正しさすべての $i$ で $\lvert e_i\rvert_q\le r$、$mr<\frac12\lfloor q/2\rfloor$どの $S$・$\mu$ でも復号は $\mu$ を返すthm-lc-correct
安全性判定版 LWE の優位度が $\delta_0,\delta_1$ 以下暗号文から $\mu$ を当てる優位度 $\le\delta_0+\delta_1+\sqrt{q^{n+1}/2^m}$thm-lc-security
探索から判定へ$q$ が素数判定版を常に正しく解く手続きを $nq$ 回使えば探索版が解けるlem-lc-search-decision
衝突から SIS へ$m>n\log_2q$$x\mapsto Ax\bmod q$($x\in\{0,1\}^m$)の衝突は SIS の解($\beta=\sqrt m$)prop-lc-hash
余りのハッシュ補題有限 Abel 群 $G$一様な $g_1,\dots,g_m$ の部分和は一様分布から統計的距離 $\frac12\sqrt{\lvert G\rvert/2^m}$ 以内lem-lc-lhl
Regev の定理$\chi$ は幅 $\alpha q\ge2\sqrt n$ の離散化した正規分布、$0<\alpha<1$判定版 LWE は量子計算で GapSVP$_\gamma$・SIVP$_\gamma$($\gamma=\tilde O(n/\alpha)$)より易しくない証明しない:Reg09 Theorem 1.1(p. 2)、Pei16 Theorem 4.2.4(p. 24)
SIS の最悪の場合からの帰着$q\ge\beta\cdot\mathrm{poly}(n)$SIS は GapSVP$_\gamma$・SIVP$_\gamma$($\gamma=\beta\cdot\mathrm{poly}(n)$)より易しくない証明しない:Pei16 Theorem 4.1.2(p. 20)

$\tilde O$ は対数の因子を除いた程度を表す。最後の 2 行の「易しくない」は、左の問題を解く効率のよい手続きがあれば、右の問題を解く効率のよい手続き(Regev の定理では量子計算の手続き)が作れることを意味する。

主定理と証明

復号の正しさ

復号の正しさ

Regev の暗号(def-lc-regev)で、公開鍵の誤差 $e_i=b_i-a_i\cdot s$ がすべて $\lvert e_i\rvert_q\le r$ をみたし、$mr<\frac12\lfloor q/2\rfloor$ とする。このとき、どの部分集合 $S$ とどの平文 $\mu\in\{0,1\}$ についても、暗号文の復号は $\mu$ を返す。

誤差の和が小さいまま残る

暗号文を $(a,b)$ とすると $a=\sum_{i\in S}a_i$、$b=\sum_{i\in S}(a_i\cdot s+e_i)+\mu\lfloor q/2\rfloor$ なので
$$ d=b-a\cdot s=E+\mu\lfloor q/2\rfloor,\qquad E:=\sum_{i\in S}e_i $$
である。三角不等式から $\lvert E\rvert_q\le\sum_{i\in S}\lvert e_i\rvert_q\le mr<\frac12\lfloor q/2\rfloor$ である。また $\lfloor q/2\rfloor\le q/2$ なので $\bigl\lvert\lfloor q/2\rfloor\bigr\rvert_q=\lfloor q/2\rfloor$ である。
$\mu=0$ のとき:$d=E$ で、$\lvert d\rvert_q=\lvert E\rvert_q$。一方、三角不等式 $\lfloor q/2\rfloor=\bigl\lvert\lfloor q/2\rfloor\bigr\rvert_q\le\lvert d\rvert_q+\lvert d-\lfloor q/2\rfloor\rvert_q$ から
$$ \lvert d-\lfloor q/2\rfloor\rvert_q\ge\lfloor q/2\rfloor-\lvert E\rvert_q>\tfrac12\lfloor q/2\rfloor>\lvert E\rvert_q=\lvert d\rvert_q $$
なので、復号は $0$ を返す。
$\mu=1$ のとき:$\lvert d-\lfloor q/2\rfloor\rvert_q=\lvert E\rvert_q$ で、同じ三角不等式から $\lvert d\rvert_q\ge\lfloor q/2\rfloor-\lvert E\rvert_q>\lvert E\rvert_q$ なので、$\lvert d\rvert_q<\lvert d-\lfloor q/2\rfloor\rvert_q$ は成り立たず、復号は $1$ を返す。$\square$

実際の暗号では $\chi$ を幅 $\alpha q$ の離散化した正規分布にとるので、誤差は有界ではない。このときは $E$ が $\frac12\lfloor q/2\rfloor$ 未満である確率を評価し、たとえば $q$ を $n^2$ と $2n^2$ の間の素数、$\alpha=o\bigl(1/(\sqrt n\log n)\bigr)$ にとると、復号を誤る確率は $n\to\infty$ で $0$ に近づく(Reg09 Lemma 5.1 と §5 のパラメータ、pp. 31–32。この記事では証明しない)。公開鍵暗号 の定義は確率 1 の正しさを求めるので、それに当てはめるには誤差を切り詰めるか、高い確率での正しさに定義を緩める。

安全性

確率分布 $P,Q$ の 統計的距離 を $\Delta(P,Q)=\frac12\sum_x\lvert P(x)-Q(x)\rvert$ とする。どんな手続き $D$(乱数を使ってもよい)についても $\lvert\Pr_P[D=1]-\Pr_Q[D=1]\rvert\le\Delta(P,Q)$ である。

余りのハッシュ補題

$G$ を有限 Abel 群とし、$g_1,\dots,g_m\in G$ を一様に、$\{1,\dots,m\}$ の部分集合 $S$ を一様に、すべて独立に選ぶ。$u\in G$ を一様で独立な乱数とすると
$$ \Delta\Bigl(\bigl(g_1,\dots,g_m,\textstyle\sum_{i\in S}g_i\bigr),\ (g_1,\dots,g_m,u)\Bigr)\le\frac12\sqrt{\frac{\lvert G\rvert}{2^m}}. $$

証明を開く

$g=(g_1,\dots,g_m)$ を固定し、$P_g(h)=\Pr_S[\sum_{i\in S}g_i=h]$ とおく。左辺は $\mathbb{E}_g\,\Delta(P_g,U)$ に等しい。Cauchy–Schwarz の不等式から $\Delta(P_g,U)\le\frac12\sqrt{\lvert G\rvert}\,\bigl(\sum_h(P_g(h)-\lvert G\rvert^{-1})^2\bigr)^{1/2}$ で、$\sum_h(P_g(h)-\lvert G\rvert^{-1})^2=\sum_hP_g(h)^2-\lvert G\rvert^{-1}$ である。$\sum_hP_g(h)^2$ は、独立な一様な部分集合 $S,S'$ について $\sum_{S}g_i=\sum_{S'}g_i$ となる確率である。$S=S'$ の確率は $2^{-m}$ で、$S\ne S'$ のときは $S,S'$ の一方だけに入る $j$ があり、$\sum_Sg_i-\sum_{S'}g_i=\pm g_j+(g_j\text{ を含まない和})$ は $g$ について平均すると $G$ 上一様なので、等しくなる確率は $\lvert G\rvert^{-1}$ である。よって $\mathbb{E}_g\sum_hP_g(h)^2\le2^{-m}+\lvert G\rvert^{-1}$ で、$\sqrt{\ }$ の凹性から $\mathbb{E}_g\Delta(P_g,U)\le\frac12\sqrt{\lvert G\rvert}\sqrt{2^{-m}}$ である。$\square$(Reg09 Claim 5.3、p. 33 は係数 $\frac12$ のない形。)

LWE による安全性

Regev の暗号の公開鍵 $\mathit{pk}$ と平文 $\mu$ の暗号文 $c_\mu$ を受け取って $0$ か $1$ を出力する手続き $D$ について、$D'_\mu$ を「$m$ 個の標本を公開鍵とみなし、それで $\mu$ を暗号化して、標本と暗号文を $D$ に渡す」手続きとし、その判定版 LWE の優位度を $\delta_\mu$ とする。このとき
$$ \bigl\lvert\Pr[D(\mathit{pk},c_0)=1]-\Pr[D(\mathit{pk},c_1)=1]\bigr\rvert\le\delta_0+\delta_1+\sqrt{\frac{q^{n+1}}{2^m}}. $$

公開鍵を一様な乱数に取り替える

$\mu\in\{0,1\}$ を固定する。次の 3 つの分布を比べる。

  • $H_1$:本物の公開鍵と $\mu$ の暗号文の組 $(\mathit{pk},c_\mu)$。
  • $H_2$:公開鍵の代わりに一様な乱数 $(a_i,u_i)\in\mathbb{Z}_q^n\times\mathbb{Z}_q$($i=1,\dots,m$)を使い、それで $\mu$ を暗号化した組。
  • $H_3$:一様な乱数 $(a_i,u_i)$ と、それと独立な一様な $(a,b)\in\mathbb{Z}_q^{n+1}$ の組。
    $D$ が $H_1$ で $1$ を出す確率は $D'_\mu$ に $A_{s,\chi}^m$ を渡したときの確率、$H_2$ で $1$ を出す確率は $D'_\mu$ に $U^m$ を渡したときの確率なので、差は $\delta_\mu$ 以下である。$H_2$ の暗号文は $\bigl(\sum_{i\in S}(a_i,u_i)\bigr)+(0,\mu\lfloor q/2\rfloor)$ である。lem-lc-lhl を $G=\mathbb{Z}_q^{n+1}$ に使うと、$\bigl((a_i,u_i)_i,\sum_S(a_i,u_i)\bigr)$ と $\bigl((a_i,u_i)_i,\text{一様}\bigr)$ の統計的距離は $\frac12\sqrt{q^{n+1}/2^m}$ 以下である。一様な元に $(0,\mu\lfloor q/2\rfloor)$ を足しても一様なので、$H_2$ と $H_3$ の統計的距離も同じ上界をもつ。
    $H_3$ は $\mu$ によらない。よって $\Pr[D(\mathit{pk},c_\mu)=1]$ は $\mu$ によらない数 $\Pr_{H_3}[D=1]$ から $\delta_\mu+\frac12\sqrt{q^{n+1}/2^m}$ 以内にあり、$\mu=0,1$ の差は主張の右辺以下である。$\square$

$m\ge(1+\varepsilon)(n+1)\log_2q$ なら $\sqrt{q^{n+1}/2^m}\le2^{-\varepsilon(n+1)\log_2q/2}$ で、$n$ について指数関数的に小さい。したがって、判定版 LWE を有意な優位度で解く効率のよい手続きがなければ、暗号文から平文を有意に当てる効率のよい手続きもない(Reg09 Lemma 5.4、p. 34 と同じ論法)。これは 公開鍵暗号 の意味的安全性で、平文を $\{0,1\}$ に限った場合である。

探索版と判定版

探索版から判定版への帰着

$q$ を素数とする。標本の分布が $A_{s',\chi}$(ある $s'$)か一様分布かを、どの $s'$ についても正しく判定する手続き $W$ があるとする。このとき $A_{s,\chi}$ の標本から、$W$ を高々 $nq$ 回使って $s$ を求められる。

1 成分ずつ試す

$s$ の第 1 成分 $s_1$ を求める(他の成分も同じ)。$k\in\mathbb{Z}_q$ を 1 つ選び、各標本 $(a,b)$ に、標本ごとに独立に選んだ一様な $l\in\mathbb{Z}_q$ を使って
$$ (a,b)\longmapsto(a',b'):=\bigl(a+(l,0,\dots,0),\ b+lk\bigr) $$
と変換する。$a$ は一様で $l$ と独立なので、$a'$ は一様で $l$ と独立である。$b=a\cdot s+e$ から
$$ b'=a'\cdot s+e+l(k-s_1) $$
である。$k=s_1$ なら $(a',b')$ は $A_{s,\chi}$ に従う。$k\ne s_1$ なら、$q$ が素数なので $k-s_1$ は $\mathbb{Z}_q$ の可逆元で、$l(k-s_1)$ は $(a',e)$ と独立な一様な乱数になり、$b'$ は $a'$ と独立に一様になる。よって変換後の標本を $W$ に渡すと、$W$ が「$A_{s',\chi}$ の形」と答えるのは $k=s_1$ のときに限る。$k$ を $q$ 通り試せば $s_1$ が決まり、$n$ 成分で $nq$ 回である。$\square$

実際には $W$ は一定の確率でしか正しく答えないので、多数の標本で多数決をとる議論を加える(Reg09 Lemma 4.2、p. 31。$q$ は $n$ の多項式以下の素数)。逆に探索版が解ければ、$s$ を求めて $b_i-a_i\cdot s$ が小さいかを見ることで判定版も解けるので、2 つは同じ難しさである。

SIS と衝突しにくいハッシュ関数

衝突から SIS の解へ

$A$ を $\mathbb{Z}_q$ 成分の $n\times m$ 行列とし、$f_A(x)=Ax\bmod q$($x\in\{0,1\}^m$)とおく。

  1. $m>n\log_2q$ なら $f_A(x)=f_A(x')$ となる $x\ne x'$ が存在する。
  2. そのような $x,x'$ について、$z=x-x'$ は $\mathrm{SIS}_{n,q,\sqrt m,m}$ の解である。
証明を開く

1:定義域は $2^m$ 個、値域は $q^n$ 個で、$m>n\log_2q$ は $2^m>q^n$ と同じなので、鳩の巣原理による。2:$z=x-x'\in\{0,\pm1\}^m$ は $0$ でなく、$Az\equiv Ax-Ax'\equiv0$、$\|z\|\le\sqrt m$ である。$\square$

したがって、SIS が難しければ $f_A$ は ハッシュ関数 として衝突しにくい。Ajtai は 1996 年に、SIS が平均の場合に難しいことを格子の問題の最悪の場合の難しさから導き、これが格子暗号の始まりになった(Pei16 p. 13、§4.1 pp. 18–20)。

Regev の定理と安全性の仮定

Regev の定理

$m$ を $n$ の多項式以下、$q\le2^{\mathrm{poly}(n)}$ とし、$\chi$ を幅 $\alpha q\ge2\sqrt n$($0<\alpha<1$)の離散化した正規分布とする。判定版 LWE を解く効率のよい手続きがあれば、任意の $n$ 次元の格子で GapSVP$_\gamma$ と SIVP$_\gamma$($\gamma=\tilde O(n/\alpha)$)を解く効率のよい量子アルゴリズムが作れる。

証明の所在

この定理は証明しない(Reg09 Theorem 1.1、p. 2。この形は Pei16 Theorem 4.2.4、p. 24)。帰着は量子計算を使うが、仮定する LWE の解法は古典的な手続きでよい。2009 年に Peikert は GapSVP について古典的な帰着を与えたが、$q\ge2^{n/2}$ が要り、SIVP には及ばない(Pei16 §4.2.4、pp. 25–26)。

安全性の仮定:格子暗号の安全性は「多項式の近似比 $\gamma$ の GapSVP$_\gamma$・SIVP$_\gamma$ を多項式時間で解くアルゴリズムは(量子計算でも)ない」という予想に頼っている(Reg09 p. 3 は古典計算についてこれを予想として述べ、量子計算についても同じ予想を立てうるとしている)。2016 年 2 月の時点で知られている多項式時間のアルゴリズム(LLLアルゴリズム とその改良)の近似比は $2^{\Theta(n\log\log n/\log n)}$ 程度で、多項式の近似比を得るアルゴリズムは $2^{\Theta(n)}$ 以上の時間を要し、量子アルゴリズムでも状況は同じであった(Pei16 p. 8)。

計算の手順

Regev の暗号を手で回す手順をまとめる。

  1. パラメータを選ぶ:素数 $q$、次元 $n$、標本数 $m$、誤差の上界 $r$ を $mr<\frac12\lfloor q/2\rfloor$ となるようにとる(thm-lc-correct)。安全性のためには $m\ge(1+\varepsilon)(n+1)\log_2q$ も要る(thm-lc-security)。
  2. 鍵を作る:$s$ を選び、$b_i=a_i\cdot s+e_i\bmod q$ を計算する。
  3. 暗号化する:部分集合 $S$ を選び、$a_i$ と $b_i$ を $S$ の上で足し、$\mu=1$ なら第 2 成分に $\lfloor q/2\rfloor$ を足す。
  4. 復号する:$d=b-a\cdot s\bmod q$ を計算し、$0$ と $\lfloor q/2\rfloor$ のどちらに $\mathbb{Z}_q$ の円周上で近いかを見る。

例題

良い基底と悪い基底

$b_1=(2,1)$、$b_2=(1,3)$ の格子 $\mathcal{L}$ と、その別の基底 $c_1=4b_1+3b_2=(11,13)$、$c_2=5b_1+4b_2=(14,17)$ を考える。点 $t=(10.4,\,9.3)$ を、基底についての座標を整数に丸めて格子の点に移す。
使う公式:def-lc-lattice。
答え:どちらの基底も行列式は $5$ で同じ格子を生成する。$\lambda_1=\sqrt5$(最短の点は $\pm(2,1)$、$\pm(1,-2)$)。丸めの結果は、良い基底で $(10,10)$($t$ に最も近い格子の点、距離 $0.8062$)、悪い基底で $(1,-2)$(距離 $14.6986$)。

途中の計算を開く

$\begin{pmatrix}4&3\\5&4\end{pmatrix}$ の行列式は $1$ なので、$c_1,c_2$ も $\mathcal{L}$ の基底である。$\det(b_1,b_2)=6-1=5$。$\lambda_1$ は係数 $\lvert z_i\rvert\le20$ の全数え上げで $\|v\|^2=5$。辺 $2\sqrt5$ の閉じた正方形(面積 $20=2^2\cdot5$)に Minkowskiの格子点定理 を使って得られる上界 $\sqrt{2\cdot5}\approx3.162$ 以下である。$t=x_1b_1+x_2b_2$ を解くと $(x_1,x_2)=(4.38,1.64)$ で、丸めて $(4,2)$、$4b_1+2b_2=(10,10)$。悪い基底では $t=9.32\,c_1-6.58\,c_2$ で、丸めて $9c_1-7c_2=(99-98,\,117-119)=(1,-2)$。座標の丸めの誤差 $0.32$、$0.42$ に長い基底ベクトルが掛かるので、遠くの点に飛ぶ。

図: 同じ格子(灰色の点)を 2 つの基底で描いたもの。左は良い基底 (2,1)、(1,3) と面積 5 の基本平行四辺形で、星印の点 t=(10.4, 9.3) を基底の座標の丸めで移すと、最も近い格子の点 (10,10)(赤い円)に移る。右は悪い基底 (11,13)、(14,17) で、基本平行四辺形は細長く同じ面積 5 をもち、同じ丸めで t は距離 14.70 離れた点 (1,−2) に移る。 図: 同じ格子(灰色の点)を 2 つの基底で描いたもの。左は良い基底 (2,1)、(1,3) と面積 5 の基本平行四辺形で、星印の点 t=(10.4, 9.3) を基底の座標の丸めで移すと、最も近い格子の点 (10,10)(赤い円)に移る。右は悪い基底 (11,13)、(14,17) で、基本平行四辺形は細長く同じ面積 5 をもち、同じ丸めで t は距離 14.70 離れた点 (1,−2) に移る。

Regev の暗号の小さな例

$q=29$、$n=2$、$m=6$、$s=(3,7)$。公開鍵の $a_i$ は $(5,11)$、$(17,2)$、$(8,20)$、$(26,14)$、$(1,9)$、$(12,25)$、誤差は $e=(1,-1,0,1,1,-1)$。$S=\{1,3,4\}$ で $\mu=0,1$ を暗号化して復号する。
使う公式:def-lc-regev、thm-lc-correct($r=1$、$mr=6<7=\frac12\lfloor29/2\rfloor$)。
答え:$b=(6,6,19,3,9,7)$。暗号文は $\mu=0$ で $((10,16),28)$、$\mu=1$ で $((10,16),13)$。復号の $d$ はそれぞれ $2$($0$ に近く $0$ を返す)と $16$($14$ に近く $1$ を返す)。64 個の部分集合と 2 つの平文のすべてで復号は正しい。

途中の計算を開く

$b_1=5\cdot3+11\cdot7+1=93\equiv6$ など。$\sum_Sa_i=(5+8+26,\,11+20+14)=(39,45)\equiv(10,16)$、$\sum_Sb_i=6+19+3=28$。$(10,16)\cdot(3,7)=142\equiv26$。$\mu=0$:$d=28-26=2=e_1+e_3+e_4$。$\mu=1$:第 2 成分は $28+14=42\equiv13$、$d=13-26\equiv16$、$\lvert16-14\rvert_{29}=2<\lvert16\rvert_{29}=13$。

SIS の解とハッシュの衝突

$q=7$、$n=1$、$m=4$、$A=(1,2,3,4)$ について、$f_A(x)=x_1+2x_2+3x_3+4x_4\bmod7$($x\in\{0,1\}^4$)の衝突を求める。
使う公式:prop-lc-hash($m=4>\log_27\approx2.807$)。
答え:$x=(1,1,0,0)$ と $x'=(0,0,1,0)$ はどちらも値 $3$ で、$z=(1,1,-1,0)$ は $Az=0$、$\|z\|=\sqrt3\le2=\sqrt m$ の SIS の解である。衝突する組は全部で $11$ 組、$\{0,\pm1\}^4$ の $0$ でない解は $10$ 個で、最短は $\pm(0,0,1,1)$($3+4=7$、$\|z\|=\sqrt2$)である。

使える条件と反例

各定理の条件のうち 1 つだけを外した例を挙げる。

定理外す条件反例成り立たなくなること
thm-lc-correct$mr<\frac12\lfloor q/2\rfloor$ex-lc-regev で誤差をすべて $2$($mr=12$)、$S$ を全体、$\mu=0$$d=12$ は $14$ に近く、復号は $1$ を返す
thm-lc-security誤差(判定版 LWE の難しさ)ex-lc-regev で $e=0$標本 2 個から Gaussの消去法 で $s=(3,7)$ が求まり、すべて復号できる。$\delta_0,\delta_1$ も $1$ に近く、定理の不等式は成り立ったままで、成り立たないのはその後の安全性の結論
thm-lc-security標本数 $m$ が大きいことex-lc-regev の設定で $m=1$暗号文 $(0,0)$ または $(a_1,b_1)$ なら $\mu=0$ と分かり、優位度 $1$。右辺の $\sqrt{q^{n+1}/2^m}=\sqrt{29^3/2}$ が $1$ を超えるので定理の不等式は成り立ったままで、成り立たないのはその後の安全性の結論
thm-lc-security$S$ を一様な乱数で選ぶこと$S$ を常に全体にとる$c_0$ を公開鍵から計算でき、優位度 $1$。$D'_\mu$ の出力は標本の分布によらないので $\delta_0=\delta_1=0$ で、$m$ が大きければ定理の不等式そのものが成り立たない
lem-lc-search-decision$q$ が素数$q=4$、$n=1$、$s_1=1$、$k=3$、誤差は $\{-1,0,1\}$ 上の一様分布変換後の $b'-a's$ の分布は $0,1,2,3$ に $\frac16,\frac13,\frac16,\frac13$ で、どの $s'$ の $A_{s',\chi}$ でも一様分布でもなく、$W$ の仮定の外になって prf-lc-search-decision の論法が使えない
prop-lc-hash の 1$m>n\log_2q$$q=7$、$n=1$、$m=2$、$A=(1,2)$$f_A$ の値 $0,2,1,3$ はすべて異なり、衝突がない
表の反例の確かめ
確認を開く

1 行目:$d=\sum_ie_i=12$、$\lvert12\rvert_{29}=12>\lvert12-14\rvert_{29}=2$。2 行目:$e=0$ なら $b_1=15+77=92\equiv5$、$b_2=51+14=65\equiv7$ で、係数行列 $\begin{pmatrix}5&11\\17&2\end{pmatrix}$ の行列式 $10-187=-177\equiv26$ は $29$ と互いに素なので、連立合同式はただ 1 つの解 $s=(3,7)$ をもつ。3 行目:$S$ は空集合か $\{1\}$ なので、$\mu=0$ の暗号文は $(0,0)$ か $(a_1,b_1)$、$\mu=1$ の暗号文は $(0,14)$ か $(a_1,b_1+14)$ で、公開鍵と比べれば区別できる。4 行目:$c_\mu=(\sum_ia_i,\sum_ib_i+\mu\lfloor q/2\rfloor)$ で、公開鍵から $c_0$ を計算して比べる。5 行目:$b'-a's_1=e+2l$ で、$2l\in\{0,2\}$ は一様ではない。6 行目:$f_A(0,0)=0$、$f_A(1,0)=1$、$f_A(0,1)=2$、$f_A(1,1)=3$。

2 行目は誤差を外すと判定版 LWE が易しくなることを示し、安全性の証明が LWE の難しさに本質的に頼っていることを表す。$q$ が合成数でも LWE の探索版と判定版が同じ難しさであることは、別の論法で示されている(Pei16 p. 25)。

よくある誤り

誤り正しくはなぜ
誤差は大きいほど安全で良い誤差の和が $\frac12\lfloor q/2\rfloor$ を超えると復号を誤るthm-lc-correct と反例の表の 1 行目
Regev の定理で格子暗号の安全性が証明された定理は帰着で、格子の問題の難しさは予想であるthm-lc-regev の後の「安全性の仮定」
同じ公開鍵の標本を少数だけ使う$m\ge(1+\varepsilon)(n+1)\log_2q$ にするlem-lc-lhl の上界が小さくなる条件
判定版の手続きで合成数の $q$ でも 1 成分ずつ $s$ が求まるこの論法は $q$ が素数のとき反例の表の 5 行目
悪い基底しか知らなければ最近点が求まらないので、それだけで安全安全性は定理の形の帰着で裏づける悪い基底を公開鍵にする初期の方式は、実用的なパラメータで解読された(Pei16 pp. 15–16)

補足

  • 効率のよい変種:$\mathbb{Z}_q^n$ の代わりに多項式環 $\mathbb{Z}_q[X]/(X^n+1)$ ($n$ は 2 のべき)などを使う環 SIS・環 LWE では、必要な乱数の元の個数が $n$ 分の 1 程度に減り、FFT の類の方法で掛け算もほぼ $n$ に比例する時間でできる(Pei16 §4.3–4.4、とくに p. 28)。
  • SIS の難しさ:prop-lc-hash と公式の表の最後の行を合わせると、格子の問題が最悪の場合に難しければ、$f_A$ は衝突しにくい ハッシュ関数 になる。
  • 関連する暗号の考え方:公開鍵暗号 の一般論、暗号理論 の安全性の定義、擬似乱数 の判別の考え方は、判定版 LWE の「一様分布と見分けがつかない」という形と同じ枠組みで書かれる。

関連項目

参考文献

[1]
Oded Regev, On lattices, learning with errors, random linear codes, and cryptography, Journal of the ACM, 2009, Theorem 1.1(p. 2)、p. 3(予想)、Lemma 4.2(p. 31)、§5(暗号、pp. 31–32)、Lemma 5.1(p. 32)、Claim 5.3(p. 33)、Lemma 5.4(p. 34)。頁は著者公開版(2009 年 5 月 2 日版)による
[2]
Chris Peikert, A Decade of Lattice Cryptography, Foundations and Trends in Theoretical Computer Science, 2016, p. 3、p. 8(知られているアルゴリズム)、p. 13、pp. 15–16、§4.1(SIS、pp. 18–20、Theorem 4.1.2 p. 20)、§4.2(LWE、Theorem 4.2.4 p. 24、§4.2.4 pp. 25–26)、§4.3–4.4(p. 28)。頁は著者公開版(2016 年 2 月 17 日版)による

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する