数理解析研究所講究録
第 1572 巻 2007 年 114-123

114

代数曲面公開鍵暗号に対する簡約を利用した攻撃法
A Reduction Attack on Algebraic Surface Public-Key Cryptosystems

岩見真希
MAKI IWAMI

大阪経済法科大学

教養部

FACULTY OF LIBERAL ARTS AND SCIENCES, OSAKA UNIVERSITY OF ECONOMICS AND LAW*

Abstract
代数曲面公開鍵暗号は, 代数曲面上のセクションを求める求セクション問題の計算困難性に安全性の根拠をおく公開鍵暗号として, 秋山と後藤により開発された. 求セクション問題は NP 完全である多次多変数方程式の求解問題に帰着される. しかし, 内山と徳永が, 公開鍵として用いられる代数曲面の定義方
程式がある条件を満たすとき, 公開燵と暗号文から, 簡約を利用することで, 求セクション問題を解くことなく効率よく平文を求めることができる攻撃法を考案した、 この攻撃法は, 体 Fp 上の多項式環で行われているが, 本稿では, それを有理関数体上の多項式環で行えるように拡張することで, 全ての場合に適用可能な攻撃法を提案する. さらに, 攻撃例として, いくつかの toy example も掲載している.

Abstract
A Public-key Cryptosystem using Algebraic Surfaces whose security is based on a decision randomizing polynomial problem which is related to a problem of finding sections on fibered algebraic
surfaces, was developed by Akiyama and Goto. This section finding problem can be reduced tosolving a multivariate equation system and this problem is known to be NP-complete. In the casethat the defining equation of a surface used for the public key is in a certain form, Uchiyama andTokunaga successed to attack in the sense of getting plaintexts from corresponding ciphertexts using
reductions efficiently without solving section finding problem. It is performed in the polynomial ringoverunder some assumptions whereas, by extending it to be able to perform in the polynomial
ring over rational function field, we can see the new algorithm applicable to all cases with some toy
examples. 1)$F_{p}$

1

はじめに
公開鍵暗号は, 暗号化する健が公開できるという特性から, 初めてアクセスしてきた相手とも安全な秘密通信を行うことができるため, 現在, 広く普及している.

しかし, 現在の公開鍵暗号の技術では, 秘密鍵暗号に比べて処理時間や電力がかかるため, 携帯電話などのモバイル機器への利用は難しいといわれている.
また, 量子計算機が実現すると解読されてしまうため, 新しい公開鍵暗号の開発が求められている.

これらの問題に対処すべく, 2005 年に秋山 (東芝) と後藤 (北海道教育大) は, 量子計算機による解読にも強く, モバイル機器への導入も視野に入れた暗号として, 代数曲面上のセクションを求める問題 (求セクショ

ン問題) の計算困難性に安全性の根拠をおく代数曲面公開鍵暗号を開発した. この求セクション問題は NP完全である多次多変数方程式を解く問題に帰着される. 秋山-後藤代数曲面公開鍵暗号 [1, 3, 4] は, 2005 年
2 月, 東芝研究開発センターの Web サイト [2] で最新技術情報として一般向けにも公開されている.
’makiOkeiho-u. ac.jp
part of this work was supported by JSPS. Grant-in-Aid for Scientific Research.

$\iota)A$115
しかし, 2007 年に内山と徳永 (首都大学東京) が, 公開鍵として用いられる代数曲面の定義方程式がある条件を満たすとき,

1 つの暗号文と公開鍵から, 簡約を利用することで, 求セクション問題を解くことなく,

対応する平文を求める攻撃法を考案し [5], そのことが, CRYPTREC report 2006 [6] の “ 付録 3 代数
曲面を用いた公開鍵暗号の安全性について の中の (4) 公開鍵アルゴリズム でも紹介されている.
内山-徳永の攻撃法が体上の多項式環で行なわれる条件つき攻撃法であるのに対して, 本稿では, 有理関数体上の多項式環で行うことができるように拡張することで, 全ての場合に適用可能な攻撃法を提案
‘’

”

“

$F_{p}$

する.

本稿では, 2 章で秋山-後藤代数曲面公開鍵暗号, 3 章で内山-徳永の条件つき攻撃法を紹介し, 条件が必要となる理由について, 具体的にその破綻する例を交えて説明し, その解決策として, 4 章で全ての場合に適用可能な新しい攻撃法を提案する.

本稿の提案手法の証明および Gr\"obner 基底を利用した攻撃手法については, 著者の [8] を参照されたい.

2

秋山-後藤代数曲面公開鍵暗号 [1, 3, 4]
本章では, 秋山-後藤代数曲面公開鍵暗号をサーベイする. 詳細は, [1, 3, 4] を参照されたい. ここで,

$F_{p}$

上で定義された代数曲面を考える.

[鍵生\hslash ]1. 秘密鍵:(Fp) 内の をパラメータとする 2 つの異なる曲線$A^{3}$$t$(a)$D_{1}$: $(x, y, t)=(u_{x}(t), u_{y}(t),$ )(b)$D_{2}$: $(x, y, t)=(v_{x}(t), v_{y}(t),t)$$D_{1}$と$D_{2}$を選ぶ.

$t$

ただし, 復号結果の一意性のため,$\deg u_{x}(t)\neq\deg v_{x}(t)$または $\deg u_{y}(t)\neq\deg v_{y}(t)$ を満たすとする.

2. 公開鍵:(a)$D_{1},$$D_{2}$

を含む, 体$F_{p}$

上の曲面 $X(x, y, t)=0$ を構成する. 次を満たすことは明らか.
$X(u_{x}(t),u_{y}(t),$ $t$) $=X(v_{x}(t),v_{y}(t),$ ) $=0$$t$

実際, 2 つのセクションを含む曲面 $X(x, y, t)=0$ は, 次の方法で構成する.
まず, 次で定義される代数曲面 $X(x, y, t)=0$ を考える.
$X(x, y, t)= \sum_{i,j}$ 果$i(t)x^{i}y^{j}=0$$D_{1}$$X$: $(u_{x}(t), u_{y}(t),$ ) と$t$$D_{2}$: $(v_{x}(t), v_{y}(t),$ ) のようにパラメータ表示された 2 つの具なる曲線が$t$のセクションとなるための必要十分条件は,$\sum_{t,j}$

