数理解析研究所講究録
第 1815 巻 2012 年 79-89

79

多変数多項式環を用いた NTRU 暗号の拡張
小柴薫居
MASAORI KOSHIBA

東京理科大学大学院理学研究科数理情報科学専攻
DEPARTMENT OF MATHEMATICAL INFORMATION SCIENCE,GRADUATE SCHOOL OF SCIENCE,
TOKYO UNIVERSITY OF SCIENCE
井上秀太郎
SHUTARO INOUE

東京理科大学理学部数理情報科学科
DEPARTMENT OF MATHEMATICAL INFORMATION SCIENCE,

TOKYO UNIVERSITY OF SCIENCE
和田雅美
MASAMI WADA

東京理科大学理学部数理情報科学科
DEPARTMENT OF MATHEMATICAL INFORMATION SCIENCE,

TOKYO UNIVERSITY OF SCIENCE森田昌宏
MASAHIRO MORITA

東京理科大学理学部数理情報科学科
DEPARTMENT OF MATHEMATICAL INFORMATION SCIENCE,

TOKYO UNIVERSITY OF SCIENCE
Abstract
NTRU[1] は CRYPTO 96 で発表された公開鍵暗号で，1 変数多項式環上に構成されたものである．既存の暗号に対して暗号化にかかる計算量が少ないことが知られている．NTRU に対する攻撃方法として総当たり攻撃や Lattice Attack[2] が知られている．本研究では NTRU を 1 変数多項式環から多変数多項式環に拡張し，新しい公開鍵暗号化方式 (MTRU) を構築した．また Risa$/Asir$ を用いて NTRU と MTRUを実装し実行時間，安全性を比較した．

80
1

はじめに
NTRU[ ] ( -th Degree Truncated Polynomial Ring) は 1 変数多項式環上で構成された公開鍵暗号であ$N$$I$る．暗号化に必要な計算量は $O(N^{2})(FFT$ を用いれば $O(N\log N))$ である．RSA は暗号化に$O(N^{3})$かかるので RSA より早いとされている．派生系として CTRU, MaTRU, $GB$ -TRU などが提案されている．またNTRUSign[3] として NTRU 格子を用いたデジタル署名方式も提案されている．
$H$
NTRU における暗号化関数 は， を自然数， $q(p<q)$ を素数，を公開鍵， をランダムな多項式，を Zq[x]/月こおける積として以下で表される．
$f$

$n$

$f$

:

$R$

$p,$

$Z_{p}[x]/(x^{n}-1)$$arrow$$*$$Z_{q}[x]/(x^{n}-1)$

