SIS問題(short integer solution problem)とは、法 $q$ の一様な乱数の $n\times m$ 行列 $A$ について、$Az\equiv0\pmod q$ をみたす長さ $\beta$ 以下の $0$ でない整数ベクトル $z$ を求める問題で、短整数解問題ともいう。解の全体は行列式 $q^n$ 以下の格子 $\Lambda^\perp(A)$ をなし、鳩の巣原理により長さ $\sqrt m\,q^{n/m}$ 以下の解が必ず存在する。$\beta\ge2^{(m-1)/4}q^{n/m}$ なら LLL アルゴリズムで解けるが、暗号の大きさでは効率のよい解法は 2016 年の時点で知られていなかった。Ajtai(1996)以来、SIS を平均的に解くことは任意の格子の近似最短ベクトル問題より易しくないと示され、ハッシュ関数や格子暗号に使われる。
SIS問題(short integer solution problem、短整数解問題)は、法 $q$ の連立 1 次合同式 $Az\equiv0\pmod q$ の、成分の小さい $0$ でない整数解を求める問題である。$A$ は一様な乱数の行列で与えられる。解の全体は整数の格子 $\Lambda^\perp(A)$ をなし、SIS はこの格子の短いベクトルを求める問題になる。
1996 年に Ajtai は、SIS を平均的に解く手続きがあれば任意の格子の短いベクトルの問題(最悪の場合)も解けることを示した(Pei16 p. 13、Theorem 4.1.2、p. 20)。これが 格子暗号 の出発点で、SIS は衝突しにくい ハッシュ関数 や署名の安全性の根拠になり、誤差つき学習問題(LWE)とも結びつく。
この記事では、解の格子 $\Lambda^\perp(A)$ の構造、解が必ず存在する範囲(鳩の巣原理による主定理)、SIS の解で LWE を見分けられること、LLL アルゴリズムで解ける範囲、最悪の場合からの帰着の核になる補題を証明する。帰着の定理そのものは証明しない。
$q\ge2$ を整数とし、$\mathbb{Z}_q=\mathbb{Z}/q\mathbb{Z}$ と書く(剰余環)。$x\in\mathbb{Z}_q$ を表す整数のうち絶対値が最小のものの絶対値を $\lvert x\rvert_q$ と書く。$\lvert x+y\rvert_q\le\lvert x\rvert_q+\lvert y\rvert_q$ で、整数 $c$ について $\lvert cx\rvert_q\le\lvert c\rvert\,\lvert x\rvert_q$ である。$z\in\mathbb{Z}^m$ のノルムは $\|z\|=(\sum z_i^2)^{1/2}$、$\|z\|_\infty=\max_i\lvert z_i\rvert$、$\|z\|_1=\sum_i\lvert z_i\rvert$ とし、$\|z\|_\infty\le\|z\|\le\sqrt m\,\|z\|_\infty$、$\|z\|_1\le\sqrt m\,\|z\|$ を使う。
整数 $n,m\ge1$、$q\ge2$ と $\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}$ という。$\|z\|$ を $\|z\|_\infty$ に替えた問題を $\mathrm{SIS}^\infty_{n,q,\beta,m}$ と書く。$u\in\mathbb{Z}_q^n$ も一様な乱数で与え、$Az\equiv u$、$\|z\|\le\beta$ をみたす $z$ を求める問題を 非斉次 SIS(ISIS)という。
$\mathrm{SIS}_{n,q,\beta,m}$ の定義そのものは 格子暗号 の記事にもある。この記事では解の集合を格子として調べる。
$n\times m$ 行列 $A$(成分は $\mathbb{Z}_q$)と $u\in\mathbb{Z}_q^n$ について
$$
\Lambda^\perp(A)=\{z\in\mathbb{Z}^m:Az\equiv0\pmod q\},\qquad \Lambda^\perp_u(A)=\{z\in\mathbb{Z}^m:Az\equiv u\pmod q\}
$$
とおく。$\Lambda^\perp(A)$ は $\mathbb{Z}^m$ の部分群で、$\Lambda^\perp_u(A)$ は空でなければ 1 つの解 $c$ を使って $c+\Lambda^\perp(A)$ と書ける。
SIS は「$\Lambda^\perp(A)$ の $0$ でない点で長さ $\beta$ 以下のものを 1 つ求めよ」という問題であり、ISIS は「剰余類 $\Lambda^\perp_u(A)$ の短い点を求めよ」という問題である。
この記事の主張が使える条件をまとめる。
$A$ は $\mathbb{Z}_q$ 成分の $n\times m$ 行列、$d$ は格子 $\Lambda^\perp(A)$ の行列式(格子(群) の covol)とする。
| 主張 | 条件 | 結論 | 根拠 |
|---|---|---|---|
| 格子の挟み込み | なし | $q\mathbb{Z}^m\subset\Lambda^\perp(A)\subset\mathbb{Z}^m$、階数 $m$ | prop-sis-lattice |
| 行列式 | なし | $d=\lvert A\mathbb{Z}^m\bmod q\rvert\le q^n$ | prop-sis-lattice |
| 行列式が $q^n$ | 列が $\mathbb{Z}_q^n$ を生成 | $d=q^n$ | prop-sis-lattice |
| 生成しない確率 | $q$ が素数、$A$ が一様 | $2q^{n-m-1}$ 以下 | prop-sis-lattice |
| 正規形 | $A=[A_1\mid A_2]$、$A_1$ が可逆 | $\Lambda^\perp(A)=\Lambda^\perp([I_n\mid A_1^{-1}A_2])$ | prop-sis-lattice |
| 解の存在(主定理) | $(t+1)^m>q^n$ | $\|z\|_\infty\le t$ の $0$ でない解がある | thm-sis-exist |
| 最短の解の長さ | なし | $\lambda_1(\Lambda^\perp(A))\le\sqrt m\,q^{n/m}$ | thm-sis-exist |
| LWE の判定 | $q$ が素数、$z\not\equiv0$、$\lvert e_i\rvert_q\le r$、$2r\|z\|_1< q$ | 優位度 $\ge1-\frac{2r\|z\|_1+1}q$ | thm-sis-lwe |
| LLL で解ける範囲 | 正規形にできる | $\beta\ge2^{(m-1)/4}q^{n/m}$ なら多項式時間 | cor-sis-lll |
| 帰着の核 | $v_i\in L$、$A=B^{-1}V\bmod q$、$Az\equiv0$ | $Vz/q\in L$、長さ $\le\sqrt m\,\beta\max_i\|v_i\|/q$ | lem-sis-core |
| 最悪の場合からの帰着 | $m=\mathrm{poly}(n)$、$q\ge\beta\cdot\mathrm{poly}(n)$ | SIS は GapSVP$_\gamma$・SIVP$_\gamma$ より易しくない | 証明しない:Pei16 Theorem 4.1.2(p. 20) |
$A$ を $\mathbb{Z}_q$ 成分の $n\times m$ 行列とする。
1. $\varphi:\mathbb{Z}^m\to\mathbb{Z}_q^n$、$\varphi(z)=Az\bmod q$ は群の準同型で、$\Lambda^\perp(A)=\ker\varphi$ である。$z\in q\mathbb{Z}^m$ なら $Az\equiv0$ なので $q\mathbb{Z}^m\subset\ker\varphi$。$\ker\varphi$ は $\mathbb{Z}^m$ の部分群なので離散で、$\mathbb{R}^m$ を張る $q\mathbb{Z}^m$ を含むので階数 $m$ の格子である。
2. 準同型定理から $\mathbb{Z}^m/\ker\varphi\cong\operatorname{im}\varphi=A\mathbb{Z}^m$ で、指数は $\lvert A\mathbb{Z}^m\rvert\le\lvert\mathbb{Z}_q^n\rvert=q^n$ である。格子(群) の定理「部分格子の指数と体積」により、$\Lambda^\perp(A)$ の covol は $\mathbb{Z}^m$ の covol $1$ の $[\mathbb{Z}^m:\Lambda^\perp(A)]$ 倍で、$d=\lvert A\mathbb{Z}^m\rvert$ である。$A\mathbb{Z}^m$ は列の生成する部分群なので、等号の条件も分かる。
3. $q$ が素数なら $\mathbb{Z}_q$ は体で、列が $\mathbb{Z}_q^n$ を生成しないことは、$A$ の階数が $n$ 未満、つまり $y^{\mathsf T}A=0$ となる $0$ でない $y\in\mathbb{Z}_q^n$ があることと同じである。$y\ne0$ を固定すると、一様な列 $a_j$ について $y\cdot a_j$ は $\mathbb{Z}_q$ で一様なので、$\Pr[y^{\mathsf T}A=0]=q^{-m}$ である。$y$ とその $0$ でない定数倍は同じ条件を与えるので、$y$ は $(q^n-1)/(q-1)$ 個の代表を動かせば足りる。和をとって
$$
\Pr[\text{生成しない}]\le\frac{q^n-1}{q-1}\,q^{-m}\le\frac{q^{n}}{q-1}q^{-m}\le2q^{n-m-1}
$$
(最後は $q\ge2$ から $\frac q{q-1}\le2$)。
4. $A_1$ が可逆なら、$Az\equiv0$ と $A_1^{-1}Az=[I_n\mid\bar A]z\equiv0$ は同値である。$z=(x,y)$($x\in\mathbb{Z}^n$、$y\in\mathbb{Z}^{m-n}$)と書くと、条件は $x\equiv-\bar Ay\pmod q$、すなわちある $w\in\mathbb{Z}^n$ で $x=-\bar Ay+qw$ と書けることである。これは $z$ が上の行列と整数ベクトル $(w,y)$ の積であることと同じで、列は $\Lambda^\perp$ を生成する。行列はブロック上三角で行列式 $q^n\ne0$ なので、列は 1 次独立である。$\square$
4 の基底の行列式 $q^n$ は 2 の $d=q^n$ と一致する($[I_n\mid\bar A]$ の列は $\mathbb{Z}_q^n$ を生成する)。$\bar A=A_1^{-1}A_2$ は、$A_2$ が一様で $A_1$ と独立なので一様な乱数である(Pei16 p. 19)。したがって、一様な $A$ の SIS を解くには、一様な $\bar A$ について正規形 $[I_n\mid\bar A]$ の SIS を解けば足りる。
$A$ を $\mathbb{Z}_q$ 成分の $n\times m$ 行列、$t\ge1$ を整数とする。$(t+1)^m>q^n$ なら、$Az\equiv0\pmod q$、$z\ne0$、$\|z\|_\infty\le t$ をみたす $z\in\mathbb{Z}^m$ が存在する。とくに $t=\lfloor q^{n/m}\rfloor$ ととれば
$$
\lambda_1(\Lambda^\perp(A))\le\sqrt m\,\lfloor q^{n/m}\rfloor\le\sqrt m\,q^{n/m}
$$
で、$\beta\ge\sqrt m\,q^{n/m}$ の $\mathrm{SIS}_{n,q,\beta,m}$ と $\beta\ge q^{n/m}$ の $\mathrm{SIS}^\infty_{n,q,\beta,m}$ は、どの $A$ についても解をもつ。
箱 $X=\{0,1,\dots,t\}^m$ の点は $(t+1)^m$ 個あり、写像 $x\mapsto Ax\bmod q$ の値は $\mathbb{Z}_q^n$ の $q^n$ 個のどれかである。$(t+1)^m>q^n$ なので、鳩の巣原理 により $Ax\equiv Ax'$ となる $x\ne x'$($x,x'\in X$)がある。$z=x-x'$ とおくと $z\ne0$、$Az\equiv Ax-Ax'\equiv0$ で、各成分は $-t\le x_i-x'_i\le t$ をみたすので $\|z\|_\infty\le t$ である。
$t=\lfloor q^{n/m}\rfloor$ なら $t+1>q^{n/m}$ なので $(t+1)^m>q^n$ であり、$q\ge2$、$n\ge1$ から $q^{n/m}>1$ で $t\ge1$ である。得られた $z$ は $\|z\|\le\sqrt m\,\|z\|_\infty\le\sqrt m\,t$ をみたす。$\square$
$t=1$ の場合は、格子暗号 の記事の命題「衝突から SIS の解へ」($m>n\log_2q$ なら $\{0,1\}^m$ 上の $x\mapsto Ax$ に衝突があり、差が長さ $\sqrt m$ 以下の解になる)にあたる。thm-sis-exist は箱の大きさ $t$ を動かして、$m$ が小さいときにも解の長さを評価する。
同じ評価は Minkowskiの格子点定理 からも出る。$\Lambda^\perp(A)$ の行列式は $q^n$ 以下なので、中心対称な閉じた立方体 $[-q^{n/m},q^{n/m}]^m$ は体積が $2^mq^n$ 以上なので、Minkowskiの格子点定理 の系「有界な閉集合の場合」を線形変換で一般の格子に移した形により、$0$ でない格子の点を含む。鳩の巣原理の証明は、その点を「箱の中の 2 点の差」として具体的に作る。
thm-sis-exist の証明は $(t+1)^m$ 個の点を調べるので、指数関数的な時間がかかる。$\beta$ が $\sqrt m\,q^{n/m}$ の多項式倍程度で $q\ge\beta\cdot\mathrm{poly}(n)$ のとき、解は必ず存在する。一方、そのような SIS を多項式時間で解く方法があれば、thm-sis-ajtai により任意の格子の GapSVP$_\gamma$・SIVP$_\gamma$ が多項式の近似比 $\gamma$ で解けることになるが、そのようなアルゴリズムは 2016 年 2 月の時点で知られていなかった(Pei16 p. 8)。これが SIS が暗号に使われる理由である。
格子暗号 の記事の誤差つき学習問題(LWE)では、一様な $A$ と一様な $s\in\mathbb{Z}_q^n$、小さい誤差 $e\in\mathbb{Z}^m$ から $b=A^{\mathsf T}s+e\bmod q$ を作る($A$ の列 $a_i$ と $b_i=a_i\cdot s+e_i$ の組が標本)。判定版は、$(A,b)$ がこの形か、$b$ が一様な乱数かを見分ける問題である。同じ $A$ について SIS の解が分かると、判定版が解ける。
$q$ を素数、$r\ge1$ を整数とし、$A$ を $\mathbb{Z}_q$ 成分の $n\times m$ 行列とする。$z\in\mathbb{Z}^m$ が $Az\equiv0$、$z\not\equiv0\pmod q$ をみたし、$T=r\|z\|_1$ が $2T< q$ をみたすとする。$b\in\mathbb{Z}_q^m$ について、$\lvert b\cdot z\rvert_q\le T$ なら $1$、そうでなければ $0$ を出力する判定を $D(b)$ とする。
1. $b=A^{\mathsf T}s+e$ なら
$$
b\cdot z=s^{\mathsf T}Az+e\cdot z\equiv e\cdot z\pmod q
$$
である($Az\equiv0$)。$\lvert\cdot\rvert_q$ の三角不等式と $\lvert cx\rvert_q\le\lvert c\rvert\,\lvert x\rvert_q$ から $\lvert e\cdot z\rvert_q\le\sum_i\lvert z_i\rvert\,\lvert e_i\rvert_q\le r\|z\|_1=T$ で、$D(b)=1$ である。
2. $z\not\equiv0$ なので、ある $k$ で $z_k\not\equiv0\pmod q$ であり、$q$ が素数なので $z_k$ は $\mathbb{Z}_q$ で可逆である。$b_k$ 以外の成分を固定すると、$b_k$ が一様なので $z_kb_k$ も一様で、$b\cdot z=z_kb_k+\sum_{i\ne k}z_ib_i$ は $\mathbb{Z}_q$ で一様である。$\lvert v\rvert_q\le T$ をみたす $v\in\mathbb{Z}_q$ は $-T,\dots,T$ の剰余で、$2T< q$ なのでこれらは相異なり $2T+1$ 個ある。よって確率は $\frac{2T+1}q$ である。
後半. $W$ が成功する確率を $\varepsilon'\ge\varepsilon$ とする。LWE の側では 1 により、$W$ が成功しても失敗しても出力は $1$ である。一様な側では $b$ は $A$ と独立なので、$W$ の出力 $z$ とも独立である。$z$ は $\|z\|\le\beta< q$ なので $z\not\equiv0$ で、$T=r\|z\|_1\le r\sqrt m\,\beta$ は $2T< q$ をみたす。2 により成功したときに $1$ を出力する確率は $\frac{2r\sqrt m\,\beta+1}q$ 以下で、
$$
\Pr[1\text{ を出力}]\le(1-\varepsilon')+\varepsilon'\,\frac{2r\sqrt m\,\beta+1}q
$$
となる。優位度は $1$ からこれを引いたもので、$\varepsilon'\bigl(1-\frac{2r\sqrt m\,\beta+1}q\bigr)\ge\varepsilon\bigl(1-\frac{2r\sqrt m\,\beta+1}q\bigr)$ 以上である。$\square$
誤差が有界でない分布(離散化した正規分布など)のときは、$\lvert e\cdot z\rvert_q\le T$ が確率的にしか成り立たないので評価が変わる。この記事では有界な誤差の場合だけを扱う。
小さい SIS を LLL アルゴリズムで解く手順をまとめる。$q$ は素数とする。
$A=[A_1\mid A_2]$ で $A_1$ が $\mathbb{Z}_q$ 上可逆とする。$\beta\ge2^{(m-1)/4}q^{n/m}$ なら、上の手順は $\mathrm{SIS}_{n,q,\beta,m}$ の解を返し、算術演算の回数は $O(m^4\log(nq))$ である。
prop-sis-lattice の 2 と 4 により、手順 2 の基底は行列式 $q^n$ の格子 $\Lambda^\perp(A)$ の基底である。LLLアルゴリズム の定理「簡約基底の性質」の 3 により、$b_1\ne0$ は $\|b_1\|\le2^{(m-1)/4}(q^n)^{1/m}\le\beta$ をみたす。基底のベクトルは整数で長さの 2 乗が $1+nq^2\le(n+1)q^2$ 以下なので、同じ記事の定理「停止と多項式時間」により算術演算の回数は $O(m^4\log((n+1)q^2))=O(m^4\log(nq))$ である。手順 1 の消去法は $O(n^2m)$ 回の演算で済む。$\square$
$m=6$ では $2^{(m-1)/4}\approx2.38$ で、thm-sis-exist の $\sqrt m\approx2.45$ とほぼ同じなので、LLL で存在範囲のほぼ全体が解ける(ex-sis-lll)。暗号では $m$ を数百以上にとるので、$2^{(m-1)/4}$ は $\sqrt m$ よりはるかに大きく、LLL は存在範囲の SIS を解けない。
Ajtai の帰着は、任意の格子 $L$ の短いベクトルを、SIS を解く手続きを繰り返し呼んで作る。その核になるのが次の補題である(Pei16 pp. 21–22 の「core step」を証明つきで述べたもの)。
$L\subset\mathbb{R}^n$ を基底行列 $B$(列が基底、$n\times n$)の格子とし、$v_1,\dots,v_m\in L$ を列とする行列を $V$ とする。$B^{-1}V$ は整数行列で、$A=B^{-1}V\bmod q$ とおく。$z\in\mathbb{Z}^m$ が $Az\equiv0\pmod q$、$\|z\|\le\beta$ をみたすなら、$v=Vz/q$ は $L$ の点で
$$
\|v\|\le\frac{\sqrt m\,\beta}{q}\max_i\|v_i\|
$$
である。
$v_i\in L$ なので $v_i=Bc_i$($c_i\in\mathbb{Z}^n$)と書け、$C=B^{-1}V$ は $c_i$ を列とする整数行列である。$C\equiv A$ なので $Cz\equiv Az\equiv0\pmod q$ で、$Cz=qy$($y\in\mathbb{Z}^n$)と書ける。すると $Vz=BCz=qBy$ で、$v=Vz/q=By\in L$ である。長さは三角不等式と $\|z\|_1\le\sqrt m\,\|z\|$ から
$$
\|Vz\|\le\sum_i\lvert z_i\rvert\,\|v_i\|\le\|z\|_1\max_i\|v_i\|\le\sqrt m\,\beta\max_i\|v_i\|
$$
で、$q$ で割ればよい。$\square$
$q\ge2\sqrt m\,\beta$ なら、新しい点 $v$ は手持ちの点 $v_i$ の最大の長さの半分以下になる。これを繰り返して格子の短いベクトルを作るのが帰着の骨組みである。ただし、$A$ がほぼ一様な乱数になるように $v_i$ を選ぶこと、得られる $v$ が $0$ ばかりにならないことの証明には、格子上の離散的な正規分布と平滑化パラメータが要る(Pei16 pp. 21–22)。この記事ではその部分を証明しない。
任意の $m=\mathrm{poly}(n)$ と $\beta>0$、十分大きい $q\ge\beta\cdot\mathrm{poly}(n)$ について、$\mathrm{SIS}_{n,q,\beta,m}$ を無視できない確率で解くことは、任意の $n$ 次元の格子で GapSVP$_\gamma$ と SIVP$_\gamma$ を圧倒的な確率で解くことより易しくない。ここで $\gamma=\beta\cdot\mathrm{poly}(n)$ である。
この定理は証明しない(Pei16 Theorem 4.1.2、p. 20)。GapSVP$_\gamma$・SIVP$_\gamma$ の定義は 格子暗号 の記事にある。最初の形は 1996 年の Ajtai によるもので、$q$ と $\gamma$ の多項式は大きかった。2004 年の Micciancio–Regev は $\gamma=\beta\cdot\tilde O(\sqrt n)$ を、2013 年の Micciancio–Peikert は任意の定数 $\varepsilon>0$ について $q\ge\beta\cdot n^\varepsilon$ を得た(Pei16 p. 20)。
$q=13$、$n=1$、$m=2$、$A=(1,5)$ とする。使う公式:prop-sis-lattice、thm-sis-exist。答え:$\Lambda^\perp(A)$ は行列式 $13$ の格子で、最短の解は $\pm(3,2)$、$\pm(-2,3)$(長さ $\sqrt{13}\approx3.61$)。鳩の巣原理の保証は $\|z\|_\infty\le3$、$\|z\|\le\sqrt2\cdot3\approx4.24$ である。
正規形の基底は $(13,0)$、$(-5,1)$ で行列式 $13$。$t=\lfloor\sqrt{13}\rfloor=3$ で $(t+1)^2=16>13$。箱 $\{0,1,2,3\}^2$ の 16 点の値 $x_1+5x_2\bmod13$ には衝突が 4 組あり、たとえば $(3,2)$ と $(0,0)$ はどちらも値 $0$ で、差 $(3,2)$ が解である($3+10=13$)。$\lvert z_i\rvert\le13$ の全数え上げで、長さの 2 乗の最小は $13$。基底 $(13,0)$、$(-5,1)$ に LLL アルゴリズムを使うと、2 回の入れ替えで $(-2,3)$、$(-3,-2)$ になる(途中で現れる $\mu_{21}=-\frac52$ を $-3$ に丸めた場合。$-2$ に丸めると $(3,2)$、$(-2,3)$ になる)。
図: q=13、A=(1,5) の解の格子。灰色の点は z1+5z2 が 13 の倍数になる整数点で、黒い四角は自明な解 13Z² の点。赤い矢印は最短の解 (3,2) と (-2,3)。破線の正方形は鳩の巣原理が保証する範囲 max|zi| ≤ 3、点線の円は半径 √13。
$q=7$、$A=(2,3)$ とする。使う公式:prop-sis-lattice の 4。答え:$A_1=2$ の逆元は $4$ なので $\bar A=4\cdot3\equiv5$、正規形は $[1\mid5]$ で基底は $(7,0)$、$(-5,1)$。解の集合は $A$ と同じで、最短の解は $\pm(-2,-1)$($2\cdot(-2)+3\cdot(-1)=-7$、$-2-5=-7$)。
$q=31$、$n=2$、$m=6$、$A=[I_2\mid\bar A]$、
$$
\bar A=\begin{pmatrix}3&17&25&8\\22&9&14&30\end{pmatrix}
$$
とする。使う公式:cor-sis-lll。答え:LLL アルゴリズムの $b_1=(0,2,1,-1,-1,1)$ は $Ab_1\equiv0$、$\|b_1\|=2\sqrt2\approx2.83$ で、$\beta=2^{5/4}\cdot31^{1/3}\approx7.47$ の SIS の解である。これは最短の解でもある。
基底は $31e_1$、$31e_2$ と $(-3,-22,1,0,0,0)$、$(-17,-9,0,1,0,0)$、$(-25,-14,0,0,1,0)$、$(-8,-30,0,0,0,1)$ で、行列式 $31^2=961$。入れ替えは 20 回。$Ab_1$ の第 1 成分は $3-17-25+8=-31$、第 2 成分は $2+22-9-14+30=31$。長さの 2 乗が $8$ 未満の整数ベクトルは成分の絶対値が $2$ 以下なので、$\{-3,\dots,3\}^6$ の全数え上げで最短が $8$ と分かる。thm-sis-exist の保証は $t=\lfloor31^{1/3}\rfloor=3$、$\|z\|\le\sqrt6\cdot3\approx7.35$。成分が $0,\pm1$ だけの解はない。
ex-sis-lll の $A$ と $z=b_1$、誤差 $\lvert e_i\rvert\le1$($r=1$)とする。使う公式:thm-sis-lwe。答え:$T=\|z\|_1=6$ で、$2T=12< 31$。一様な $b$ を誤って $1$ と判定する確率は $\frac{13}{31}$、優位度は $\frac{18}{31}\approx0.58$ 以上である。
$s=(7,19)$、$e=(1,0,-1,1,0,-1)$ なら $b=A^{\mathsf T}s+e\equiv(8,19,4,12,7,5)$ で、$b\cdot z\equiv28\equiv-3$($=e\cdot z$)、$\lvert-3\rvert_{31}=3\le6$ なので $1$。一様な乱数の例 $b'=(5,12,0,27,3,19)$ では $b'\cdot z\equiv13$、$13>6$ なので $0$。$s=(7,19)$ で $e\in\{-1,0,1\}^6$ の $729$ 通りすべてについて判定は $1$ になる。
| 主張 | 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|---|
| thm-sis-exist | $(t+1)^m>q^n$ | $q=11$、$n=m=1$、$A=(3)$、$t=3$:$(t+1)^m=4\le11$ | $\Lambda^\perp(A)=11\mathbb{Z}$ で、$\lvert z\rvert\le3$ の $0$ でない解がない。結論が成り立たない |
| prop-sis-lattice の 2 の等号 | 列が $\mathbb{Z}_q^n$ を生成 | $q=7$、$A$ の行が $(1,2)$ と $(2,4)$ | 像は $(1,2)$ の倍数の $7$ 個で、行列式は $7< 49$。等式 $d=q^n$ が成り立たない |
| thm-sis-lwe の 2 | $q$ が素数 | $q=9$、$n=m=1$、$A=(3)$、$z=(3)$、$r=1$($T=3$、$2T=6< 9$) | 一様な $b$ でも $b\cdot z=3b\in\{0,3,6\}$ で $\lvert b\cdot z\rvert_9\le3$ がいつも成り立ち、確率は $1\ne\frac79$。優位度は $0$ で、$\frac29$ 以上という結論が成り立たない |
| thm-sis-lwe | $z\not\equiv0\pmod q$ | $z=0$($T=0$ で $2T< q$ はみたす) | $b\cdot z=0$ で判定はいつも $1$。2 の確率は $1\ne\frac1q$、優位度は $0$ で、下界 $1-\frac1q$ が成り立たない |
| thm-sis-lwe | $2T< q$ | $2T\ge q$ | $\lvert\cdot\rvert_q\le\frac q2\le T$ なので判定はいつも $1$ で、2 の確率は $1$ となり $\frac{2T+1}q>1$ と食い違う。優位度は $0$ だが、下界 $1-\frac{2T+1}q$ は負なので優位度の評価そのものは成り立つ |
| SIS が意味をもつ | $\beta< q$ | $\beta\ge q$ | $(q,0,\dots,0)$ がいつも解で、問題が自明になる |
1 行目:$3z\equiv0\pmod{11}$ と $z\equiv0\pmod{11}$ は同値($3$ は可逆)。2 行目:基底 $(7,0)$、$(-2,1)$ の行列式は $7$ で、$0\le z_i< 70$ の解は全体の $\frac17$。3 行目:$z=(3)$ は $Az=9\equiv0$、$z\not\equiv0\pmod9$ をみたすが、$3$ は $\mathbb{Z}_9$ で可逆でないので $b\cdot z$ は一様にならない。LWE の側でも $b=3s+e$、$b\cdot z\equiv3e$ でいつも $1$ なので、2 つの側の判定の分布は同じである。4・5 行目は定義から直ちに分かる。
| 誤り | 正しくは | なぜ |
|---|---|---|
| SIS は $\beta$ が大きいほど難しい | $\beta$ が大きいほどやさしく、$\beta\ge q$ なら自明 | 条件 $\|z\|\le\beta$ が緩むから |
| $m$ を増やすと難しくなる | $m$ を増やすとやさしくなり、$n$ を増やすと難しくなる | 余分な列には $0$ を当てればよい(Pei16 p. 19) |
| 解が存在するなら簡単に見つかる | 存在は鳩の巣原理で保証されるが、探索は指数時間 | rem-sis-exist |
| 行列式はいつも $q^n$ | $\lvert A\mathbb{Z}^m\rvert$ で、$q^n$ 以下 | prop-sis-lattice、反例の表の 2 行目 |
| LLL は SIS を解くので SIS は易しい | LLL が解けるのは $\beta\ge2^{(m-1)/4}q^{n/m}$ の範囲 | cor-sis-lll |
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する