そして,院 j $(t)u_{x}(t)^{i}u_{y}(t)^{j}= \sum_{i,j}$ 果$j(t)v_{\Phi}(t)^{i}v_{\nu}(t)^{j}=0$$\sum_{(t,j)\neq(0,0)}c_{ij}(t)(u_{x}(t)^{i}u_{y}(t)^{j}-v_{x}(t)^{i}v_{y}(t)^{j})=0$を満たすことが必要である. したがって,$c_{10}(t)(tu_{x}(t)-v_{x}(t))= \sum_{(i,j)\neq(0,0),(1,0)}c_{lj}(t)(u_{x}(t)^{i}u_{y}(t)^{j}-v_{x}(t)^{\dot{*}}v_{y}(t)^{j})$ここで,$u_{x}(t)^{i}u_{y}(t)^{j}-v_{x}(t)^{i}v_{y}(t)^{j}=(u_{x}(t)^{i}-v_{x}(t)^{i})u_{y}(t)^{j}+v_{x}(t)^{i}(u_{y}(t)^{j}-v_{y}(t)^{j})$

この表現は, もし $(u_{x}(t)-v_{x}(t))|(u_{y}(t)-v_{y}(t))$ ならば,$(u_{x}(t)-v_{x}(t))$.
が成り立ち,

で割ることができる. す116
なわち, この条件が満たされているならば, ランダムに選んだ多項式$c_{i:}$$(t)((i,j)\neq(O, 0),$ $(1,0))$を用いて, 上記の関係式により, 多項式 $c_{1}0(t)$ を決定することができる.

まとめると, 鍵生成アルゴリズムは次のように書くことができる :1.

$\lambda_{x}(t)|\lambda_{y}(t)$を満たすランダムな 2 つの多項式$\lambda_{x}(t),$$\lambda_{y}(t)$を選ぶ.

(これは $(u_{x}(t)-v_{x}(t))|(u_{y}(t)-v_{y}(t))$ であるために必要な条件)

2. ランダムに$v_{x}(t)$を選び,$\lambda_{x}(t)+v_{x}(t)$なる $u_{x}(t)$ を計算する.

$(i.e. u_{x}(t)=\lambda_{x}(t)+v_{x}(t))$

3. ランダムに$v_{y}(t)$を選び,$\lambda_{y}(t)+v_{y}(t)$なる $u_{y}(t)$ を計算する.

$(i.e. u_{y}(t)=\lambda_{y}(t)+v_{y}(t))$

4. ランダムに果 j(t) $((i,j)\neq(0,0),$ $(1,0))$ を選び, 次の条件を満たす$c_{1}0(t)$$c_{10}(t)(u_{x}(t)-v_{x}(t))= \sum_{(i,j)\neq(0,0),(1,0)}q_{j}(t)(u_{x}(t)^{1}u_{y}(t)^{j}-v_{x}(t)^{i}v_{y}(t)^{j})$5.

$\sum_{i,j}\mathfrak{g}_{j}(t)u_{x}(t)^{i}u_{y}(t)^{j}=\sum_{i,j}c_{tj}(t)v_{x}(t)^{i}v_{y}(t)^{j}=0$$c00=- \sum_{(i,j)\neq(0,0)}$ 果 i $(t)u_{x}(t)^{t}u_{y}(t)^{j}$より,.

を計算する.

coo はで与えられる.

以上のアルゴリズムより, 次を得る.
$\deg_{t}X(x,y,t)=\deg c_{00}(t)\geq\deg_{xy}X(x,y,t)d$

ここで $\deg_{xy}X(x, y, t)$ は $X(x, y,t)$ の $x$ と $y$ に関する次数をあらわす.

(b) 暗号化ステップで選ばれるモニックな既約多項式 $f(t)\in F_{p}[t]$ の次数の下限として $\ell\in N$ を選ぶ.
セキュリティ上の理由から (詳細は [4] の 53 参照), $\deg_{t}X(x, y, t)<\ell$ を満たすように設定する.
(c) $d\geq ma3C(\deg u_{x}(t), \deg u_{y}(t),$ $\deg v_{x}(t)$ , deg $v_{y}(t))$ を満たす $d\in N$ を選ぶ.
$\ell$

もしくは$d$

を大きくとることで, 基礎体の標数$P$を可能な限り小さく選ぶことができる (e.g. 最大 4 ビット). 鍵サイズの見積もりは $[4]7$ 章を参照されたい.

[暗号化]
$m$

を平文とする.

$m$を次のような小さなブロックに分割する.
$m=m_{0}||m_{1}||\cdots||m_{\ell-1}$

ただし, 各$m_{t}$

は $0\leq m_{i}\leq p-1$ を満たすように選ぶ.

1. $m$ を次のように平文多項式に埋め込む.
$m(t)=m_{\ell-1}d^{-1}+\cdots+m_{1}t+m0$

2. セキュリティ上, 次を満たすランダムな多項式 $s(x, y, t)$ を選ぶ (詳細は [4] の 53 参照) :$\alpha>\deg_{x}X(x,y,t)l1’\supset\beta>\deg_{y}X(x,y,t)$を満たす項$x^{\alpha}y^{\beta}$

を含み,さらに次を満たす.

$(\deg_{x}s(x,y,t)+\deg_{y}s(x,y,t))d+\deg_{t}s(x,y,t)<p$(この条件により, $deg(s(u_{x}(t),u_{y}(t),t)-s(v_{x}(t),v_{y}(t),t))<p$ が導かれ, 復号ステップにおいて, 因子 $f(t)$ を検出することができる)

117
3. 次を満たすランダムな多項式 $r(x, y, t)$ を選ぶ (セキ参照されたい) :$\iota$リティ上必要な条件であり, 詳細は [4] の 53 を$\deg_{t}r(x, y, t)<\ell$

4. deg $f(t)\geq\ell$ なるモニックな既約多項式 $f(t)$ をランダムに選ぶ.
5. 暗号文である多項式 $F(x, y, t)$ を次で計算する.
$F(x,y,t)=m(t)+f(t)s(x,y, t)+X(x,y,t)r(x,y,t)$[復号]$D_{1},$ $D_{2}$は $X$ 上に存在するため,

1. セクション$D_{1}$

および$D_{2}$$X(u_{x}(t), u_{y}(t),t)=X(v_{x}(t), v_{y}(t),t)=0$ を満たすことに注意されたい.

を $F(x, y,t)$ に代入する :$h_{1}(t)=F(u_{x}(t), u_{y}(t),t)=m(t)+f(t)s(u_{x}(t),u_{y}(t),t)$$h_{2}(t)=F(v_{x}(t), v_{y}(t),$ $t$) $=m(t)+f(t)s(v_{x}(t), v_{y}(t),$ )$t$