($V$

$l11$

$M \mapsto pH*R+M$
NTRU に対する攻撃方法として総当たり攻撃や Meet-In-The-Middle Attack, Lattice Attack[2] が知られている．NTRU においてこれらの攻撃に対する安全性を高めるためには次数 を上げる他に方法はない．
本研究では NTRU を 1 変数多項式環から多変数多項式環に拡張し，新しい公開鍵暗号化方式を構築した．これを MTRU(Multivariable Truncated Polynomial Ring) と呼ぶこととする．さらに数式処理システ
ム $Risa/Asir$ を用いて NTRU と MTRU をそれぞれ実装し，実行時間，安全性を比較検討した．の生を$m$ を自然数， $q(p<q)$ を素数，MTRU における暗号化関数 は，をイデアル，$n$$f$

成元， を公開鍵，$H$$R_{1},$$\cdots,$$R_{m}$$f$:$P,$ $Q$$p,$をランダムな多項式， を$\circ$$Z_{p}[x_{1}, \cdots, x_{m}]/P$$P_{1},$$\cdots,$$P$$P_{m}$における積として以下で表す．

$Z_{q}[x_{1}, \cdots , x_{m}]/Q$$Z_{q}[x_{1}, \cdots, x_{m}]/Q$$arrow$$(V \backslash \perp)$$M \mapsto H$
MTRU では多変数多項式環を用いることにより，イデアル $P$ の生成元の次数を大きくするだけでなく，変数 $m$ を増やすことにより安全性を高めることが可能である．また NTRU では平文の集合と暗号文の集合は係数体が異なるだけであったが，MTRU では法となるイデアルも異なるものとした．このことにより暗号化関数にランダムな多項式が増え，暗号文への総当たり攻撃に対する安全性が向上した．

NTRU

2

本章では NTRU についてまとめる．以降，本章では 1 変数多項式環 $R$ をとし，剰余環 $R/I$ の元である$n$$\mathbb{Z}[x]$, イデアル$I$を$\langle x^{n}-1\rangle\subset \mathbb{Z}[x]$次多項式 $F$ を以下で表記する．
$F= \sum_{i=0}^{n}F_{i}x^{i}$

係数$F_{0},$2.1$p,$ $q$$\cdots$,$F_{n}$のうち$d_{1}$個が 1,$d_{2}$個が $-1$ , 残りが$0$である多項式の集合を$\mathcal{L}(d_{1}, d_{2})\subset R/I$とする．

鍵生成$n/2$ 未満の自然数
を $p\ll q$ なる互いに異なる自然数とする．

上で逆元$F_{p}^{-1},$ $F_{q}^{-1}$をもつ多項式 $F\in \mathcal{L}(d_{L}, d_{L}-1)$を決定する．
は十分存在するので，これを決定する．

$F*F_{p}^{-1}\equiv 1 (mod p)(mod I)$$F*F_{q}^{-1}\equiv 1 (mod q)(mod I)$$d_{L},$ $d_{G}$$\mathbb{Z}_{p}[x]/I$と$\mathbb{Z}_{q}[x]/I$

81
次に $G\in \mathcal{L}(d_{G}, d_{G})$ をランダムに選ぶ．この $G$ と$F_{q}^{-1}$から $H$ を生成する．

$H\equiv G*F_{q}^{-1} (mod q)(mod I)$

公開鍵を $\{p, q, H, I\}$ , 秘密鍵を

2.2$\{F, F_{p}^{-1}\}$とする．

暗号化

平文を $M\in \mathbb{Z}_{p}[x]/I$ とする．

$R\in \mathcal{L}(d_{R}, d_{R})\}$($d_{R}$は $n/2$ 未満の自然数)

をランダムに選び，以下の式で暗号文 $C$ を生成する．
$C\equiv p\cdot H*R+M (mod q)(mod I)$

2.3

復号

暗号文 $C$ に対し，秘密鍵 $F$ によって $A$ を求め$A\equiv C*F (mod q)(mod I)$$F$の $Z_{p}[x]/I$ における逆元$F_{p}^{-1}$によって復号文 $M’$ を求める．
$M’\equiv A*F_{p}^{-1} (mod p)(mod I)$

2.4

復号条件

$\ovalbox{\tt\small REJECT}\backslash ^{o_{\overline{7}}}$

メータ $p,$ $q,$$d_{L},$ $d_{G},$ $d_{R}$の取り方と，平文の係数等によっては復号できない場合がある．

定理 1(復号条件)$|F|_{\infty}$

を次のように定義し$|F|_{\infty} \equiv_{0}\max_{\leq i\leq n}\{F_{i}\}-\min_{0\leq i\leq n}\{F_{i}\}$

復号文が平文に一致するための必要条件は以下である．
$|p\cdot G*R+F*M|_{\infty}\leq q$

証明

復号過程において$A\equiv C*F (mod q)(mod I)$$\equiv p\cdot F*H*R+F*M (mod q)(mod I)$$\equiv p\cdot F*F_{q}^{-1}*G*R+F*M (mod q)(mod I)$$\equiv p\cdot G*R+F*M (mod q)(mod I)$$R/I$ 上でである．ここで $|p\cdot G*R+F*M|_{\infty}\leq q$ ならば，

$A=p\cdot G*R+F*M$

