(57)【特許請求の範囲】
【請求項１】
楕円曲線の同型類を頂点集合とし、前記楕円曲線間のＬ≧３であるＬ−同種写像を辺集合とするグラフにおいて、入力値に基づき後戻りすることなく頂点間を移動させて出力値を計算する暗号装置であり、
移動元の頂点Ｅｉのｘ座標αｘｉを入力として、移動先の頂点Ｅｉ＋１に対する後戻り点のｘ座標βｘｉ＋１を移動元の頂点Ｅｉのｘ座標で表した式を利用して前記後戻り点のｘ座標βｘｉ＋１を計算した上で、３次方程式を解いて移動先の頂点Ｅｉ＋１のｘ座標αｘｉ＋１を計算することにより、前記移動先の頂点Ｅｉ＋１である楕円曲線の曲線情報を計算する曲線計算部と、
前記曲線計算部によって計算された前記曲線情報を用いて前記入力値に対する前記出力値を計算する出力値計算部と
を備える暗号装置。
【請求項２】
前記グラフは、楕円曲線間の３−同種写像を辺集合とし、
前記曲線計算部は、前記ｘ座標βｘｉ＋１が前記ｘ座標αｘｉの−３倍であることを利用して後戻り点のｘ座標βｘｉ＋１を計算する
請求項１に記載の暗号装置。
【請求項３】
前記曲線計算部は、カルダノの公式を用いて前記３次方程式を解く
請求項２に記載の暗号装置。
【請求項４】
前記曲線計算部は、ζを１の３乗根とした場合に、３次方程式の２つの３乗根ｕ，ｖがｖ＝−ζ／ｕとなることを利用して前記３次方程式を解く
請求項３に記載の暗号装置。
【請求項５】
前記曲線計算部は、前記移動元の頂点Ｅｉである楕円曲線ｙ２＝ｘ３＋Ａｉｘ＋ＢｉのＡｉ及びＢｉと、前記移動元の頂点Ｅｉのｘ座標αｘｉとを入力として、前記３次方程式を数１に示すように解いて、解λ０，λ１，λ２を計算し、前記解λ０，λ１，λ２から１つの解を選択して、選択された前記解を前記移動先の頂点Ｅｉ＋１のｘ座標αｘｉ＋１として決定する
請求項４に記載の暗号装置。
【数１】
0006614979.tif 000016
【請求項６】
前記曲線計算部は、前記移動元の頂点Ｅｉである楕円曲線ｙ２＝ｘ３＋Ａｉｘ＋ＢｉのＡｉ及びＢｉと、前記ｘ座標αｘｉとを入力として、前記移動先の頂点Ｅｉ＋１である楕円曲線ｙ２＝ｘ３＋Ａｉ＋１ｘ＋Ｂｉ＋１における曲線情報Ａｉ＋１及びＢｉ＋１を数２に示すように計算する
請求項５に記載の暗号装置。
【数２】
0006614979.tif 000017
【請求項７】
前記曲線計算部は、始点Ｅ０である楕円曲線ｙ２＝ｘ３＋Ａ０ｘ＋Ｂ０における曲線情報Ａ０及びＢ０と、始点Ｅ０のｘ座標αｘ０と、ウォークデータω＝ｂ０ｂ１．．．ｂｎ−１とを入力として、ｋ＝０，．．．，ｎ−２の整数ｋについて昇順に、前記移動先の頂点Ｅｋ＋１である楕円曲線ｙ２＝ｘ３＋Ａｋ＋１ｘ＋Ｂｋ＋１における曲線情報Ａｋ＋１及びＢｋ＋１を計算するとともに、前記移動先の頂点Ｅｋ＋１のｘ座標αｘｋ＋１を決定し、決定されたｘ座標αｘｎ−１から前記移動先の頂点Ｅｎである楕円曲線ｙ２＝ｘ３＋Ａｎｘ＋Ｂｎにおける曲線情報Ａｎ及びＢｎを計算し、
前記出力値計算部は、前記曲線計算部によって計算された前記曲線情報Ａｎ及びＢｎから、前記移動先の頂点Ｅｎである楕円曲線のｊ不変量ｊｎを前記出力値として計算する
請求項６に記載の暗号装置。
【請求項８】
前記出力値計算部は、前記ｊ不変量ｊｎを前記ウォークデータωに対するハッシュ値として計算する
請求項７に記載の暗号装置。
【請求項９】
前記グラフは、複数の整数ＬについてのＬ−同種写像を辺集合とし、
前記曲線計算部は、３−同種写像の辺の移動を計算する場合に、前記ｘ座標βｘｉ＋１が前記ｘ座標αｘｉの−３倍であることを利用して、３次方程式を解く
請求項１に記載の暗号装置。
【請求項１０】
前記出力値計算部は、前記出力値として、ハッシュ値と、暗号文と、署名との少なくともいずれかを計算する
請求項１から９までのいずれか１項に記載の暗号装置。
【請求項１１】
楕円曲線の同型類を頂点集合とし、前記楕円曲線間のＬ≧３であるＬ−同種写像を辺集合とするグラフにおいて、入力値に基づき後戻りすることなく頂点間を移動させて出力値を計算する暗号方法であり、
暗号装置における曲線計算部が、移動元の頂点Ｅｉのｘ座標αｘｉを入力として、移動先の頂点Ｅｉ＋１に対する後戻り点のｘ座標βｘｉ＋１を移動元の頂点Ｅｉのｘ座標で表した式を利用して前記後戻り点のｘ座標βｘｉ＋１を計算した上で、３次方程式を解いて移動先の頂点Ｅｉ＋１のｘ座標αｘｉ＋１を計算することにより、前記移動先の頂点Ｅｉ＋１である楕円曲線の曲線情報を計算し、
前記暗号装置における出力値計算部が、計算された前記曲線情報を用いて前記入力値に対する前記出力値を計算する暗号方法。
【請求項１２】
楕円曲線の同型類を頂点集合とし、前記楕円曲線間のＬ≧３であるＬ−同種写像を辺集合とするグラフにおいて、入力値に基づき後戻りすることなく頂点間を移動させて出力値を計算する暗号プログラムであり、
曲線計算部が、移動元の頂点Ｅｉのｘ座標αｘｉを入力として、移動先の頂点Ｅｉ＋１に対する後戻り点のｘ座標βｘｉ＋１を移動元の頂点Ｅｉのｘ座標で表した式を利用して前記後戻り点のｘ座標βｘｉ＋１を計算した上で、３次方程式を解いて移動先の頂点Ｅｉ＋１のｘ座標αｘｉ＋１を計算することにより、前記移動先の頂点Ｅｉ＋１である楕円曲線の曲線情報を計算する曲線計算処理と、
出力値計算部が、前記曲線計算処理によって計算された前記曲線情報を用いて前記入力値に対する前記出力値を計算する出力値計算処理と
を行う暗号装置としてコンピュータを機能させる暗号プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、耐量子計算機暗号に関する。
【背景技術】
【０００２】
耐量子計算機暗号の１つとして、楕円曲線上の同種写像を利用した暗号がＪａｏらにより提案された（非特許文献１〜３）。同種写像には、パラメータＬがあり、これまでＹｏｓｈｉｄａらによって、Ｌ＝２の場合の高速化手法が提案されていた（非特許文献４）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Ｌ．Ｄｅ  Ｆｅｏ，  Ｄ．  Ｊａｏ  ａｎｄ  Ｊ．  Ｐｌｕｔ，  “Ｔｏｗａｒｄｓ  ｑｕａｎｔｕｍ−ｒｅｓｉｓｔａｎｔ  ｃｒｙｐｔｏｓｙｓｔｅｍｓ  ｆｒｏｍ  ｓｕｐｅｒｓｉｎｇｕｌａｒ  ｅｌｌｉｐｔｉｃ  ｃｕｒｖｅ  ｉｓｏｇｅｎｉｅｓ”，  Ｊ．  Ｍａｔｈ．  Ｃｒｙｐｔｏｌｏｇｙ，  ８（１），  ｐｐ．１-２９，  ２０１４
【非特許文献２】Ｄ．Ｊａｏ  ａｎｄ  Ｒ．Ｖｅｎｋａｔｅｓａｎ，  “Ｕｓｅ  ｏｆ  ｉｓｏｇｅｎｉｅｓ  ｆｏｒ  ｄｅｓｉｇｎ  ｏｆ  ｃｒｙｐｔｏｓｙｓｔｅｍｓ”，  ＵＳ  Ｐａｔｅｎｔ，  ７４９９５４４，  Ｍａｒｃｈ  ３，  ２００９
【非特許文献３】Ｄ．Ｊａｏ，  Ｐ．Ｌ．  Ｍｏｎｔｇｏｍｅｒｙ，  Ｒ．Ｖｅｎｋａｔｅｓａｎ  ａｎｄ  Ｖ．Ｂｏｙｋｏ，  “Ｓｙｓｔｅｍｓ  ａｎｄ  ｍｅｔｈｏｄｓ  ｆｏｒ  ｇｅｎｅｒａｔｉｏｎ  ａｎｄ  ｖａｌｉｄａｔｉｏｎ  ｏｆ  ｉｓｏｇｅｎｙ−ｂａｓｅｄ  ｓｉｇｎａｔｕｒｅｓ”，  ＵＳ  Ｐａｔｅｎｔ，  ７６１７３９７，  Ｎｏｖｅｍｂｅｒ  １０，  ２００９
【非特許文献４】Ｒ．  Ｙｏｓｈｉｄａ  ａｎｄ  Ｋ．  Ｔａｋａｓｈｉｍａ，  “Ｃｏｍｐｕｔｉｎｇ  ａ  ｓｅｑｕｅｎｃｅ  ｏｆ  ２−ｉｓｏｇｅｎｉｅｓ  ｏｎ  ｓｕｐｅｒｓｉｎｇｕｌａｒ  ｅｌｌｉｐｔｉｃ  ｃｕｒｖｅｓ”，  ＩＥＩＣＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｆｕｎｄａｍｅｎｔａｌｓ，  ９６−Ａ（１）：  ｐｐ．１５８−１６５，  ２０１３
【非特許文献５】Ｄ．Ｘ．Ｃｈａｒｌｅｓ，  Ｅ．Ｚ．  Ｇｏｒｅｎ  ａｎｄ  Ｋ．Ｅ．  Ｌａｕｔｅｒ，  “Ｃｒｙｐｔｏｇｒａｐｈｉｃ  ｈａｓｈ  ｆｕｎｃｔｉｏｎｓ  ｆｒｏｍ  ｅｘｐａｎｄｅｒ  ｇｒａｐｈｓ”，  Ｊ．  Ｃｒｙｐｔｏｌｏｇｙ，  ｖｏｌ．２２，  Ｎｏ．１  ｐｐ．９３−１１３．
【非特許文献６】Ｊ．  Ｖｅｌｕ，“Ｉｓｏｇｅｎｉｅｓ  ｅｎｔｒｅ  ｃｏｕｒｂｅｓ  ｅｌｌｉｐｔｉｑｕｅｓ”，Ｃ．Ｒ．  Ａｃａｄ．  Ｓｃ．  Ｐａｒｉｓ，  Ｓｅｒｉｅｓ  Ａ，  ｖｏｌ．  ２７３，  ｐｐ．２３８−２４１，１９７１．
【発明の概要】
【発明が解決しようとする課題】
【０００４】
Ｊａｏらの暗号では、Ｌ＝３の場合の演算も使っているが、この演算は遅かった。
この発明は、Ｌ≧３の場合における同種写像の計算効率を向上させ、Ｌ≧３の同種写像を利用した暗号の計算効率を向上させることを目的とする。
【課題を解決するための手段】
【０００５】
この発明に係る暗号装置は、
超特異楕円曲線の同型類を頂点集合とし、前記楕円曲線間のＬ≧３であるＬ−同種写像を辺の集合とするグラフにおいて、後戻りすることなく頂点間を移動させて出力値を計算する暗号装置であり、
移動元の頂点Ｅｉのｘ座標αｘｉを入力として、移動先の頂点Ｅｉ＋１に対する後戻り点のｘ座標βｘｉ＋１を移動元の頂点Ｅｉのｘ座標で表した式を利用して前記後戻り点のｘ座標βｘｉ＋１を計算した上で、３次方程式を解いて移動先の頂点Ｅｉ＋１のｘ座標αｘｉ＋１を計算することにより、前記移動先の頂点Ｅｉ＋１である楕円曲線の曲線情報を計算する曲線計算部と、
前記曲線計算部によって計算された前記曲線情報を用いて前記出力値を計算する出力値計算部と
を備える。
【発明の効果】
【０００６】
この発明では、後戻り点のｘ座標βｘｉ＋１を移動元の頂点Ｅｉのｘ座標で表した式を利用して後戻り点のｘ座標βｘｉ＋１を計算した上で、３次方程式を解く。これにより、後戻り点のｘ座標βｘｉ＋１を少ない計算量で計算でき、同種写像の計算効率を向上させることができる。
【図面の簡単な説明】
【０００７】
【図１】実施の形態１に係る暗号装置１０の構成図。
【図２】実施の形態１に係るグラフＧ及びウォークの説明図。
【図３】実施の形態１に係る３−同種写像列計算処理のフローチャート。
【図４】実施の形態１に係るＩｓｏｇＳｅｑアルゴリズムを示す図。
【図５】実施の形態１に係る３−同種写像計算処理のフローチャート。
【図６】実施の形態１に係るＩｓｏｇアルゴリズムを示す図。
【図７】変形例に係る暗号装置１０の構成図。
【発明を実施するための形態】
【０００８】
実施の形態１．
＊＊＊前提＊＊＊
実施の形態１における暗号には、情報を第三者から秘匿する狭義の暗号だけでなく、情報の送信元のなりすまし、情報の改ざんの防止に用いられる署名も含む。また、実施の形態１における暗号には、狭義の暗号及び署名といった処理で用いられるハッシュ値を計算することも含む。
実施の形態１では、暗号の処理の具体例として、ハッシュ値を計算する処理を説明する。しかし、実施の形態１で説明した処理を応用して、非特許文献１〜３といった文献に記載された鍵共有、狭義の暗号、署名を実現することも可能である。
【０００９】
＊＊＊構成の説明＊＊＊
図１を参照して、実施の形態１に係る暗号装置１０の構成を説明する。
暗号装置１０は、暗号処理を実行するコンピュータである。
暗号装置１０は、プロセッサ１１と、記憶装置１２と、インタフェース１３とを備える。プロセッサ１１は、信号線を介して他のハードウェアと接続され、これら他のハードウェアを制御する。
【００１０】
プロセッサ１１は、プロセッシングを行うＩＣ（Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）である。プロセッサ１１は、具体的には、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）、ＤＳＰ（Ｄｉｇｉｔａｌ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｏｒ）、ＧＰＵ（Ｇｒａｐｈｉｃｓ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）である。
【００１１】
記憶装置１２は、メモリ１２１と、ストレージ１２２とを備える。メモリ１２１は、具体的には、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）である。ストレージ１２２は、具体的には、ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）である。また、ストレージ１２２は、ＳＤ（Ｓｅｃｕｒｅ  Ｄｉｇｉｔａｌ）メモリカード、ＣＦ（ＣｏｍｐａｃｔＦｌａｓｈ）、ＮＡＮＤフラッシュ、フレキシブルディスク、光ディスク、コンパクトディスク、ブルーレイ（登録商標）ディスク、ＤＶＤといった可搬記憶媒体であってもよい。
【００１２】
インタフェース１３は、暗号装置１０の外部からデータの入力を受け付け、外部へデータを出力するためのインタフェースである。インタフェース１３は、具体的には、キーボードといった入力装置と、ディスプレイといった出力装置とを接続するＵＳＢ（Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓ）、ＰＳ／２、ＨＤＩＭ（Ｈｉｇｈ−Ｄｅｆｉｎｉｔｉｏｎ  Ｍｕｌｔｉｍｅｄｉａ  Ｉｎｔｅｒｆａｃｅ）といったコネクタである。また、インタフェース１３は、具体的には、外部からネットワークを介して送信されたデータを送受信するＮＩＣ（Ｎｅｔｗｏｒｋ  Ｉｎｔｅｒｆａｃｅ  Ｃａｒｄ）であってもよい。
【００１３】
暗号装置１０は、機能構成要素として、受付部２１と、曲線計算部２２と、出力値計算部２３とを備える。受付部２１と、曲線計算部２２と、出力値計算部２３との各部の機能はソフトウェアにより実現される。
記憶装置１２のストレージ１２２には、暗号装置１０の各部の機能を実現するプログラムが記憶されている。このプログラムは、プロセッサ１１によりメモリ１２１に読み込まれ、プロセッサ１１によって実行される。これにより、暗号装置１０の各部の機能が実現される。
【００１４】
プロセッサ１１によって実現される各部の機能の処理の結果を示す情報とデータと信号値と変数値は、メモリ１２１、又は、プロセッサ１１内のレジスタ又はキャッシュメモリに記憶される。以下の説明では、プロセッサ１１によって実現される各部の機能の処理の結果を示す情報とデータと信号値と変数値は、メモリ１２１に記憶されるものとして説明する。
【００１５】
プロセッサ１１によって実現される各機能を実現するプログラムは、記憶装置１２に記憶されているとした。しかし、このプログラムは、磁気ディスク、フレキシブルディスク、光ディスク、コンパクトディスク、ブルーレイ（登録商標）ディスク、ＤＶＤといった可搬記憶媒体に記憶されてもよい。
【００１６】
図１では、プロセッサ１１は、１つだけ示されていた。しかし、プロセッサ１１は、複数であってもよく、複数のプロセッサ１１が、各機能を実現するプログラムを連携して実行してもよい。
【００１７】
＊＊＊動作の説明＊＊＊
図２から図６を参照して、実施の形態１に係る暗号装置１０の動作を説明する。
実施の形態１に係る暗号装置１０の動作は、実施の形態１に係る暗号方法に相当する。また、実施の形態１に係る暗号装置１０の動作は、実施の形態１に係る暗号プログラムの処理に相当する。
ここでは、（１）Ｐｉｚｅｒグラフとハッシュ関数と、（２）楕円曲線上の同種写像とを説明した上で、（３）暗号装置１０の動作を説明する。
【００１８】
＊＊（１）Ｐｉｚｅｒグラフとハッシュ関数＊＊
ここでは、（１−１）エクスパンダーグラフと、（１−２）Ｐｉｚｅｒグラフと、（１−３）後戻りしないウォークと、（１−４）ハッシュ関数の安全性とについて説明する。
【００１９】
＊（１−１）エクスパンダーグラフ＊
Ｇ＝（Ｖ，ε）を頂点集合Ｖと辺集合εとをもつグラフとする。＃Ｕ≧＃Ｖ／２を満たす任意の部分集合Ｕ⊂Ｖに対し、Ｕの境界集合Γ（Ｕ）が＃Γ（Ｕ）≧ｃ＃Ｕをみたすとき、グラフＧは拡張率ｃ＞０のエクスパンダーグラフと言われる。ここで、Γ（Ｕ）：＝｛ｖ∈Ｖ｜∃ｕ∈Ｕ，｛ｕ，ｖ｝∈ε｝である。また、＃Ｕは、Ｕの個数である。同様に、＃Ｖ及び＃Γは、それぞれＶの個数及びΓの個数である。
任意のエクスパンダーグラフは、完全グラフである。エクスパンダーグラフ上のランダムウォークは、急撹拌性を持つ。Ｏ（ｌｏｇ＃Ｖ）ステップのランダムウォークをした後の終点の分布は、グラフ上の一様分布に近似する。
【００２０】
＊（１−２）Ｐｉｚｅｒグラフ＊
ＰｉｚｅｒグラフＧ＝（Ｖ，ε）は、体Ｆｐ２上の超特異楕円曲線の同型類を頂点集合Ｖに持つ。ｐ２は、ｐ２のことであり、ｐは素数位数である。各頂点は、ｊ−不変量又は代表元Ｅで表される。また、辺集合εは、頂点間のＬ−同種写像の集合である。このグラフは、各頂点がＬ＋１個の辺を持つ。頂点を楕円曲線Ｅで表すとき、頂点である楕円曲線Ｅから出る辺は、頂点である楕円曲線ＥのＬ＋１個のＬ等分点と対応している。頂点である楕円曲線Ｅから出るＬ＋１個の各辺の端点について、頂点である楕円曲線Ｅと異なる点は位数Ｌの部分群Ｃ⊂Ｅ［Ｌ］を用いてＥ／Ｃで表される。
グラフＧは、急撹拌性を持つことが知られている。特に、これはエクスパンダーグラフの特別な種類であるラマヌジャングラフと呼ばれる。詳細は、非特許文献５等に記載されている。
【００２１】
＊（１−３）後戻りしないウォーク＊
ハッシュ関数への入力値は、グラフＧを後戻りせずにウォークする道順として使用される。そして、そのウォークの終点がハッシュ関数の出力値とされる。グラフＧは（Ｌ＋１）−正則グラフなので、各頂点に接続している辺の数はＬ＋１である。したがって、始点を除いた各点では、次に進む頂点の候補が後戻りとなる頂点を除いたＬ個存在する。
【００２２】
＊（１−４）ハッシュ関数の安全性＊
エクスパンダーグラフを用いたハッシュ関数には、Ｃａｙｌｅｙグラフを用いる場合とＰｉｚｅｒグラフを用いる場合との２種類がある。Ｃａｙｌｅｙグラフを用いたハッシュ関数には、Ｚｅｍｏｒハッシュ関数とＬＰＳハッシュ関数と等があるが、そのほとんどはすでに攻撃法が見つかっており安全ではない。しかし、Ｐｉｚｅｒグラフを用いたハッシュ関数には、まだ攻撃法が見つかっていない。
ハッシュ関数の安全性は、衝突困難性と原像計算困難性という２つの性質によって保障される。衝突困難性とは、同じハッシュ値をもつ２つの異なる入力を探すことが困難なことである。原像計算困難性とは与えられたハッシュ値を持つような入力を探すことが困難なことである。
【００２３】
Ｐｉｚｅｒグラフにおけるハッシュ関数の安全性は次の３つの問題の困難性により保障される。
問題１．体Ｆｐ２上の超特異楕円曲線Ｅ１，Ｅ２と、その間の次数Ｌｎの異なる同種写像ｆ１：Ｅ１→Ｅ２，ｆ２：Ｅ１→Ｅ２を構成する。
問題２．体Ｆｐ２上の超特異楕円曲線Ｅが与えられたとき、次数Ｌ２ｎの自己準同型写像ｆ：Ｅ→Ｅ（ｆはＬｎ倍写像でない）を構成する。
問題３．体Ｆｐ２上の超特異楕円曲線Ｅ１，Ｅ２が与えられたとき、次数Ｌｎの同種写像ｆ：Ｅ１→Ｅ２を構成する。
ハッシュ関数の衝突を計算できれば問題１，問題２は解かれる。また、ハッシュ関数の原像計算ができれば問題３は解かれる。
同種写像問題は、楕円曲線間の同種写像問題、超特異楕円曲線間の同種写像問題に分類される。現在知られている最も効率的な攻撃の計算量は、古典計算機を用いた場合は、それぞれＯ（４√ｐ）、Ｏ（√ｐ）であり、量子計算機を用いた場合は、それぞれＬｐ［１／２，（√３）／２］、Ｏ（４√ｐ）である。
【００２４】
＊＊（２）楕円曲線上の同種写像＊＊
ここでは、（２−１）楕円曲線と、（２−２）Ｖｅｌｕの公式とについて説明する。
【００２５】
＊（２−１）楕円曲線＊
ｐを３より大きい素数とする。体Ｆｐ２上の楕円曲線Ｅは、Ｗｅｉｅｒｓｔｒａｓｓ標準形としてｙ２＝ｘ３＋Ａｘ＋Ｂ，Ａ，Ｂ∈Ｆｐ２，４Ａ３＋２７Ｂ２≠０で与えられる。楕円曲線Ｅのｊ−不変量ｊ（Ｅ）は、数１１で計算される。
【数１１】
0006614979.tif 000002
ｊ−不変量ｊ（Ｅ）＝ｊ∈Ｆ−ｐ（ｊ≠０，１７２８）となる楕円曲線Ｅは、数１２となる
【数１２】
0006614979.tif 000003
【００２６】
２つの楕円曲線が同じｊ−不変量をもつことは、それらが同型であることの必要十分条件である。楕円曲線ＥのＦ−ｐ有理点群をＥ（Ｆ−ｐ）＝｛（ｘ，ｙ）∈Ｆ−ｐ２｜ｙ２＝ｘ３＋Ａｘ＋Ｂ｝∪｛ＯＥ｝とする。ここで、ＯＥは、楕円曲線Ｅの無限遠点を表す。整数ｎに対し、楕円曲線Ｅのｎ等分点の集合はＥ［ｎ］＝｛Ｐ∈Ｅ（Ｆ−ｐ）｜［ｎ］Ｐ＝ＯＥ｝である。Ｆ−ｐ上の２つの楕円曲線Ｅ１，Ｅ２に対し、準同型φ：Ｅ１→Ｅ２はＯＥ１をＯＥ２へ移す代数曲線の射である。非零な準同型は同種写像と呼ばれ、核の濃度がＬとなるｓｅｐａｒａｂｌｅな同種写像はＬ−同種写像と呼ばれる。Ｅ（Ｆ−ｐ）上に位数ｐの点が存在しないようなＦ−ｐ上の楕円曲線を超特異であるという。超特異楕円曲線のｊ−不変量は常にＦｐ２に含まれる。
【００２７】
＊（２−２）Ｖｅｌｕの公式＊
２−同種写像と３−同種写像とのＶｅｌｕの公式（非特許文献６）を用いた計算について説明する。Ｖｅｌｕの公式とは、楕円曲線ＥとＣ＝ｋｅｒφが与えられたとき、同種写像φ：Ｅ→Ｅ’とＥ’との定義式を明示的に計算する公式である。この公式は任意の次数Ｌについて成立する。
ここでは、Ｌが２又は３のときを説明する。Ｃを楕円曲線Ｅ上の位数２又は３の部分群とする。このとき、Ｃ＝ｋｅｒφとなる同種写像φ：Ｅ→Ｅ’が一意に存在する。Ｅ’＝Ｅ／Ｃと表す。
【００２８】
Ｌ＝２の場合、Ｃ＝＜（α，０）＞⊂Ｅ［２］を楕円曲線Ｅ上の位数２の部分群とすると、楕円曲線Ｅ／Ｃは数１３で与えられる。
【数１３】
0006614979.tif 000004
さらに、同種写像φ：Ｅ→Ｅ／Ｃは、数１４で与えられる。ここで、φ（ＯＥ）＝ＯＥ／Ｃ，φ（（α，０））＝ＯＥ／Ｃである。
【数１４】
0006614979.tif 000005
【００２９】
Ｌ＝３の場合、Ｃ＝＜（αｘ，αｙ）＞⊂Ｅ［３］を楕円曲線Ｅ上の位数３の部分群とすると、楕円曲線Ｅ／Ｃは数１５で与えられる。
【数１５】
0006614979.tif 000006
さらに、同種写像φ：Ｅ∋（ｘ，ｙ）→（Ｘ，Ｙ）∈Ｅ／Ｃは、数１６で与えられる。ここで、φ（ＯＥ）＝ＯＥ／Ｃ，φ（（αｘ，αｙ））＝ＯＥ／Ｃである。
【数１６】
0006614979.tif 000007
【００３０】
Ｌ＝２，３の両方において、楕円曲線Ｅが超特異であればＥ／ＣもまたＦｐ２上定義される。また、明らかに超特異楕円曲線Ｅに対し同種写像φもＦｐ２上で定義される。
【００３１】
＊＊（３）暗号装置１０の動作＊＊
暗号装置１０は、ハッシュ関数への入力値を、グラフＧを後戻りせずにウォークする道順として使用し、そのウォークの終点をハッシュ関数の出力値とする。実施の形態１では、Ｌ＝３の場合について説明する。つまり、実施の形態１では、グラフＧにおいて、頂点である楕円曲線Ｅから出る辺が、頂点である楕円曲線Ｅの４個の３等分点と対応している場合について説明する。
なお、以下の説明で、グラフＧとは、（１−２）で説明した、体Ｆｐ２上の超特異楕円曲線の同型類を頂点集合Ｖとし、頂点間のＬ−同種写像を辺集合εとしたＰｉｚｅｒのラマヌジャングラフである。
【００３２】
ここでは、（３−１）入力値に従いグラフＧをウォークする際に使用するセレクター関数を定義し、（３−２）３等分点に関する記法と、（３−３）３等分点について成り立つ性質とを説明する。そして、（３−１）から（３−３）を踏まえた上で、（３−４）３−同種写像列の計算法を説明する。
実施の形態１に係る暗号装置１０は、３−同種写像列を計算することにより、入力値に対応するハッシュ値を計算する。
【００３３】
＊（３−１）セレクター関数＊
上述した通り、グラフＧは（Ｌ＋１）−正則グラフなので、各頂点に接続している辺の数はＬ＋１である。そのため、図２に示すように、Ｌ＝３の場合、グラフＧは４−正則グラフなので、各頂点に接続している辺の数は４本である。したがって、始点Ｅ０を除いた各点Ｅｉ（ｉ＝１，．．．，ｎ−１）では、次に進む頂点の候補が後戻りとなる後戻り点を除いた３個存在する。
暗号装置１０は、ｉ＝１，．．．，ｎ−１の各整数についての頂点Ｅｉから次に進む候補となる３つの頂点と接続された３つの辺に対して、値ｂ∈｛０，１，２｝を割り当てる。そして、暗号装置１０は、次に進む候補となる３つの頂点λ０，λ１，λ２∈Ｆｐ２と、値ｂ∈｛０，１，２｝に対して、Ｆｐ２の順序を用いて、数１７のようにセレクター関数ｓｅｌｅｃｔ（３）を定義し、ウォークデータω＝ｂ０ｂ１．．．ｂｎ−１∈｛０，１，２｝ｎ及びセレクター関数ｓｅｌｅｃｔ（３）により次に進む移動先の頂点Ｅｉ＋１を決定する。ここで、Ｆｐ２の順序としては、Ｆｐ２＝Ｆｐ［τ］２＝Ｆｐτ＋Ｆｐ＝〜（Ｆｐ）２となる生成元τを固定し、（Ｆｐ）２での自然な辞書式順列を用いる。
【数１７】
0006614979.tif 000008
【００３４】
始点Ｅ０では、３等分点を任意に選ぶことができる。そのため、暗号装置１０は、数１８に示すセレクター関数ｓｅｌｅｃｔ０（３）を用いて、始点Ｅ０のｘ座標αｘ０と、始点Ｅ０の後戻り点のｘ座標βｘ０とを決定する。なお、ψ３（ｘ）＝３ｘ４＋６Ａ０ｘ２＋１２Ｂ０ｘ−Ａ０２＝０の４つの根をλ０，λ１，λ２，λ３∈Ｆｐ２（λ０≦λ１≦λ２≦λ３）とする。
【数１８】
0006614979.tif 000009
【００３５】
＊（３−２）３等分点に関する記法＊
ウォークデータω＝ｂ０ｂ１．．．ｂｎ−１∈｛０，１，２｝ｎに対応して、頂点Ｅｉ上の４つの３等分点の表記を次のように固定する。
（αｘｉ，αｙｉ）は、ｉ番目の同種写像φｉに関係のある点である。（βｘｉ，βｙｉ）は、ｉ番目の後戻り点である。（γｘｉ，γｙｉ）及び（δｘｉ，δｙｉ）は、残りの２点である。
【００３６】
＊（３−３）３等分点について成り立つ性質＊
（性質１）
（αｘｉ，αｙｉ），（βｘｉ，βｙｉ），（γｘｉ，γｙｉ），（δｘｉ，δｙｉ）を楕円曲線Ｅｉの３等分点とし、φｉ：Ｅｉ→Ｅｉ／ＣをＣ＝＜（αｘｉ，αｙｉ）＞としたときの３−同種写像とする。このとき、φｉ（βｘｉ，βｙｉ），φｉ（γｘｉ，γｙｉ），φｉ（δｘｉ，δｙｉ）は、Ｅｉ＋１の後戻り点である。
【００３７】
（性質２）
Ｅｉ＋１上の後戻り点のｘ座標βｘｉ＋１は、βｘｉ＋１＝−３αｘｉにより与えられる。
【００３８】
＊（３−４）３−同種写像列計算処理＊
図３及び図４を参照して、３−同種写像列計算処理を説明する。
図４に示すＩｓｏｇＳｅｑアルゴリズムによって３−同種写像列が計算される。
【００３９】
ステップＳ１の入力値受付処理（図４のＩｎｐｕｔ参照）では、受付部２１は、入力値及び始点Ｅ０のｊ不変量ｊ０を受け付ける。受付部２１は、受け付けられた入力値を、ウォークデータω＝ｂ０ｂ１．．．ｂｎ−１（ｂｉ∈｛０，１，２｝，ｉ＝０，．．．，ｎ−１）に変換する。
具体的には、受付部２１は、インタフェース１３を介して、外部から入力値を受け付ける。具体例としては、ユーザにより入力装置が操作されて入力された入力値を、受付部２１がインタフェース１３を介して受け付ける、あるいは、通信装置を介して送信された入力値を受付部２１がインタフェース１３を介して受け付ける。また、受付部２１は、初期の楕円曲線Ｅ０のｊ不変量ｊ０をメモリ１２１から読み出す。なお、始点Ｅ０のｊ不変量ｊ０は、入力値とともに外部から受け付けられるとしてもよい。
そして、受付部２１は、入力値を３進数で表すことにより、入力値をウォークデータωに変換する。受付部２１は、３進数で表された入力値の桁数をｎとして、３進数で表された入力値の上位の桁から、その桁の値を値ｂ０，値ｂ１，．．．，値ｂｎ−１と順に割り当てる。受付部２１は、入力値が基準値以上の値になるように、入力値を表すビット列に固定のビット列を追加した上で、３進数に変換してもよい。
【００４０】
ステップＳ２の初期処理（図４の（１）参照）では、曲線計算部２２は、ステップＳ１で受け付けられた始点Ｅ０のｊ不変量ｊ０を入力として、始点Ｅ０である楕円曲線ｙ２＝ｘ３＋Ａ０ｘ＋Ｂ０における曲線情報Ａ０及びＢ０を、数１２に基づき計算する。曲線情報Ａ０及びＢ０を計算するということは、楕円曲線Ｅ０を計算するということに相当する。
また、曲線計算部２２は、計算された曲線情報Ａ０及びＢ０と、ステップＳ１で入力値から変換されたウォークデータωに含まれる値ｂ０とを入力として、数１８に示すセレクター関数ｓｅｌｅｃｔ０（３）により、始点Ｅ０のｘ座標αｘ０と、始点Ｅ０の後戻り点のｘ座標βｘ０とを決定する。
曲線計算部２２は、計算されたＡ０及びＢ０と、始点Ｅ０のｘ座標αｘ０と、始点Ｅ０の後戻り点のｘ座標βｘ０とをメモリ１２１に書き込む。
【００４１】
ステップＳ３の３−同種写像計算処理（図４の（２）〜（４）参照）では、曲線計算部２２は、ｉ＝０，．．．，ｎ−２の整数ｉについて昇順に、移動先の頂点Ｅｉ＋１である楕円曲線ｙ２＝ｘ３＋Ａｉ＋１ｘ＋Ｂｉ＋１における曲線情報Ａｉ＋１及びＢｉ＋１を計算するとともに、移動先の頂点Ｅｉ＋１のｘ座標αｘｉ＋１を決定する。
【００４２】
図５及び図６を参照して、ステップＳ３の３−同種写像計算処理について説明する。
ステップＳ３では、ｉ＝０，．．．，ｎ−２の整数ｉについて昇順に、Ａｉ及びＢｉと、移動元の頂点Ｅｉのｘ座標αｘｉと、値ｂｉ＋１とを入力として、図６に示すＩｓｏｇアルゴリズムが呼び出され、Ａｉ＋１及びＢｉ＋１と、移動先の頂点Ｅｉ＋１のｘ座標αｘｉ＋１とが計算される。
【００４３】
ステップＳ３１の曲線計算処理（図６の（１）参照）では、曲線計算部２２は、移動元の頂点Ｅｉである楕円曲線の曲線情報Ａｉ及びＢｉと、移動元の頂点Ｅｉのｘ座標αｘｉとから、数１５に基づき、移動先の頂点Ｅｉ＋１である楕円曲線の曲線情報Ａｉ＋１及びＢｉ＋１を計算する。
具体的には、曲線計算部２２は、曲線情報Ａｉ及びＢｉと、移動元の頂点Ｅｉのｘ座標αｘｉとをメモリ１２１から読み出す。そして、曲線計算部２２は、読み出された曲線情報Ａｉ及びＢｉと、移動元の頂点Ｅｉのｘ座標αｘｉとを入力として、数１５から得られる数１９により、曲線情報Ａｉ＋１及びＢｉ＋１を計算する。曲線計算部２２は、計算された曲線情報Ａｉ＋１及びＢｉ＋１をメモリ１２１に書き込む。
【数１９】
0006614979.tif 000010
【００４４】
ステップＳ３２の３次方程式計算処理（図６の（２）参照）では、曲線計算部２２は、移動先の頂点Ｅｉ＋１のｘ座標αｘｉ＋１の候補となる３次方程式の解λ１，λ２，λ３を計算する。
【００４５】
具体的には、曲線計算部２２は、Ａｉ及びＢｉと、移動元の頂点Ｅｉのｘ座標αｘｉとをメモリ１２１から読み出す。
そして、まず、曲線計算部２２は、読み出されたｘ座標αｘｉを入力として、（３−３）３等分点について成り立つ性質で説明した性質１，２に従い、移動先の頂点Ｅｉ＋１上の後戻り点のｘ座標βｘｉ＋１を、βｘｉ＋１＝−３αｘｉにより計算する。
次に、曲線計算部２２は、３次方程式ｘ３＋ｕｘ２＋ｖｘ＋ｗ＝０を解いて、（βｘｉ＋１，βｙｉ＋１）以外の３等分点のｘ座標を計算する。ここで、ｕ＝βｘｉ＋１であり、ｖ＝２Ａｉ＋１＋（βｘｉ＋１）２であり、ω＝４Ｂｉ＋１＋２Ａｉ＋１βｘｉ＋１＋（βｘｉ＋１）３である。
この際、曲線計算部２２は、カルダノの公式を用いて３次方程式を解く。つまり、ｘ２＋ｘ＋１＝０の解を、ω０とする。そして、数２０に示すｔ１，ｔ２，ｔ３に対して数２０に示すｕ，ｖとすると、求める解は、数２１になる。
【数２０】
0006614979.tif 000011
【数２１】
0006614979.tif 000012
これに対して、曲線計算部２２は、数１５と、βｘｉ＋１＝−３αｘｉとを代入する。そして、曲線計算部２２は、ζを１の３乗根とした場合に、３次方程式の２つの３乗根ｕ，ｖがｖ＝−ζ／ｕとなることを利用して、３次方程式を解く。数２２に示すζ１，ζ２，ζ３に対して数２２に示すｕ，ｖとすると、解λ０，λ１，λ２は数２３になる。
【数２２】
0006614979.tif 000013
【数２３】
0006614979.tif 000014
【００４６】
ステップＳ３３の座標決定処理（図６の（３）参照）では、曲線計算部２２は、計算された解λ０，λ１，λ２と、ステップＳ１で入力値から変換されたウォークデータωに含まれる値ｂｉ＋１とを入力として、数１７に示すセレクター関数ｓｅｌｅｃｔ（３）により、移動先の頂点Ｅｉ＋１のｘ座標αｘｉ＋１を決定する。曲線計算部２２は、決定されたｘ座標αｘｉ＋１をメモリ１２１に書き込む。
【００４７】
ステップＳ４の終了処理（図４の（５）参照）では、曲線計算部２２は、ステップＳ３で決定された頂点Ｅｎ−１のｘ座標αｘｎ−１から、移動先の頂点Ｅｎである楕円曲線ｙ２＝ｘ３＋Ａｎｘ＋Ｂｎにおける曲線情報Ａｎ及びＢｎを、数１５に基づき計算する。
具体的には、曲線計算部２２は、曲線情報Ａｎ−１及びＢｎ−１と、移動元の頂点Ｅｎ−１のｘ座標αｘｎ−１とをメモリ１２１から読み出す。そして、曲線計算部２２は、読み出された曲線情報Ａｎ−１及びＢｎ−１と、移動元の頂点Ｅｎ−１のｘ座標αｘｎ−１とを入力として、数１５から得られる数２４により、曲線情報Ａｎ及びＢｎを計算する。曲線計算部２２は、計算された曲線情報Ａｎ及びＢｎをメモリ１２１に書き込む。
【数２４】
0006614979.tif 000015
【００４８】
ステップＳ５の出力値計算処理（図４のＯｕｔｐｕｔ参照）では、出力値計算部２３は、ステップＳ４で計算された曲線情報Ａｎ及びＢｎをメモリ１２１から読み出す。そして、出力値計算部２３は、頂点Ｅｎである楕円曲線のｊ不変量ｊｎを数１１に基づき計算する。出力値計算部２３は、計算されたｊ不変量ｊｎを、ステップＳ１で受け付けられた入力値に対するハッシュ値として出力する。
【００４９】
＊＊＊実施の形態１の効果＊＊＊
以上のように、実施の形態１に係る暗号装置１０は、３−同種写像列を計算することにより、入力値に対するハッシュ値を計算した。３−同種写像列を計算する際、暗号装置１０は、移動先の頂点Ｅｉ＋１に対する後戻り点のｘ座標βｘｉ＋１が、移動元の頂点Ｅｉのｘ座標αｘｉのみを変数として表したβｘｉ＋１＝−３αｘｉを用いて、後戻り点のｘ座標βｘｉ＋１を計算した。これにより、後戻り点のｘ座標βｘｉ＋１の計算量を少なくできる。その結果、同種写像の計算効率を向上させることができる。
【００５０】
また、実施の形態１に係る暗号装置１０は、３−同種写像列を計算する際、一般の多項式解法アルゴリズムではなく、カルダノの公式を用いて３次方程式を解いた。これにより、３次方程式の計算量を少なくできる。その結果、同種写像の計算効率を向上させることができる。
【００５１】
また、実施の形態１に係る暗号装置１０は、３−同種写像列を計算する際、ζを１の３乗根とした場合に、３次方程式の２つの３乗根ｕ，ｖがｖ＝−ζ／ｕとなることを利用して、３次方程式を解いた。これにより、３乗根の計算を１回減らすことができ、３次方程式の計算量を少なくできる。その結果、同種写像の計算効率を向上させることができる。
【００５２】
＊＊＊他の構成＊＊＊
実施の形態１では、暗号処理の具体例として、ハッシュ値を計算する処理を説明した。そのため、出力値計算部２３は、出力値として、ハッシュ値を計算した。
しかし、実施の形態１で説明した処理を応用して、非特許文献１〜３といった文献に記載された鍵共有、狭義の暗号、署名を実現することも可能である。鍵共有及び狭義の暗号を実現する場合、出力値計算部２３は、出力値として、暗号文を計算する。また、署名を実現する場合、出力値計算部２３は、出力値として、電子署名を計算する。
つまり、出力値計算部２３は、出力値として、ハッシュ値と、暗号文と、署名との少なくともいずれかを計算する。
【００５３】
また、実施の形態１では、Ｌ＝３の場合について説明した。しかし、Ｌ＞３の場合についても、同様に、移動先の頂点Ｅｉ＋１に対する後戻り点のｘ座標βｘｉ＋１を移動元の頂点Ｅｉのｘ座標で表した式を利用して後戻り点のｘ座標βｘｉ＋１を計算することにより、後戻り点のｘ座標βｘｉ＋１の計算量を少なくできる。その結果、同種写像の計算効率を向上させることができる。
【００５４】
実施の形態１では、暗号装置１０の各部の機能がソフトウェアで実現された。しかし、変形例として、暗号装置１０の各部の機能はハードウェアで実現されてもよい。この変形例について、実施の形態１と異なる点を説明する。
【００５５】
図７を参照して、変形例に係る暗号装置１０の構成を説明する。
各部の機能がハードウェアで実現される場合、暗号装置１０は、プロセッサ１１と記憶装置１２とに代えて、処理回路１４を備える。処理回路１４は、暗号装置１０の各部の機能及び記憶装置１２の機能を実現する専用の電子回路である。
【００５６】
処理回路１４は、単一回路、複合回路、プログラム化したプロセッサ、並列プログラム化したプロセッサ、ロジックＩＣ、ＧＡ（Ｇａｔｅ  Ａｒｒａｙ）、ＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）、ＦＰＧＡ（Ｆｉｅｌｄ−Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ）が想定される。
各部の機能を１つの処理回路１４で実現してもよいし、各部の機能を複数の処理回路１４に分散させて実現してもよい。
【００５７】
また、一部の機能がハードウェアで実現され、他の機能がソフトウェアで実現されてもよい。つまり、暗号装置１０の各部のうち、一部の機能がハードウェアで実現され、他の機能がソフトウェアで実現されてもよい。
【００５８】
プロセッサ１１と記憶装置１２と処理回路１４とを、総称して「プロセッシングサーキットリー」という。つまり、各部の機能は、プロセッシングサーキットリーにより実現される。
【符号の説明】
【００５９】
１０  暗号装置、１１  プロセッサ、１２  記憶装置、１２１  メモリ、１２２  ストレージ、１３  インタフェース、１４  処理回路、２１  受付部、２２  曲線計算部、２３  出力値計算部。
【図１】
0006614979.tif 000018
【図２】
0006614979.tif 000019
【図３】
0006614979.tif 000020
【図４】
0006614979.tif 000021
【図５】
0006614979.tif 000022
【図６】
0006614979.tif 000023
【図７】
0006614979.tif 000024