2. $h_{1}(t)-h_{2}(t)$ を計算する :$h_{1}(t)-h_{2}(t)=f(t)(s(u_{x}(t),u_{y}(t),$$t$) $-s(v_{x}(t),v_{y}(t),$ ))$t$

3. $h_{1}(t)-h_{2}(t)$ を因数分解し, すべの因子の中で次数が最大のモニックな既約多項式 $f(t)$ を検出する.
(この方法で $f(t)$ が検出される理由は次を参照されたい)4.

$h_{1}(t)$の $f(t)$ に関する正規形を計算し,$m(t)$ を得る.

$(\deg m(t)<\deg f(t).)$

5. $m(t)$ から $m$ を求める.
例 1(鍵生成)以後. 本稿の例では, 体 F2 を扱うものとする.

[秘密鍵]$\lambda_{x}(t)|\lambda_{y}(t)$を満たすようにランダムに生成された多項式を$u_{x}(t):=t^{2}+t,$ $u_{y}(t):=t^{3}+t^{2}+t+1$$1+t^{2}$$\lambda_{x}(t)$$:=t^{2}+1,$$\lambda_{y}(t)$$:=t(t^{2}+1)$ ,とする. そして $v_{x}(t):=u_{x}(t)-\lambda_{x}(t)=1+t,$ $v_{y}(t):=u_{y}(t)-\lambda_{y}(t)=$を計算する. このとき, 秘密鍵は次のような異なる 2 つの曲線で定義される.
$D_{1}$: $(u_{x}(t),u_{y}(t),t)=(t^{2}+t, t^{3}+t^{2}+t+1, t)$ ,$D_{2}$: $(v_{x}(t), v_{y}(t),t)=(1+t, 1+t^{2},t)$ .

[公開鍵] 2 つの曲線 (秘密鍵) を含む代数曲面 $X(x, y, t)= \sum_{i,j}$ 果$j(t)x9$ (公開鮒を生成するために, ラ
および $\infty o(t)\in F_{2}(t)$ を次で計算する.
ンダムに果 j(t)((i, $j)\neq(O,$ $0),$ $(1,0)$ ) を生成し,$c_{10}(t)$$c_{10}(t):=- \sum_{(i,j)\neq(0,0),(1,0)}q_{j}(t)(u_{x}(t)^{:}u_{y}(t)^{j}-v_{x}(t)^{:}v_{y}(t)^{j})/(u_{x}(t)-v_{x}(t))$$c_{00}(t)$$:=- \sum_{(i,j)\neq(0,0)}q_{j}(t)u_{x}(t)^{i}u_{y}(t)^{j}$.

例えば, 次のような $X_{A}(x,y, t)$ および $X_{B}(x, y,t)$ が生成される.
や でくくることがある)(以後, 紙面上で見やすくするために, 便宜上,
$x$

$y$

$X_{A}(x,y, t)$ $:=y^{5}+x^{5}+(t^{6}+t^{4}+t^{3}+t+1)x^{2}y+(t^{13}+t^{12}+t^{11}+t^{10}+t^{7}+t^{5}+t^{3})x+(t^{8}+t^{7}+t^{4}+$$t+1)y+t^{14}+t^{9}+t^{7}+t^{6}+t^{5}+t^{4}+t^{3}+t$ ,$X_{B}(x, y, t):=t^{2}+t^{8}+t^{12}+t^{14}+t^{21}+t^{22}+t^{23}+t^{24}+t^{26}+t^{27}+t^{28}+t^{29}+y+t^{2}y+y^{2}+t^{3}y^{2}+y^{3}+t^{2}y^{3}+$$t^{3}y^{3}+ty^{4}+t^{2}y^{4}+t^{4}y^{4}+t^{5}y^{4}+y^{5}+t^{4}y^{5}+x(t+t^{3}+t^{5}+t^{10}+t^{11}+t^{16}+t^{17}+t^{19}+t^{21}+t^{23}+t^{26}+t^{28}+$

118$t^{3}y+t^{4}y+y^{2}+ty^{2}+t^{3}y^{2}+y^{3}+ty^{3}+t^{3}y^{3}+t^{5}y^{3}+y^{4}+ty^{4}+t^{2}y^{4}+t^{3}y^{4}+t^{4}y^{4}+y^{5}+t^{2}y^{5})+x^{4}(1+t^{2}+$$t^{4}+t^{5}+t^{3}y+t^{4}y+t^{5}y+y^{2}+ty^{2}+t^{2}y^{2}+t^{3}y^{2}+t^{4}y^{2}+ty^{3}+t^{2}y^{3}+t^{4}y^{3}+y^{4}+t^{2}y^{4}+t^{3}y^{4}+t^{5}y^{4}+y^{6}+$$t^{4}y^{5})+x^{3}(t+t^{3}+t^{4}+t^{5}+y+ty+t^{3}y+t^{\text{\’{o}}}y+t^{2}y^{2}+t^{4}y^{2}+y^{3}+t^{2}y^{3}+t^{3}y^{3}+t^{5}y^{3}+t^{2}y^{4}+t^{3}y^{4}+y^{5}+$$t^{5}y^{5})+x^{2}(t+t^{5}+t^{2}y+t^{4}y+y^{2}+ty^{2}+ty^{3}+t^{2}y^{3}+t^{3}y^{3}+t^{4}y^{3}+t^{5}y^{3}+y^{4}+ty^{4}+t^{3}y^{4}+t^{4}y^{4}+y^{5}+ty^{5}+$$t^{5}y^{5})+x^{5}(1+t^{3}+ty+t^{2}y+t^{3}y+t^{4}y+t^{4}y^{2}+t^{5}y^{2}+ty^{3}+t^{2}y^{3}+t^{4}y^{3}+y^{4}+t^{2}y^{4}+t^{4}y^{4}+ty^{5}+t^{25}y+t^{5}y^{5})$$X_{i}(x, y, t)(i=A, B)$ が 2 つの曲線を含むことは,$X_{i}(u_{x}(t), u_{y}(t),$ $t$) $=X_{i}(v_{x}(t), v_{y}(t),$ ) $=0$ をチェックす$t$

ることで確かめることができる.
注意 1
ここでは, 辞書式順序を用いることとする.

$X_{A}(x, y, t)$

を公開鍵として使用する場合, 主項 $LT(X_{A})=x^{5}$が仮定 1(3 章参照) を満たすため, 内山-徳永の攻撃法で解読することができる. 一方,$X_{B}(x, y,t)$ が公開鍵として使用された場合, 主項が $LT(X_{B})=t(1+t+t^{4})x^{5}y^{5}$ となり, 仮定 1 を満たさないため, 内山-徳永の攻撃法が適用できない. そこで, 全ての場合, すなわち, 本稿の例では $X_{A}(x, y,t)$ と $X_{B}(x,y,t)$ の両方に適用可能な新しい攻撃法を提案して, 解読する (4 章参照).
各種攻撃法を理解しやすくするため, 暗号化と復号の例を挙げる.

例 2(暗号化と復号)[暗号化]$m(t)$ 坪文多項式), $f(t),$ $s(x, y,t)$ , そして $r(x, y, t)$ を次のように設定する.