82である．よって，$M’\equiv A*F_{p}^{-1} (mod p)(mod I)$$\equiv p\cdot F_{p}^{-1}*G*R+F_{p}^{-1}*F*M (mod p)(mod I)$$\equiv M (mod p)(mod I)$であるので復号文は平文と一致する．口

3MTRU

3.1

準備

記号の定義を以下とする．
$\overline{x}:=x_{1}, \cdots, x_{m}$

$k$

:体

$R:=k[x_{1}, \cdots, x_{m}]$$I:=\langle f_{1}, \cdots, f_{s}|f_{i}\in R\rangle$$\sqrt{I};=\{f|\exists n, f^{n}\in I\}$$V$( ) $:=\{(a_{1}, \cdots, a_{n})\in k^{n}|\forall f\in I, f(a_{1}, \cdots, a_{m})=0\}$$I$$V:=$ 多様体
$I$

( $V$ ) $:=\{f\in R|\forall x\in V, f(x)=0\}$$LT(f)$ $:=f$ の先頭項

multideg $(f)$ : $f$ の多重次数$\mathcal{L}_{I}(d_{1}, d_{2})$$:=${係数のうち$d_{1}$個が 1,$d_{2}$個が $-1$ , 残りが$0$である $R/I$ の元}$\dim(X)$ : 線形空間 $X$ の次元定理 2剰余環 $R/I$ の元 $f$ の逆元 $f^{-1}$ が存在することの必要十分条件は以下である． を$z$する．単項式順序を $z>x_{1}>\cdots>x_{n}$ の辞書式順序とする．このときイデアル$k[\overline{x}, z]$の簡約グレブナ基底 $G$ に先頭項が$z$$x_{1},$$\cdots,$ $x_{n}$と異なる変数と$J=\langle f*z-1,$ $fi,$ $\cdots,$$f_{s}\rangle\subset$となる多項式が含まれる．

この多項式を $z-h$ とすると $h=f^{-1}$ である．
証明

$V(J)=V(G)$ であるから $z-h=0$ より(必要性の証明) の簡約グレブナ基底に $z-h$ が含まれるとき，$z=h$ , これを $f*z-1=0$ に代入して $f*h=1$ であるから $f$ の逆元は存在し $h=f^{-1}$ である．
(十分性の証明) の簡約グレブナ基底を $G=\{g_{1}, \cdots, g_{u}\}$ とすると
$J$

$J$

$\langle LT(J)\rangle=\langle LT(g_{1}), \cdots , LT(g_{u})\rangle$である．よって，ある$i$により $LT(f*z-1)$ を $LT(g_{i})$ が割り切る．

$I$ は $J$ から
以下 $LT(f)$ が $I$ の簡約グレブナ基底で簡約できないことから $LT(g_{i})=z$ を示す．

たイデァルだから消去定理より $G_{z}=G\cap k[\overline{x}]$ は$J$の簡約グレブナ基底である．

$z$を消去し83$f\in R/I$ であるので，$LT(f)<\min\{LT(g)|g\in G_{z}\}$

よって変数順序を $z>x_{1}>\cdots>x_{n}$ とし，単項式順序を辞書式順序としているので $LT(f)$ は $LT(g_{i})$ で割れない．よって $LT(g_{i})=z$ に他ならないので示された$\square$系3

定理 2 と同じ条件の元で，剰余環 $R/I$ の元$f$の逆元声 1 が存在することの必要十分条件は以下である．

$\langle g_{1}, \cdots, g_{u}, f\rangle=\{1\}$証明

逆元 $f$ が存在するならば，(mod )$f*f^{-1}\equiv 1$$I$$\Leftrightarrow f*f^{-1}=a_{1}*g_{1}+\cdots+a_{u}*g_{u}+1$$\Leftrightarrow f*f^{-1}-a_{1}*g_{1}-\cdots-a_{u}*g_{u}=1$$\Leftrightarrow 1\in\langle g_{1}, \cdots, g_{u}, f\rangle$

よって$\langle g_{1},$逆に$\langle g_{1},$$\cdots,$ $g_{u},$$\cdots,$$g_{u},$$f\rangle=\{1\}.$$f\rangle=\{1\}$ならば $f*h\equiv 1(mod I)$ なる元が存在し，これは逆元に他ならないので示された．口

3.2

鍵生成変数の数 m, 互いに異なる自然数 $p,$ $q(p\ll q),$ては 3.6 にて詳しく述べる．

$l_{p},$$l_{q}$$2$

つのグレブナ基底 $P,$ $Q$ を決定する．この選び方についを $P,$ $Q$ の生成元の数とする．
$R/P,$ $R/Q$ を線形空間としてみたときの次元をそれぞれ以下とする．
$n_{p}=\dim(R/P)$$n_{q}=\dim(R/Q)$$n_{p}/2$未満の自然数$\mathbb{Z}_{p}[\overline{x}]/P,$$\mathbb{Z}_{q}[\overline{x}]/Q$$d_{F},$ $d_{G}$上に逆元選ぶ．

を決定する．多項式$F\in \mathcal{L}_{P}(d_{F}, d_{F}-1)$を持つか調べる．これらの逆元

$F$
$F$

$F_{P}^{-1},$ $F_{Q}^{-1}$をランダムに選び，定理 2 にょり$F_{P}^{-1},$$F_{Q}^{-1}$が両方存在する多項式 $F$ をまたこのことに関しては？？にて詳しく述べる．
次に$G\in \mathcal{L}_{P}(d_{G}, d_{G})$をランダムに選ぶ．この$G$と$F_{Q}^{-1}$から $H$ を生成する．

$H\equiv G$
公開鍵を $\{q, H, P, Q\}$ , 秘密鍵を $\{FF_{P}^{-1}\}$ とする．

84
3.3

暗号化

平文を

$M\in \mathbb{Z}_{p}[\overline{x}]/P$とする．島$\in \mathcal{L}_{P}(d_{R}, d_{R})$をランダムに選び $C$ を生成する．

ら$C \equiv H\otimes\sum_{i=0}(P_{i}\otimes R_{i})+M (mod q)(mod Q)$

3.4

復号

まず暗号文 $C$ と秘密鍵 $F$ から $A$ を求め，

$A\equiv C$生成した $A$ より復号文 $M’$ を求める．

$M’\equiv A$
3.5

復号条件

定理 4(復号条件)
復号文が平文と一致する必要条件は以下である．

$|G$