,,$m(t):=1+t+t^{2}+t^{\theta}+t^{4}+t^{6}+t^{8}+t^{9}+t^{14}+t^{17}+t^{19}+t^{20}+t^{23}+t^{26}+t^{28}+t^{29}+t^{30}+t^{32}+t^{84}+t^{35}+t^{36}+t^{37}+t^{39}$$f(t):=1+t+t^{2}+t^{4}+t^{7}+t^{9}+t^{10}+t^{11}+t^{14}+t^{17}+t^{22}+t^{23}+t^{25}+t^{26}+t^{27}+t^{28}+t^{32}+t^{34}+t^{36}+t^{38}+t^{40}$$s(x,y, t)$ $:=t+t^{3}+x^{3}+y^{2}+x^{6}y^{6},$ $r(x, y,t)$ $:=1+t^{3}+t^{4}+xy+y^{2}$ .
$F_{2}[x, y,t]$

で, 暗号文 $F_{A}(x, y, t)$ は $X_{A}(x, y, t)$ を用いて次のように計算される.

$F_{A}(x, y,t)$$:=m(t)+f(t)s(x, y,t)+X_{A}(x,y, t)r(x, y,t)=1+t+t^{6}+t^{12}+t^{14}+t^{15}+t^{17}+t^{19}+t^{24}+t^{2b}+$$t^{26}+t^{27}+t^{28}+t^{29}+t^{31}+t^{32}+t^{33}+t^{34}+t^{35}+t^{36}+t^{37}+t^{39}+t^{43}+y+ty+t^{3}y+t^{4}y+t^{8}y+t^{10}y+t^{12}y+$$y^{2}+t^{2}y^{2}+t^{3}y^{2}+t^{5}y^{2}+t^{6}y^{2}+t^{10}y^{2}+t^{11}y^{2}+t^{17}y^{2}+t^{22}y^{2}+t^{23}y^{2}+t^{25}y^{2}+t^{26}y^{2}+t^{27}y^{2}+t^{28}y^{2}+t^{32}y^{2}+$$t^{34}y^{2}+t^{36}y^{2}+t^{38}y^{2}+t^{40}y^{2}+y^{3}+ty^{3}+t^{4}y^{3}+t^{7}y^{3}+t^{8}y^{3}+y^{5}+t^{3}y^{5}+t^{4}y^{5}+y^{7}+x^{5}(1+t^{3}+t^{4}+y^{2})+$$x^{3}(1+t+t^{2}+t^{4}+t^{7}+t^{9}+t^{10}+t^{11}+t^{14}+t^{17}+t^{22}+t^{23}+t^{25}+t^{26}+t^{27}+t^{28}+t^{32}+t^{34}+t^{36}+t^{38}+\theta^{0}+$$y^{2}+ty^{2}+t^{3}y^{2}+t^{4}y^{2}+t^{6}y^{2})+x^{2}(y+ty+t^{3}y+t^{4}y+t^{7}y+t^{8}y+t^{9}y+t^{11}y+t^{12}y+t^{13}y+y^{3}+ty^{3}+t^{3}y^{3}+$$t^{4}y^{3}+t^{6}y^{3})+x(t^{3}+t^{5}+t^{6}+t^{8}+t^{9}+t^{12}+t^{17}+ty+t^{3}y+t^{4}y+t^{5}y+t^{6}y+t^{7}y+t^{9}y+t^{14}y+y^{2}+ty^{2}+t^{3}y^{2}+$$t^{4}y^{2}+t^{5}y^{2}+t^{8}y^{2}+t^{10}y^{2}+t^{11}y^{2}+t^{12}y^{2}+t^{13}y^{2}+y^{6})+x^{6}(y+y^{6}+ty^{6}+t^{2}y^{6}+t^{4}y^{6}+t^{7}y^{6}+t^{9}y^{6}+t^{10}y^{6}+$.

$t^{11}y^{6}+t^{14}y^{6}+t^{17}y^{6}+t^{22}y^{6}+t^{23}y^{6}+t^{25}y^{6}+t^{26}y^{6}+t^{27}y^{6}+t^{28}y^{6}+t^{32}y^{6}+t^{34}y^{6}+t^{36}y^{6}+t^{38}y^{6}+t^{40}y^{6})$[復号]$F_{A}(u_{x}(t), u_{y}(t),$ $t$) $-F_{A}(v_{x}(t),v_{y}(t),t)=(t(1+t)^{5}(1+t^{2}+t^{3})(1+t^{2}+t^{6}+t^{8}+t^{9}+t^{10}+t^{11}+t^{12}+t^{16}+t^{17}+$$t^{18}+t^{19}+t^{21})(1+t+t^{2}+t^{4}+t^{7}+t^{9}+t^{10}+t^{11}+t^{14}+t^{17}+t^{22}+t^{23}+t^{26}+t^{26}+t^{27}+t^{28}+t^{32}+t^{S4}+t^{36}+t^{38}+t^{40})$.

ここで, 最大の次数をもつ因子として $f(t)$ が検出される. 最後に, $F(x, y, t)$ の $f(t)$ に関する正規形を計算し (次のように$arrow^{*}$$f(t)$$F_{A}(x,y,t)$を用いてあらわす). 平文多項式を得る.
$arrow^{*}$$1+t+t^{2}+t^{3}+t^{4}+t^{6}+t^{8}+t^{9}+t^{14}+t^{17}+t^{19}+t^{20}+t^{23}$$f(t)$$+t^{26}+t^{28}+t^{29}+t^{30}+t^{32}+t^{34}+t^{3S}+t^{36}+t^{37}+t^{39}(=m(t))$

例 3(暗号化と復号)$X_{B}(x, y, t)$

を公開鍵として使用した場合, 同様に, 対応する暗号文 $F_{B}(x, y, t)$ は次のように計算される.

$F_{B}(x, y, t)$$:=m(t)+f(t)s(x,y, t)+X_{B}(x, y, t)r(x, y, t)=t^{2}+t^{8}+t^{12}+t^{14}+t^{21}+t^{22}+t^{23}+t^{24}+t^{26}+t^{27}+$

119$t^{28}+t^{29}+y+t^{2}y+y^{2}+t^{3}y^{2}+y^{3}+t^{2}y^{3}+t^{3}y^{3}+ty^{4}+t^{2}y^{4}+t^{4}y^{4}+t^{5}y^{4}+y^{5}+t^{4}y^{5}+x(t+t^{3}+t^{5}+t^{10}+t^{11}+$$t^{16}+t^{17}+t^{19}+t^{21}+t^{23}+t^{26}+t^{28}+t^{3}y+t^{4}y+y^{2}+ty^{2}+t^{3}y^{2}+y^{3}+ty^{3}+t^{3}y^{3}+t^{5}y^{3}+y^{4}+ty^{4}+t^{2}y^{4}+t^{3}y^{4}+$$t^{4}y^{4}+y^{5}+t^{2}y^{5})+x^{4}(1+t^{2}+t^{4}+t^{5}+t^{3}y+t^{4}y+t^{5}y+y^{2}+ty^{2}+t^{2}y^{2}+t^{3}y^{2}+t^{4}y^{2}+ty^{3}+t^{2}y^{3}+t^{4}y^{3}+y^{4}+$$t^{2}y^{4}+t^{3}y^{4}+t^{5}y^{4}+y^{5}+t^{4}y^{5})+x^{3}(t+t^{3}+t^{4}+t^{5}+y+ty+t^{3}y+t^{5}y+t^{2}y^{2}+t^{4}y^{2}+y^{3}+t^{2}y^{3}+t^{3}y^{3}+t^{5}y^{3}+t^{2}y^{4}+$$t^{3}y^{4}+y^{5}+t^{5}y^{5})+x^{2}(t+t^{5}+t^{2}y+t^{4}y+y^{2}+ty^{2}+ty^{3}+t^{2}y^{3}+t^{3}y^{3}+t^{4}y^{3}+t^{5}y^{3}+y^{4}+ty^{4}+t^{3}y^{4}+t^{4}y^{4}+y^{5}+$.

$ty^{5}+t^{5}y^{5})+x^{5}(1+t^{3}+ty+t^{2}y+t^{3}y+t^{4}y+t^{4}y^{2}+t^{5}y^{2}+ty^{3}+t^{2}y^{3}+t^{4}y^{3}+y^{4}+t^{2}y^{4}+t^{4}y^{4}+ty^{5}+t^{2}y^{5}+t^{5}y^{5})$例 2 と同様に復号される.

そして,各種攻撃手法を用いた解読例は, 次の各章を参照されたい.

3

内山-徳永の簡約を利用した条件付き攻撃法 [5]4 章で全ての場合に適用可能な新しい攻撃法を提案するために, まず, 次の仮定を満たす場合のみに適用可能な内山徳永の攻撃法を簡単にサーベイする. [5] では「割る」, 「余り」, 「先頭項」 という表現を用いているところを, (同じ意味であるが) 4 章および [8] への発展の都合上, 著者によりそれぞれ「正規化する (正規形になるまで簡約を繰り返す) 」, 「正規形」. 「主項」 という表現におきかえ, 各因子の属するドメインも追記して引用している.
仮定 1

公開鍵となる代数曲面 $X$ の定義方程式の, 単項式順序鹿に関する主項 LT(X) が$F_{p}((\alpha, \beta)\neq(0,0))$ なる形をしている.

$\alpha^{\alpha}y^{\beta}$

where$c\in$

アルゴリズム 1(内山-徳永の条件付き攻撃法):

入力

仮定 1 を満たす秋山-後藤代数曲面公開鍵暗号の公開鍵 $X(x, y, t)\in F_{p}[x, y, t]$
暗号文 $F(x, y, t)\in F_{p}[x, y, t]$ .

:出力

暗号文 $F(x, y, t)$ に対応する平文 $m$

1. $F(x, y,t)$ の $X(x, y, t)$ に関する正規形 $R_{1}(x, y,t)\in F_{p}[x, y,t]$ を求める.

2.

$R_{1}$の項で $x^{i}y^{j}((i,j)\neq(O, 0))$ の形をしたもので係数が$\mathbb{F}_{p}$の要素でないものをランダムに選び. その係数を $C$ とする.

3.

$C$

の

の因子となる $F_{p}[t]$ の要素を求め, その中に含まれる次数ゑ以上の既約因子の集合を$\hat{G}$

の要素

$g$

に関する正規形$n$$\hat{G}$とする.

$R_{1}$

が $F_{p}[t]$ の要素となるものを選ぶ.

4. 多項式 $n(t)=n_{k-1}t^{k-1}+\cdots+n_{1}t+n_{0}\in F_{p}[t]$ とおき $m=n_{0}||n_{1}||\cdots||n_{k-1}$ を出力して修了.
注意 2
ここで,

Step 3 における $g(t)$ は $f(t)$ に他ならず, $n(t)$ も $m(t)$ に一致している. 内山徳永の実装では, Step2, 3 では Step2 の条件を満たす 2 つの異なる$R_{1}$の項を取り, それらの係数を$C_{1},$ $C_{2}$として, 最大公約因子 $GCD(C_{1}, C_{2})$ 計算を利用して検出している.

このアルゴリズムの正当性は, 命題 2 を用いて定理 3 を証明しているが, 詳細は [5] を参照されたい.

命題 2 (Propositionl in pp.79-80 in [7])Let $G=\{g_{1}, \cdots g_{t}\}$ be a Grobner basis for an ideal $I\subset k[x_{1}, \cdots , x_{n}]$ and let $f\in k[x_{1}, \cdots , x_{n}]$ (which,
are variables). Then there is a uniquedenotes the polynomi $al$ ring over the field where ,$r\in k[x_{1}, \cdots , x_{n}]$ wtith the following two properties:$k$$x_{1}$–$x_{n}$

120(i) There is $g\in I$ such that $f=g+r$ .
(ii) No term of$r$is reduced by any of $LT(g_{1}),$ $\cdots LT(g_{l})$ .

In particular, is the normal form of the red uc tion ofwhen using the red uction algorithm.
$r$

$f$

by

$G$

no matter how the elements of$G$

are listed

定理 3 (Theoreml in [5])提案アルゴリズムの中で生成される多項式 $g(t),n(t)$ は, 秋山-後藤代数曲面公開健暗号での暗号化/復号の際に用いられる多項式 $f(t)$ , 平文から得られる多項式 $m(t)$ にそれぞれ一致している. すなわち, 出力された平文は正しいものである.

例 4(仮定を満たす公開鍵を使用した例 2 に対する攻撃)$F_{A}(x, y, t)$に関する正規形を $R_{A}(x, y, t)$ とする. このとき,を因数分解した結果のリストは次である.

の $X_{A}(x, y, t)$で非零な $C|j$$R_{A}(x,y,t)$の項 $c_{ij}(t)x^{:}y^{j}$ の中$\{(1+t+t^{2})(1+t+t^{2}+t^{4}+t^{5})(1+t+t^{3}+t^{4}+t^{5}+t^{8}+t^{9}+t^{10}+t^{12}+t^{16}+t^{17})(1+t+t^{4}+t^{6}+t^{7}+t^{8}+t^{10}+$$t^{16}+t^{17}+t^{18}+t^{19}),$ $1+t+t^{2}+t^{4}+t^{7}+t^{9}+t^{10}+t^{11}+t^{14}+t^{17}+t^{22}+t^{23}+t^{25}+t^{26}+t^{27}+t^{28}+t^{32}+t^{34}+$$t^{36}+t^{38}+t^{40},$ $t(1+t)(1+t^{3}+t^{6})(1+t+t^{4}+t^{5}+t^{6})(1+t+t^{2}+t^{4}+t^{7}+t^{9}+t^{10}+t^{11}+t^{14}+t^{17}+t^{22}+t^{23}+$$t^{2\text{\’{o}}}+t^{26}+t^{27}+t^{28}+t^{32}+t^{34}+t^{36}+t^{38}+t^{40}),$ $(1+t+t^{2})^{2}(1+t+t^{2}+t^{3}+t^{4})(1+t+t^{2}+t^{4}+t^{7}+t^{9}+t^{10}+$$t^{11}+t^{14}+t^{17}+t^{22}+t^{23}+t^{25}+t^{26}+t^{27}+t^{28}+t^{32}+t^{34}+t^{36}+t^{38}+t^{40}),$ $1+t+t^{2}+t^{4}+t^{7}+t^{9}+t^{10}+t^{11}+$$t^{14}+t^{17}+t^{22}+t^{23}+t^{25}+t^{26}+t^{27}+t^{28}+t^{32}+t^{34}+t^{36}+t^{38}+t^{40},t^{3}(1+t^{2}+t^{3})(1+t^{3}+t^{4}+t^{5}+t^{7})(1+t+$$t^{2}+t^{4}+t^{7}+t^{9}+t^{10}+t^{11}+t^{14}+t^{17}+t^{22}+t^{23}+t^{25}+t^{26}+t^{27}+t^{28}+t^{32}+t^{34}+t^{36}+t^{38}+t^{40}),$ $1+t+t^{2}+$$t^{4}+t^{7}+t^{9}+t^{10}+t^{11}+t^{14}+t^{17}+t^{22}+t^{23}+t^{26}+t^{26}+t^{27}+t^{28}+t^{32}+t^{34}+t^{36}+t^{38}+t^{40},$ $(1+t+t^{3}+t^{4}+$$t^{6})(1+t+t^{2}+t^{4}+t^{7}+t^{9}+t^{10}+t^{11}+i^{14}+t^{17}+t^{22}+t^{23}+t^{25}+t^{26}+t^{27}+t^{28}+t^{32}+t^{34}+t^{36}+t^{38}+t^{40})\}$$\infty 0$(最初の要素) を除く, 全ての非零要素が共通因子 $1+t+t^{2}+t^{4}+t^{7}+t^{9}+t^{10}+t^{11}+t^{14}+t^{17}+$$t^{22}+t^{23}+t^{25}+t^{26}+t^{27}+t^{28}+t^{32}+t^{84}+t^{36}+t^{38}+t^{40}$ $:=g(t)$ を持っていることがわかる.

すなわち,$f(t)$ が検出できている.

最後に,$R_{A}$の $g(t)$ に関する正規形を計算し,

次を得る.

.

$1+t+t^{2}+t^{3}+\theta+t^{6}+t^{8}+t^{9}+t^{14}+t^{17}+t^{19}+t^{20}+t^{23}+t^{26}+t^{28}+t^{29}+t^{30}+t^{32}+t^{34}+t^{35}+t^{36}+t^{37}+t^{39}$

これはまさに, 平文多項式 $m(t)$ に他ならない.

例 5(内山-徳永の攻撃法が適用できない例 : 仮定を満たさない公開鍵を使用した例 3 に対する検証)$F_{B}(x,y,t)$ の $X_{B}(x,y,t)$に関する正規形を計算する. いま,$LT(X_{B})=t(1+t+t^{4})x^{5}y^{5}$ であるから,

求める正規形を得ようとすると, アルゴリズム 1 における $F_{p}[x, y,t]$ での演算では簡約が進まない. そこで,上の多項式環 $F_{p}(t)[x, y]$ に拡張して正規形を計算してみると, 次が得られる. ここで, 分
有理関数体$\mathbb{F}_{p}(t)$母因子 $t(1+t+t^{4})$ は $LT(X_{B})=t(1+t+t^{4})x^{5}y^{5}$ により生じていることに注意されたい.
$R_{B}(x,y, t)$ $:=(1+t^{3}+t^{7}+\cdots+t^{44}y^{16}+t^{46}y^{16}+t^{48}y^{16}+x^{2}(t^{4}y^{6}+t^{8}y^{6}+t^{12}y^{6}+\cdots+t^{42}y^{16}+t^{45}y^{16}+$$t^{49}y^{16})+x(ty^{6}+t^{4}y^{6}+t^{5}y^{6}+\cdots+t^{45}y^{16}+t^{47}y^{16}+t^{49}y^{16})+x^{4}(t^{6}+t^{4}y^{6}+t^{6}y^{6}+\cdots+t^{46}y^{16}+t^{4}7y^{16}+$$t^{60y^{16}})+x^{3}(1+t+t^{2}+\cdots+t^{48}y^{16}+t^{49}y^{16}+t^{50}y^{16}))/(1+t^{3}+ty+t^{2}y+t^{3}y+t^{4}y+t^{4}y^{2}+t^{5}y^{2}+ty^{3}+$$t^{2}y^{3}+t^{4}y^{3}+y^{4}+t^{2}y^{4}+t^{4}y^{4}+ty^{5}+t^{2}y^{5}+t^{6}y^{5})^{2}$. しかし, 分子に着目して $c0o(t)$ を除く非零なGCD を計算しても, 1 となり, $f(t)$ が検出できない. その理由は, 簡約の途中で,$t(1+t+t^{4})$ の影響で低次の項の次数が上がり,しているからである.

$c_{ij}(t)$の主項 $LT(X_{B})$ の主係数

よって余分に簡約がおこり, 検出に必要な低次項の形を壌121
4

全ての場合に適用可能な攻撃手法の提案$F(x, y, t)$ の $X(x, y, t)$ に関する正規形を $R_{1}(x, y, t),$ $s(x, y, t)$ の $X(x, y, t)$ に関する正規形を $R_{2}(x, y, t)$とする.

このとき, $F=G_{1}X+R_{1},$ $s=G_{2}X+R_{2}$ ,($G_{1},$ $G_{2},$ $R_{1},$ $R_{2}$は一意的) とかける. 暗号文$F=m(t)+f(t)s(x, y, t)+X(x, y, t)r(x, y, t)$ に代入すると$F(x,y,t)=m(t)+f(t)R_{2}(x, y,t)+X(x,y,t)(f(t)G_{2}(x,y, t)+r(x, y,t))$となり, 実は $R_{1}(x, y, t)=m(t)+f(t)R_{2}(x, y, t)$ が成り立っため,関する正規形として $R_{1}(x, y, t)=m(t)+f(t)R_{2}(x, y, t)$ が得られ,$X$の主係数が定数のときには,$f(t)$ を検出してから,

主項 LT(X)における$c_{\alpha\beta}(t)$にさらに $R_{1}(x, y, t)$

しかし, 例 5 に見られるように,の $f(t)$ に関する正規形を計算することで $m(t)$ を求めることに成功した.
$=c_{\alpha}\rho(t)x^{\alpha}y^{\beta}$$F$ の $X$

が定数でない場合 ( を含む場合), $F(x, y, t)$ を $X(x, y_{s}t)$ に関$t$

して正規化すると, 必ずしも望まれる形 $Farrow m(t)+f(t)R_{2}(x,y,t)$ で簡約が止まるとは限らない. 簡約の途中で, 主係数がかけあわされて剰余の$t$の次数が上がり,$X$の主項の項順序よりも高くなってしまい,

望ましくない簡約が引き起こされることがある. その結果, $m(t)+f(t)R_{2}(x,y, t)$ の形が余分な簡約で崩れ, $f(t)$ の検出に失敗する.
本章では, すべての公開鍵の形に適用可能な攻撃法を提案する. 主なアイディアは, $f(t)$ の検出を難しくする原因である主係数 LC(X) $\in F_{p}[t]$ をなくすこと, すなわち, 公開腱 $X(x, y,t)$ を と に関してモニックに変換してから, 有理関数体上の多項式環 $F_{p}(t)[x,y]$ で簡約を繰返し, 正規形を計算するこ
$x$

$y$

$\mathbb{F}_{p}(t)$とである.
アルゴリズム 2(提案手法 : 有理関数体での攻撃)

秋山-後藤代数曲面公開鍵暗号の公開鍵 $X(x, y, t)\in F_{p}[x, y, t]$ ,:入力

暗号文 $F(x, y, t)\in F_{p}[x, y, t]$ .

$0$

暗号文 $F(x, y, t)$ に対応する平文 $m$ .

:出力. 公開鍵 $X$ を, $\tilde{X}:=X/LC(X)\in F_{p}(t)[x, y]$ でモニックに変換する.

1. $F$ の2.

$R_{1}$$\tilde{X}$に関する正規形 $R_{1}(x, y, t)\in F_{p}(t)[x, y]$ を求める.

の項のうち,

ムに選び,

3.

$C$

$q_{j}(t)x^{i}y^{j}((i,j)\neq(O, 0))$ の形をしたもので $c_{ij}(t)$ が $F_{p}$$c_{ij}(t)$を通分し, その分子を $C(\in F_{p}[t])$ とする.

を $F_{p}[t]$ で因数分解し,る正規形 $n$ が,の要素でないものをランダ$F_{p}[t]$

$t$

の次数が

$\ell$

以上の既約因子の集合を$\hat{G}$とする.

$R_{1}$の$\hat{G}$

の要素

$g$

に関す

の要素となるものを選ぶ.

4 多項式 $n(t)=n_{k-1}t^{k-1}+\cdots+n_{1}t+n_{0}\in F_{p}[t]$ とおき $m=n_{0}||n_{1}||\cdots||n_{k-1}$ を出力して修了.

各簡約ステップで生じる有理式に関する多項式部分を, 通分でまとめてしまうことなく処理を進める必要がある.

$m(t)$ を $F_{p}(t)[x, y]$ の表現ではなく,と, 暗号文 $F$ の$t$$F_{p}[x, y, t]$で一意的に求めるためには,

定理 4提案アルゴリズムアルゴリズム 2 の中で生成される多項式 $g(t),$ $n(t)$ は, 秋山-後藤代数曲面公開鍵暗号での暗号化/復号の際に用いられる多項式 $f(t)$ , 平文から得られる多項式 $m(t)$ にそれぞれ一致している. すな
わち, 出力された平文は正しいものである.

122
例6

主係数が $LC(X_{B})=t(1+t+t^{4})$ であるから, モニックにするための変換 $\overline{X}_{B}(x, y, t):=X_{B}(x, y, t)/LC(X_{B})$を施す. ここで, アルゴリズムは $F_{p}(t)[x, y](t$ に関する有理式体上の $x,$$y$に関する多項式環. この例では$p=2)$ で実行されることに注意されたい.
$F_{B}(x, y, t)$$arrow^{*}$$R_{1}(x, y, t)(\in F_{2}(t)[x, y])$$\overline{X}_{B}(x,y,t)$

ここで, 分母には $t^{2}(1+t+t^{4})^{3}$ があらわれている.

次のリストは,$R_{1}(x,y, t)$の非零の項鞠

$x^{i}y^{j}$における果 j の集合の各要素をそれぞれ通分して$F_{2}$

上で因数分解して分子のみ取り出した集合である. 最初の要素は coo の分子である.
$t(1+t+t^{2})(1+t+t^{4})(1+t^{2}+t^{3}+t^{4}+t^{5})(1+t^{3}+t^{4}+t^{6}+t^{7}+t^{8}+t^{9}+t^{10}+t^{11}+t^{12}+t^{13}+t^{14}+t^{15})(1+t^{2}+$$t^{3}+t^{4}+t^{8}+t^{9}+t^{11}+t^{13}+t^{17}+t^{20}+t^{22}+t^{23}+t^{24}+t^{25}+t^{27}+t^{29}+t^{30}+t^{31}+t^{36}+t^{37}+t^{38}+t^{39}+t^{40}+t^{41}+$$t^{43}+t^{47}+t^{49}),$$(1+t)^{5}(1+t+t^{2})(1+t+t^{4})(1+t^{3}+t^{4}+t^{5}+t^{6}+t^{7}+t^{8}+t^{10}+t^{12})(1+t^{2}+t^{3}+t^{4}+t^{5}+t^{6}+$$t^{8}+t^{9}+t^{11}+t^{13}+t^{14})(1+t+t^{2}+t^{4}+t^{7}+t^{9}+t^{10}+t^{11}+t^{14}+t^{17}+t^{22}+t^{23}+t^{25}+t^{26}+t^{27}+t^{28}+t^{32}+t^{34}+$$t^{36}+t^{38}+t^{40}),$ $t^{2}(1+t+t^{4})(1+t^{3}+t^{4})^{2}(1+t+t^{2}+t^{4}+t^{7}+t^{9}+t^{10}+t^{11}+t^{14}+t^{17}+t^{22}+t^{23}+t^{25}+t^{26}+t^{27}+$$t^{28}+t^{32}+t^{34}+t^{36}+t^{38}+t^{40}),$ $t^{3}(1+t)^{3}(1+t+t^{2})(1+t+t^{4})(1+t+t^{2}+t^{4}+t^{7}+t^{9}+t^{10}+t^{11}+t^{14}+t^{17}+t^{22}+$$t^{23}+t^{25}+t^{26}+t^{27}+t^{28}+t^{32}+t^{34}+t^{36}+t^{38}+t^{40})$,$\cdot$. . . . . . . . . . .... , $(1+t+t^{2}+t^{6}+t^{7}+t^{8}+t^{9})(1+t+t^{2}+$$t^{4}+t^{7}+t^{9}+t^{10}+t^{11}+t^{14}+t^{17}+t^{22}+t^{23}+t^{25}+t^{26}+t^{27}+t^{28}+t^{32}+t^{34}+t^{36}+t^{38}+t^{40}),$ $(1+t)(1+t+t^{5}+$$t^{6}+t^{8})(1+t+t^{2}+t^{4}+t^{7}+t^{9}+t^{10}+t^{11}+t^{14}+t^{17}+t^{22}+t^{23}+t^{25}+t^{26}+t^{27}+t^{28}+t^{32}+t^{34}+t^{36}+t^{38}+t^{40})\}$