旺明
復号の過程において$A \equiv C$$\equiv F\otimes H\otimes\sum_{i=0}^{l_{p}}(P_{i}\otimes R)+F\otimes M (mod q)(mod Q)$$\iota_{p}$$\equiv F*F_{Q}^{-1}\otimes G\otimes\sum_{i=0}(P_{i}$ら$\equiv G\otimes\sum_{i=0}(P_{i}\otimes\hslash)+F\otimes M (mod q)(mod Q)$となり，$P$はグレブナ基底なので剰余をとれば $\sum_{i=0}^{l_{p}}(P_{i}$ より$M’ \equiv A\otimes F_{P}^{-1} (mod p)(mod P)$$\equiv F_{P}^{-1}\otimes G\otimes\sum_{i=0}^{l_{p}}(P_{i}$$\equiv M (mod p)(mod P)$

よって，復号文に平文は一致する．口

85
3.6

グレブナ基底 $P,$ $Q$ の選び方

3.2 におけるグレブナ基底 $P,$$Q$が満たすべき条件は以下である．

1. { $R/P$ を線形空間としてみたときの基底}

2.

$\exists f\in P,$$\subset${ $R/Q$ を線形空間としてみたときの基底}$\forall g\in Q,g\neq 0(mod f)$

条件 1 を満たしていない場合，平文$M$を $R/P$ にとるので暗号化の過程で $Q$ で剰余をとったときに平文の情報が失われてしまう．

条件 2 を満たしていない場合，$C\equiv M(mod q)(mod P)$ となってしまい簡単に解読されてしまう．

3.7

2 変数の場合の例

2 変数の場合の MTRU の具体例をあげる．
$\overline{x}=\{x, y\}$ ,辞書式順序を採用し，グレブナ基底を $P=$$\langle x^{3}-1,$ $y^{3}-1\rangle,$$Q=\langle x^{7}-1,$ $y^{7}-1\rangle$, パラメータを $\{p, q, d_{F}, d_{G}, d_{R}\}=$ {3,89,3,1,1} とした．

$F=x^{2}+x+y-xy-1$$F_{p}^{-1}=-x-x^{2}-y-2xy-2y^{2}-2xy^{2}-2x^{2}y^{2}$$F_{Q}^{-1}=-75-33x-34x^{2}-33x^{3}-76x^{4}-72x^{5}-32x^{6}-S5y-54xy-51x^{2}y-15x^{3}y-20x^{4}y$$-31x^{5}y-11x^{6}y-72y^{2}-11xy^{2}-80x^{2}y^{2}-55x^{3}y^{2}-51x^{4}y^{2}-28x^{5}y^{2}-59x^{6}y^{2}-6y^{3}$$-54xy^{3}-40x^{2}y^{3}-69x^{3}y^{3}-16x^{4}y^{3}-62x^{5}y^{3}-20x^{6}y^{3}-y^{4}-68xy^{4}-55x^{2}y^{4}$$-63x^{3}y^{4}-65x^{4}y^{4}-S5x^{5}y^{4}-19x^{6}y^{4}-47y^{5}-51xy^{5}-S5x^{2}y^{5}-55x^{3}y^{5}-53x^{4}y^{5}$$-39x^{5}y^{5}-26x^{6}y^{5}-70y^{6}-85xy^{6}-11x^{2}y^{6}-66x^{3}y^{6}-75x^{4}y^{6}-38x^{5}y^{6}-11x^{6}y^{6}$$G=-y+1$$H=84+52x+66x^{2}+33x^{3}+88x^{4}+55x^{5}+68x^{6}+79y+68xy+72x^{2}y+18x^{3}y+56x^{4}y+41x^{5}y$$+21x^{6}y+13y^{2}+43xy^{2}+60x^{2}y^{2}+49x^{3}y^{2}+58x^{4}y^{2}+3x^{5}y^{2}+41x^{6}y^{2}+66y^{3}+46xy^{3}$$+40x^{2}y^{3}+75x^{3}y^{3}+35x^{4}y^{3}+55x^{5}y^{3}+39x^{6}y^{3}+5y^{4}+75xy^{4}+74x^{2}y^{4}+6x^{3}y^{4}+40x^{4}y^{4}$$+66x^{5}y^{4}+x^{6}y^{4}+43y^{5}+17xy^{5}+59x^{2}y^{5}+8x^{3}y^{5}+12x^{4}y^{5}+46x^{5}y^{5}+82x^{6}y^{5}+66y^{6}+55xy^{6}$$+74x^{2}y^{6}+7Sx^{3}y^{6}+67x^{4}y^{6}+x^{5}y^{6}+15x^{6}y^{6}$$R_{1}=-x+1$$R_{2}=x-1$$M=x^{2}+xy-y+1$$C=52+75x+15x^{2}+S4x^{3}+23x^{4}+77x^{5}+32x^{6}+76y+12xy+27x^{2}y+20x^{3}y+74x^{4}y+59x^{5}y$$+88x^{6}y+47y^{2}+45xy^{2}+19x^{2}y^{2}+57x^{3}y^{2}+41x^{4}y^{2}+83x^{5}y^{2}+64x^{6}y^{2}+33y^{3}+52xy^{3}$$+59x^{2}y^{3}+60x^{3}y^{3}+14x^{4}y^{3}+27x^{5}y^{3}+22x^{6}y^{3}+65y^{4}+37xy^{4}+20x^{2}y^{4}+58x^{3}y^{4}+32x^{4}y^{4}$$+14x^{5}y^{4}+41x^{6}y^{4}+32y^{5}+4xy^{5}+19x^{2}y^{5}+61x^{3}y^{5}+54x^{4}y^{5}+8x^{5}y^{5}+51y^{6}+43xy^{6}$$+20x^{2}y^{6}+16x^{3}y^{6}+29x^{4}y^{6}+SSx^{5}y^{6}+20x^{6}y^{6}$864

安全性4.1

総当たり攻撃4.1.1

NTRU

NTRU[ ]
$I$によれば，公開鍵に対して$H,$ $q,$ $Q$は既知であるので $G$ を総当たりすればより秘密鍵 $F$ を求めることが可能である．よって$\mathcal{L}(d_{G}, d_{G})$$F_{q}^{-1}$を求まり，$F_{q}^{-1}$を総当たりすればよい．つまり公開鍵の安全性(KeySecurity) は(KeySecurity)$=\sqrt{\neq \mathcal{L}(d_{G},d_{G})}$$= \frac{1}{d_{G}!}\sqrt{\frac{n!}{(n-2d_{G})!}}$

同様に暗号文について総当たりする空間はであるので，暗号文の安全性 (MessageSecurity) は$G$$\mathcal{L}(d_{R}, d_{R})$(MessageSecurity)$=\sqrt{\#\mathcal{L}(d_{R},d_{R})}$$= \frac{1}{d_{R}!}\sqrt{\frac{n!}{(n-2d_{R})!}}$

である．

4.1.2

MTRU

定理 5(総当たり攻撃に対する安全性)
MTRU における公開鍵に対する総当たり攻撃の安全性 (KeySecurity) は，(KeySecurity)$=\sqrt{\#\mathcal{L}_{P}(d_{G},d_{G})}$$= \frac{1}{d_{G}!}\sqrt{\frac{n_{p}!}{(n_{p}-2d_{G})!}}$

暗号文の安全性は (MessageSecurity) は，(MessageSecurity)$=(\sqrt{\#\mathcal{L}_{P}(d_{R},d_{R})})^{l_{p}}$

である．

証明

公開鍵の作り方は以下であるので，総当たりする空間は$\mathcal{L}_{P}(d_{G}, d_{G})$$H\equiv G\otimes F_{Q}^{-1} (mod q)(mod Q)$

である．

87
よって，安全性は公開鍵の安全性 (KeySecurity) は(KeySecurity)$=\sqrt{\#\mathcal{L}_{P}(d_{G},d_{G})}$$=\sqrt{(_{d_{G}}^{n_{p}})*(^{n_{p_{d_{G}^{-d_{G}}}}})}$$= \frac{1}{d_{G}!}\sqrt{\frac{n_{p}!}{(n_{p}-2d_{G})!}}$

暗号文に対して，総当たりする空間は$(\mathcal{L}_{P}(d_{R}, d_{R}))$(MessageSecurity)

である．よって暗号文の安全性 (MessageSecurity) は$=(\sqrt{(\#\mathcal{L}_{P}(d_{R},d_{R}))})^{\iota_{p}}$$=(\sqrt{(_{d_{R}d_{R}}^{n_{p)*(^{n_{p}-d_{R}})}}})^{\iota_{p}}$$=( \frac{1}{d_{R}!}\sqrt{\frac{n_{p}!}{(n_{p}-2d_{R})!}})^{l_{p}}$口

4.2

格子簡約攻撃Coppersmith, Shamir[2] によれば，NTRU 暗号はある格子に対して LLL アルゴリズムにょり簡約基底を求め，公開鍵から秘密鍵と等価な鍵を得ることができる．
公開鍵を$H= \sum_{i=0}^{n}h_{i}x^{i}$として $H$ の係数ベクトルの巡回行列を $M_{H}$ とする．

$M_{H}=(\begin{array}{llll}h_{0} h_{1} \cdots h_{n-1}h_{n-1} h_{0} \cdots h_{n-2}| | |h_{1} h_{2} \cdots h_{0}\end{array})$$\ovalbox{\tt\small REJECT}$

を $f$ の係数ベクトル， を$V_{g}$$g$の係数ベクトルとして以下のことが成り立っ．
$V_{f}M_{H}=V_{g}$ここで次のような格子を考える． を $(n, n)$ 単位行列として$I$$L_{M}=(\begin{array}{ll}\alpha I M_{H}O qI\end{array})$

この簡約基底は整数結合で表されるので $F,$ $G$ と等価な鍵が見つかる．

88
以下，MTRU において格子簡約攻撃について検討する．

$M_{h}$

は $R/I$上の倍行列であるので，$R/Q$ 上の$h$倍行列を考えてこれをとする．このとき，$V_{f}*M_{h}’=V_{g}$ であるので NTRU 格子と同様に格子を構成す単位行列としてる． を$M_{h}’$$I$$(n_{q}, n_{q})$$L_{M}’=(\begin{array}{ll}\alpha I M_{h}O qI\end{array})$

この格子の列ベクトルは $vh\equiv w(mod q)(mod Q)$ を満たす
底がと等価な鍵を含んでいるが，MTRU では$(\alpha V_{f}, V_{g})$$L_{M}’$$(\alpha v, w)$である．NTRU においてはこの簡約基の簡約基底に$(\alpha V_{f}, V_{g})$と等価な鍵は含まれなかった．よって NTRU に対する格子簡約攻撃をそのまま MTRU に適用することはできない．ただし，他の格子を用いた LLL アルゴリズムによる攻撃を受ける可能性はある．

5実装$Risa/$ Asir[4]を用いて NTRU と MTRU 実装した．

計算機環境は $CPU:$ Intel Corei72. $8GHz,$ $MEMORY:DDR316GB,$ $OS:MacOSXl0.6.4,$
Risa/Asir:Version 20100526 である．
$30KB$ のテキストデータを暗号化し復号した．
実験は鍵を生成し，$n,$
表 1 は NTRU の実験結果であり，り方である．p,$q$$d_{F},$ $d_{G},$ $d_{R}$は NTRU[ ] で提案されているは 3 つのパラメータの取$I$は MTRU に合わせた．

は NTRU と同じものとした．グレブナ基
表 2 はそれぞれ 2 変数の MTRU の実験結果である．
$Q=\langle x_{1}^{b}-1,$
底は NTRU を単純に拡張した形の $P=\langle x_{1}^{a}-1,$とした．また はNTRU と MTRU の KeySecurity をほぼ同じにするようにとった．
key, enc, dec はそれぞれ鍵生成，暗号化，復号にかかった時間 (秒) であり，ffle は暗号文の大きさ ( $KB$ ) で$d_{F},$ $d_{G},$ $d_{R}$$\cdots,$$x_{m}^{a}-1\rangle,$ある．ks は KeySecurity, ms は MessageSecurity である．

表 1: NTRU

表 2:MTRU(2)$\cdots,$$x_{m}^{b}-1\rangle$$a$

89
参献[1] J. Hoffstein, J. Pipher and J. Silverman, “NTRU: A Ring-Based Public Key Cryptosystem”
CRYPTO 1996, Lecture Notes in Computer Science, Vol. 1423, 1998, pp. 267-288.
[2] D. Coppersmith and A. Shamir, “Lattice attacks on NTRU”, EUROCRYPT 1997, Lecture Notes inComputer Science, Vol. 1233, 1997, pp. 52-61.

[3] Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman, “NTRUSIGN:Digital signatures using theNTRU lattice” $CT$-RSA 2003 [3-540-00847-0] Hoffstein.
-[4] Risa/Asir
http: $//www$ . math. kobe-u. ac.jp/Asir/asir-ja. html