最初の要素$c_{00}$.

を除く全ての要素が, 共通する因子 $1+t+t^{2}+t^{4}+t^{7}+t^{9}+t^{10}+t^{11}+t^{14}+t^{17}+t^{22}+$をもつことがわかる. (すなわち $f(t)$ を検出することができた). 実際の計算では, 最初の要素以外から任意の 2 つの要素を選んで GCD を計算するだ$t^{23}+t^{25}+t^{26}+t^{27}+t^{28}+t^{32}+t^{34}+t^{36}+t^{38}+t^{40}):=g(t)$けでよい. 最後に, $R(x, y, t)$ の $g(t)(=f(t))$ に関する正規形を計算して平文 $m(t)$ を得る.

5

まとめ

秋山-後藤代数曲面公開鍵暗号に対する内山-徳永の攻撃手法とは, 公開鍵がある条件を満たすとき, 公開
鍵と暗号文から. $F_{p}[x, y, t]$ における簡約を利用して平文を得ることができるというものである. 一方, 提案攻撃法では, $F_{p}[x, y,t]$ ではなく $F_{p}(t)[x, y]$ で行なえるように拡張することで, 任意の公開鍵に対して適用可能となっている. 提案手法に関する証明および Gr\"obner 基底を用いた攻撃法の提案とその証明については, [8] を参照されたい.

参考文献[1] A. Akiyama, Y. Goto:AConstruction of an Algebraic Surface Public-key Cryptosystem. CD-ROM
2E ンレ 3, PP.925-930Symposium on Cryptoyaphy and Information Security (SCIS2005) January 2005.
[2] Algebraic surface public key cryptosystem, opened to the general public at website, February 2005 :About To8hiba $>Technologiae>Corporate$ Research&Development Center $>Resear\bm{i}$ and Development $>R\epsilon eearch$ News
http: $//www$ . toshiba. co. $jp/rdc/rd/topics_{-}e_{-}05$ . htm#050206
http: $//www$ . toshiba. co. $jp/rdc/rd/detai1_{-}j/0502_{-}06$ . htm

123[3] A. Akiyama, Y. Goto : A Security Analysis for a Public-key Cryptosystem using Algebraic Surfaces.
CD-ROM 2A3-l, Symposium on Cryptography and Information Security (SCIS2006) January 2006.
[4] K. Akiyama, Y. Goto: A Public-key Cryptosystem using Algebraic Surfaces. Workshop Record of theInternational Workshop on Post-Quantum Cryptography (PQCrypto2006), pp.119-138, May 2006.
[5] S. Uchiyama, H. Tokunaga: 代数曲面を用いた公開鍵暗号の安全性について. CD-ROM 2Cl-2, Symposium on CryptograPhy and Information Security (SCIS2007), January 2007. (written in Japanese)[6] Cryptography Research and Evaluation Committees(CRYPTREC) : CRYPTREC Report 2006; Report of the CryPtographic Technique Monitoring Subcommittee, March 2007.

.

http: $//www.ipa$ go. $jP/security/enc/CRYPTREC/fy18/documents/c06_{-}wat_{-}f$ inal. pdf[7] D. Cox, J. Little and D. O’Shea: Ideals, Varieties, and Algoriths: An Introduction to Computational
Algebraic Geometry and Commutative Algebra, Second Edition, Springer-Verlag.
[8] M. Iwami :A Reduction Attack on Algebraic Surface Public-Key Cryptosystems : 査読中.