(57)【特許請求の範囲】
【請求項１】
メッセージμのハッシュ値ｃと秘密鍵とのＭｉｄｄｌｅ−Ｐｒｏｄｕｃｔを計算して得られた値にランダムな値ｙを加えて署名要素ｚを生成し、数１に示す署名要素ｈと前記署名要素ｚと前記ハッシュ値ｃとを含む署名σを生成する署名生成部と、
前記署名生成部によって生成された前記署名要素ｚを含む署名σを出力する出力部と
を備える署名装置。
【数１】
0006818949.tif 000055
【請求項２】
メッセージμのハッシュ値ｃと秘密鍵とのＭｉｄｄｌｅ−Ｐｒｏｄｕｃｔを計算して生成された署名要素ｚと、前記ハッシュ値ｃとを含む署名σであって、数２に示す署名要素ｈと前記署名要素ｚと前記ハッシュ値ｃとを含む署名σを受け付ける受付部と、
前記受付部によって受け付けられた前記署名要素ｚと公開鍵とのＭｉｄｄｌｅ−Ｐｒｏｄｕｃｔを数３に示すように計算して得られた値ｗ’１と、前記メッセージμとを入力として、ハッシュ値ｃ’を計算し、計算されたハッシュ値ｃ’と、前記署名σに含まれるハッシュ値ｃとが一致するか否かを判定することにより、前記署名σを検証する検証部と
を備える検証装置。
【数２】
0006818949.tif 000056
【数３】
0006818949.tif 000057
【請求項３】
前記公開鍵は、ランダムな多項式ａと秘密鍵とのＭｉｄｄｌｅ−Ｐｒｏｄｕｃｔを計算して生成された
請求項２に記載の検証装置。
【請求項４】
メッセージμのハッシュ値ｃと秘密鍵とのＭｉｄｄｌｅ−Ｐｒｏｄｕｃｔを計算して署名要素ｚを生成し、前記署名要素ｚと前記ハッシュ値ｃとを含む署名σであって、数４に示す署名要素ｈと前記署名要素ｚと前記ハッシュ値ｃとを含む前記署名σを出力する署名装置と、
前記署名装置によって生成された前記署名要素ｚと公開鍵とのＭｉｄｄｌｅ−Ｐｒｏｄｕｃｔを数５に示すように計算して得られた値ｗ’１と、前記メッセージμとを入力として、ハッシュ値ｃ’を計算し、計算されたハッシュ値ｃ’と、前記署名σに含まれるハッシュ値ｃとが一致するか否かを判定することにより、前記署名σを検証する検証装置と
を備える署名システム。
【数４】
0006818949.tif 000058
【数５】
0006818949.tif 000059
【請求項５】
署名装置における署名生成部が、メッセージμのハッシュ値ｃと秘密鍵とのＭｉｄｄｌｅ−Ｐｒｏｄｕｃｔを計算して得られた値にランダムな値ｙを加えて署名要素ｚを生成して、数６に示す署名要素ｈと前記署名要素ｚと前記ハッシュ値ｃとを含む署名σを生成し、
前記署名装置における出力部が、前記署名要素ｚを含む署名σを出力する署名方法。
【数６】
0006818949.tif 000060
【請求項６】
署名生成部が、メッセージμのハッシュ値ｃと秘密鍵とのＭｉｄｄｌｅ−Ｐｒｏｄｕｃｔを計算して得られた値にランダムな値ｙを加えて署名要素ｚを生成し、数７に示す署名要素ｈと前記署名要素ｚと前記ハッシュ値ｃとを含む署名σを生成する署名生成処理と、
出力部が、前記署名生成処理によって生成された前記署名要素ｚを含む署名σを出力する出力処理と
を行う署名装置としてコンピュータを機能させる署名プログラム。
【数７】
0006818949.tif 000061
【請求項７】
検証装置における受付部が、メッセージμのハッシュ値ｃと秘密鍵とのＭｉｄｄｌｅ−Ｐｒｏｄｕｃｔを計算して生成された署名要素ｚと、前記ハッシュ値ｃとを含む署名σであって、数８に示す署名要素ｈと前記署名要素ｚと前記ハッシュ値ｃとを含む署名σを受け付け、
前記検証装置における検証部が、前記署名要素ｚと公開鍵とのＭｉｄｄｌｅ−Ｐｒｏｄｕｃｔを数９に示すように計算して得られた値ｗ’１と、前記メッセージμとを入力として、ハッシュ値ｃ’を計算し、計算されたハッシュ値ｃ’と、前記署名σに含まれるハッシュ値ｃとが一致するか否かを判定することにより、前記署名σを検証する検証方法。
【数８】
0006818949.tif 000062
【数９】
0006818949.tif 000063
【請求項８】
受付部が、メッセージμのハッシュ値ｃと秘密鍵とのＭｉｄｄｌｅ−Ｐｒｏｄｕｃｔを計算して生成された署名要素ｚと、前記ハッシュ値ｃとを含む署名σであって、数１０に示す署名要素ｈと前記署名要素ｚと前記ハッシュ値ｃとを含む署名σを受け付ける受付処理と、
検証部が、前記受付処理によって受け付けられた前記署名要素ｚと公開鍵とのＭｉｄｄｌｅ−Ｐｒｏｄｕｃｔを数１１に示すように計算して得られた値ｗ’１と、前記メッセージμとを入力として、ハッシュ値ｃ’を計算し、計算されたハッシュ値ｃ’と、前記署名σに含まれるハッシュ値ｃとが一致するか否かを判定することにより、前記署名σを検証する検証処理と
を行う検証装置としてコンピュータを機能させる検証プログラム。
【数１０】
0006818949.tif 000064
【数１１】
0006818949.tif 000065
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、量子コンピュータを考慮したディジタル署名に関する。
【背景技術】
【０００２】
ディジタル署名は、データの正当性を検証することができる暗号技術である。
ネットワークを介して通信を行う際には、受け取ったデータが本当に送信者から送られたデータであり、かつ、受け取ったデータが改ざんされていないデータであるというデータの正当性を確かめられるようにする必要がある。送信側でデータに署名を付随させ、受信側でデータに付随する署名を検証することにより、データの正当性を検証することができる。【０００３】
格子暗号とは，線形独立な整数ベクトルの線形変換で表されるベクトルの集合である格子を用いて実現される暗号技術である。
ある格子についての最短ベクトル問題は、その格子に含まれる最も短いベクトルを見つける問題である。格子暗号は、最短ベクトル問題を解くことが量子コンピュータにとっても困難であることを安全性の根拠としているため、格子暗号は、量子コンピュータが実現されたとしても安全であると考えられている暗号方式の１つである。【０００４】
効率的な格子暗号は、イデアル格子と呼ばれる特殊な格子の上での最短ベクトル問題を安全性の根拠としている。イデアル格子を定義する多項式である円分多項式の性質より、特定のパラメータにおいては最短ベクトル問題が量子コンピュータによって効率的に解読されることが知られている。【０００５】
非特許文献１には、イデアル格子上の最短ベクトル問題を安全性の根拠とした、効率的なディジタル署名方式が示されている。しかし、非特許文献１に示された方法は、特定の円分多項式によって定義される格子上の最短ベクトル問題を安全性の根拠としているため、安全ではない可能性がある。【０００６】
非特許文献２には、特定の円分多項式に依存しない格子上の最短ベクトル問題を安全性の根拠とした、効率的なディジタル署名方式が示されている。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Ｌｅｏ  Ｄｕｃａｓ，  Ｅｉｋｅ  Ｋｉｌｔｚ，  Ｔａｎｃｒｅｄｅ  Ｌｅｐｏｉｎｔ，  Ｖａｄｉｍ  Ｌｙｕｂａｓｈｅｖｓｋｙ，  Ｐｅｔｅｒ  Ｓｃｈｗａｂｅ，  Ｇｒｅｇｏｒ  Ｓｅｉｌｅｒ，  ａｎｄ  Ｄａｍｉｅｎ  Ｓｔｅｈｌｅ．  ＣＲＹＳＴＡＬＳ−Ｄｉｌｉｔｈｉｕｍ：  Ａ  Ｌａｔｔｉｃｅ−Ｂａｓｅｄ  Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅ  Ｓｃｈｅｍｅ．  Ｉｎ  ＣＨＥＳ，  ｐａｇｅｓ  ２３８−２６８，  ２０１８．
【非特許文献２】Ｖａｄｉｍ  Ｌｙｕｂａｓｈｅｖｓｋｙ．  Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅｓ  Ｂａｓｅｄ  ｏｎ  ｔｈｅ  Ｈａｒｄｎｅｓｓ  ｏｆ  Ｉｄｅａｌ  Ｌａｔｔｉｃｅ  Ｐｒｏｂｌｅｍｓ  ｉｎ  ａｌｌ  Ｒｉｎｇｓ．  Ｉｎ  ＡＳＩＡＣＲＹＰＴ，  ｐａｇｅｓ  １９６−２１４，  ２０１６．
【発明の概要】
【発明が解決しようとする課題】
【０００８】
非特許文献２で示されているディジタル署名方式は、量子コンピュータがハッシュ関数を計算するような安全性モデルにおいては安全であることが示されていない。格子の上での最短ベクトル問題を安全性の根拠とするディジタル署名方式は、ディジタル署名を生成するためにハッシュ関数を計算している。そのため、厳密な意味での量子コンピュータに対する安全性を考慮するためには、量子コンピュータがハッシュ関数を計算するようなモデルにおいても安全性が示されていることが望ましい。
この発明は、量子コンピュータに対しても安全性が保証可能なディジタル署名方式を構成可能にすることを目的とする。
【課題を解決するための手段】
【０００９】
この発明に係る署名装置は、
メッセージμのハッシュ値ｃと秘密鍵とのＭｉｄｄｌｅ−Ｐｒｏｄｕｃｔを計算して署名要素ｚを生成する署名生成部と、
前記署名生成部によって生成された前記署名要素ｚを含む署名σを出力する出力部と
を備える。
【発明の効果】
【００１０】
この発明では、メッセージμのハッシュ値ｃと秘密鍵とのＭｉｄｄｌｅ−Ｐｒｏｄｕｃｔを計算して署名要素ｚを生成する。これにより、量子コンピュータがハッシュ関数を計算するような安全性モデルにおいて安全であることを示すことが可能なディジタル署名方式を構成可能になる。
【図面の簡単な説明】
【００１１】
【図１】実施の形態１に係る署名システム１の構成図。
【図２】実施の形態１に係る鍵生成装置１０の構成図。
【図３】実施の形態１に係る署名装置２０の構成図。
【図４】実施の形態１に係る検証装置３０の構成図。
【図５】実施の形態１に係る鍵生成装置１０の動作のフローチャート。
【図６】実施の形態１に係る鍵生成処理のフローチャート。
【図７】実施の形態１に係る署名装置２０の動作のフローチャート。
【図８】実施の形態１に係る署名生成処理のフローチャート。
【図９】実施の形態１に係る検証装置３０の動作のフローチャート。
【図１０】変形例１に係る鍵生成装置１０の構成図。
【図１１】変形例１に係る署名装置２０の構成図。
【図１２】変形例１に係る検証装置３０の構成図。
【発明を実施するための形態】
【００１２】
実施の形態１．
【００１３】
＊＊＊構成の説明＊＊＊
図１を参照して、実施の形態１に係る署名システム１の構成を説明する。
署名システム１は、鍵生成装置１０と、署名装置２０と、検証装置３０とを備える。鍵生成装置１０と、署名装置２０と、検証装置３０とは、インターネットといった通信路４０を介して接続されている。通信路４０は、インターネットに限らず、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）といった他の種別の通信路であってもよい。
【００１４】
鍵生成装置１０は、ＰＣ（Ｐｅｒｓｏｎａｌ  Ｃｏｍｐｕｔｅｒ）といったコンピュータである。鍵生成装置１０は、暗号化に利用する公開鍵及び秘密鍵を生成し、通信路４０を介して、秘密鍵を署名装置２０に送信するとともに、公開鍵を検証装置３０に送信する。
【００１５】
署名装置２０は、ＰＣ（Ｐｅｒｓｏｎａｌ  Ｃｏｍｐｕｔｅｒ）といったコンピュータである。署名装置２０は、コンピュータ内部に保存されている文書データ等の平文データに対して、保管している秘密鍵で署名を生成することで署名データを生成し、署名データと平文データとを検証装置３０に送信する。
【００１６】
検証装置３０は、ＰＣ（Ｐｅｒｓｏｎａｌ  Ｃｏｍｐｕｔｅｒ）といったコンピュータである。検証装置３０は、署名装置２０から受け取った平文データ及び署名データと、鍵生成装置１０から受け取った公開鍵とを用いて、平文データについての署名データの検証結果データを生成する。
【００１７】
なお、同じコンピュータ内に、鍵生成装置１０と署名装置２０と検証装置３０とのいずれか２つ以上が同時に含まれていてもよい。
【００１８】
図２を参照して、実施の形態１に係る鍵生成装置１０の構成を説明する。
鍵生成装置１０は、プロセッサ１１と、メモリ１２と、ストレージ１３と、通信インタフェース１４とのハードウェアを備える。プロセッサ１１は、信号線を介して他のハードウェアと接続され、これら他のハードウェアを制御する。
【００１９】
鍵生成装置１０は、機能構成要素として、受付部１１１と、鍵生成部１１２と、送信部１１３とを備える。鍵生成装置１０の各機能構成要素の機能はソフトウェアにより実現される。
ストレージ１３には、鍵生成装置１０の各機能構成要素の機能を実現するプログラムが格納されている。このプログラムは、プロセッサ１１によりメモリ１２に読み込まれ、プロセッサ１１によって実行される。これにより、鍵生成装置１０の各機能構成要素の機能が実現される。
ストレージ１３は、鍵記憶部１３１の機能を実現する。
【００２０】
図３を参照して、実施の形態１に係る署名装置２０の構成を説明する。
署名装置２０は、プロセッサ２１と、メモリ２２と、ストレージ２３と、通信インタフェース２４とのハードウェアを備える。プロセッサ２１は、信号線を介して他のハードウェアと接続され、これら他のハードウェアを制御する。
【００２１】
署名装置２０は、機能構成要素として、受付部２１１と、署名生成部２１２と、出力部２１３とを備える。署名装置２０の各機能構成要素の機能はソフトウェアにより実現される。
ストレージ２３には、署名装置２０の各機能構成要素の機能を実現するプログラムが格納されている。このプログラムは、プロセッサ２１によりメモリ２２に読み込まれ、プロセッサ２１によって実行される。これにより、署名装置２０の各機能構成要素の機能が実現される。
ストレージ２３は、鍵記憶部２３１の機能を実現する。
【００２２】
図４を参照して、実施の形態１に係る検証装置３０の構成を説明する。
検証装置３０は、プロセッサ３１と、メモリ３２と、ストレージ３３と、通信インタフェース３４とのハードウェアを備える。プロセッサ３１は、信号線を介して他のハードウェアと接続され、これら他のハードウェアを制御する。
【００２３】
検証装置３０は、機能構成要素として、受付部３１１と、検証部３１２とを備える。検証装置３０の各機能構成要素の機能はソフトウェアにより実現される。
ストレージ３３には、検証装置３０の各機能構成要素の機能を実現するプログラムが格納されている。このプログラムは、プロセッサ３１によりメモリ３２に読み込まれ、プロセッサ３１によって実行される。これにより、検証装置３０の各機能構成要素の機能が実現される。
ストレージ３３は、鍵記憶部３３１と、結果記憶部３３２との機能を実現する。
【００２４】
プロセッサ１１，２１，３１は、演算処理を行うＩＣ（Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）である。プロセッサ１１，２１，３１は、具体例としては、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）、ＤＳＰ（Ｄｉｇｉｔａｌ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｏｒ）、ＧＰＵ（Ｇｒａｐｈｉｃｓ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）である。
【００２５】
メモリ１２，２２，３２は、データを一時的に記憶する記憶装置である。メモリ１２，２２，３２は、具体例としては、ＳＲＡＭ（Ｓｔａｔｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、ＤＲＡＭ（Ｄｙｎａｍｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）である。
【００２６】
ストレージ１３，２３，３３は、データを保管する記憶装置である。ストレージ１３，２３，３３は、具体例としては、ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）である。また、ストレージ１３，２３，３３は、ＳＤ（登録商標，Ｓｅｃｕｒｅ  Ｄｉｇｉｔａｌ）メモリカード、ＣＦ（ＣｏｍｐａｃｔＦｌａｓｈ，登録商標）、ＮＡＮＤフラッシュ、フレキシブルディスク、光ディスク、コンパクトディスク、ブルーレイ（登録商標）ディスク、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）といった可搬記憶媒体であってもよい。
【００２７】
通信インタフェース１４，２４，３４は、外部の装置と通信するためのインタフェースである。通信インタフェース１４，２４，３４は、具体例としては、Ｅｔｈｅｒｎｅｔ（登録商標）、ＵＳＢ（Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓ）、ＨＤＭＩ（登録商標，Ｈｉｇｈ−Ｄｅｆｉｎｉｔｉｏｎ  Ｍｕｌｔｉｍｅｄｉａ  Ｉｎｔｅｒｆａｃｅ）のポートである。
【００２８】
図２では、プロセッサ１１は、１つだけ示されている。しかし、鍵生成装置１０は、プロセッサ１１を代替する複数のプロセッサを備えていてもよい。同様に、署名装置２０は、プロセッサ２１を代替する複数のプロセッサを備えていてもよい。検証装置３０は、プロセッサ３１を代替する複数のプロセッサを備えていてもよい。
これら複数のプロセッサは、各機能構成要素の機能を実現するプログラムの実行を分担する。それぞれのプロセッサは、プロセッサ１１，２１，３１と同じように、演算処理を行うＩＣである。
【００２９】
＊＊＊動作の説明＊＊＊
図５から図９を参照して、実施の形態１に係る署名システム１の動作を説明する。
実施の形態１に係る署名システム１の動作は、実施の形態１に係る署名方法に相当する。また、実施の形態１に係る署名システム１の動作は、実施の形態１に係る署名プログラムの処理に相当する。
【００３０】
＊＊準備＊＊
実施の形態１に係る署名システム１の動作の説明に必要な情報を説明する。
＜記法＞
以下の説明で用いる記法を説明する。
自然数の集合を数１１で表し、整数の集合を数１２で表す。以下、文章中では、自然数の集合をＮと表し、整数の集合をＺと表す。
【数１１】
0006818949.tif 000002
【数１２】
0006818949.tif 000003
【００３１】
任意の整数ａ，ｂに対して、（ａ，ｂ）は、数１３に示す集合を表し、［ａ，ｂ］は、数１４に示す集合を表す。
【数１３】
0006818949.tif 000004
【数１４】
0006818949.tif 000005
任意の正の整数ｄ＞０に対して、［ｄ］は、集合｛１，２，．．．，ｄ｝を表す。
【００３２】
Ｓをある集合とし、Ｐを集合Ｓ上の確率分布とする。このとき、数１５は、ａ∈Ｓが集合Ｓから一様ランダムに選ばれていることを表す。また、数１６は、ｂ∈Ｓが確率分布Ｐに沿って選ばれていることを表す。
【数１５】
0006818949.tif 000006
【数１６】
0006818949.tif 000007
【００３３】
ｎｅｇｌ（λ）は、自然数λについて無視できる関数の集合を表す。
【００３４】
＜ディジタル署名＞
ディジタル署名は、ＫｅｙＧｅｎアルゴリズムと、Ｓｉｇｎアルゴリズムと、Ｖｅｒｉｆｙアルゴリズムとの３つのアルゴリズムからなる。
【００３５】
ＫｅｙＧｅｎアルゴリズムは、セキュリティパラメータλを入力として、秘密鍵ｓｋと公開鍵ｐｋとのペア（ｓｋ，ｐｋ）を出力する。
【００３６】
Ｓｉｇｎアルゴリズムは、秘密鍵ｓｋと、メッセージμとを入力として、署名σを出力する。
【００３７】
Ｖｅｒｉｆｙアルゴリズムは、公開鍵ｐｋと、メッセージμと、署名σとを入力として、署名σがメッセージμの有効な署名であれば１を出力し、そうでなければ０を出力する。
【００３８】
＜Ｍｉｄｄｌｅ−Ｐｒｏｄｕｃｔ  Ｌｅａｒｎｉｎｇ  Ｗｉｔｈ  Ｅｒｒｏｒｓ（ＭＰＬＷＥ）＞
ＭＰＬＷＥは、文献（Ｍｉｒｕｍａ  Ｒｏｓｃａ，  Ａｍｉｎ  Ｓａｋｚａｄ，  Ｄａｍｉｅｎ  Ｓｔｅｈｌｅ，  ａｎｄ  Ｒｏｎ  Ｓｔｅｉｎｆｅｌｄ．  Ｍｉｄｄｌｅ−Ｐｒｏｄｕｃｔ  Ｌｅａｒｎｉｎｇ  ｗｉｔｈ  Ｅｒｒｏｒｓ．  Ｉｎ  ＣＲＹＰＴＯ，  ｐａｇｅｓ  ２８３-２９７，  ２０１７．）に記載されている。
【００３９】
次数が高々ｋ−１＞０で、係数がＺの多項式の集合をＲ＜ｋで表し、係数がＺｑの多項式の集合をＲｑ＜ｋで表す。多項式ｒのＬ∞ノルムとＬ２ノルムとをそれぞれ数１７に示すように表す。
【数１７】
0006818949.tif 000008
自然数αに対して、数１８を満たす要素ｗの集合をＳα＜ｋで表す。
【数１８】
0006818949.tif 000009
ある多項式ｒ０＋ｒ１ｘ＋．．．＋ｒｋ−１ｘｋ−１∈Ｒ＜ｋ（または、ｒ∈Ｓ＜ｋ）に対して、数１９と書く。
【数１９】
0006818949.tif 000010
ベクトルｒ∈Ｚｋに対して、ｒ［ｉ：ｊ］（０＜ｉ＜ｊ＜ｋ）は、ｒのｉ番目からｊ番目の係数のベクトルを表す。
【００４０】
（Ｔｏｅｐｌｉｔｚ行列の定義）
任意のｄ，ｋ＞０と、ａ∈Ｒ＜ｋとに対して、ｉ行目（ｉ＝１，．．．，ｄ）がｘｉ−１・ａの係数ベクトルであるようなＲｄ×（ｋ＋ｄ−１）の行列をＴｏｅｐｄ，ｋ（ａ）で表し、Ｔｏｅｐｌｉｔｚ行列と呼ぶ。
【００４１】
（Ｍｉｄｄｌｅ−Ｐｒｏｄｕｃｔの定義）
ｄａ，ｄｂ，ｄ，ｋをｄａ＋ｄｂ−１＝ｄ＋２ｋを満たす整数とする。数２０に示すＭｉｄｄｌｅ−Ｐｒｏｄｕｃｔの写像は、数２１に示す写像である。
【数２０】
0006818949.tif 000011
【数２１】
0006818949.tif 000012
ここで、ｄａ＋ｄｂ−１−ｄが負でなく、かつ偶数であるような全てのｄａ，ｄｂに対して、数２２に示す記法が用いられる。
【数２２】
0006818949.tif 000013
【００４２】
以下のように、Ｍｉｄｄｌｅ−ＰｒｏｄｕｃｔをＴｏｅｐｌｉｔｚ行列を用いて表すことができる。Ｔｏｅｐｌｉｔｚ行列とベクトルとの積はＯ（ｎｌｏｇｎ）で計算することができる。
【００４３】
（補題１）
ｄ，ｋ＞０とする。数２３であるとする。
【数２３】
0006818949.tif 000014
このとき、数２４が成立する。
【数２４】
0006818949.tif 000015
【００４４】
（系１）
数２４は、数２５のように変換することができる。
【数２５】
0006818949.tif 000016
【００４５】
対応する次元をもつ多項式に対して、Ｍｉｄｄｌｅ−Ｐｒｏｄｕｃｔと多項式との積は、結合法則のような以下の性質を満たす。
（補題２）
ｄ，ｋ，ｎ＞０とする。全てのｒ∈Ｒ＜ｋ＋１，ａ∈Ｒ＜ｎ，ｓ∈Ｒ＜ｎ＋ｄ＋ｋ−１に対して、数２６が成立する。
【数２６】
0006818949.tif 000017
【００４６】
補題２と同じ次数を持つ多項式について、Ｍｉｄｄｌｅ−Ｐｒｏｄｕｃｔが部分的に可換性を持つことを多項式の積の可換性から示すことができる。
（系２）
補題２と同じｒ∈Ｒ＜ｋ＋１，ａ∈Ｒ＜ｎ，ｓ∈Ｒ＜ｎ＋ｄ＋ｋ−１に対して、数２７が成立する。
【数２７】
0006818949.tif 000018
【００４７】
（ＭＰＬＷＥ分布の定義）
ｎ，ｄ＞０、ｑ≧２、χをＲ＜ｄ上の分布とする。ｓ∈Ｚに対して、Ｚｑ＜ｎ［ｘ］×Ｒｑ＜ｄ上の分布ＭＰＬＷＥｑ，ｎ，ｄ，χ（ｓ）は、数２８に示すように、ａ，ｅをサンプルし、数２９を返す分布である。
【数２８】
0006818949.tif 000019
【数２９】
0006818949.tif 000020
【００４８】
決定性のＭＰＬＷＥ問題の定義を説明する。ＭＰＬＷＥ問題は、ＭＰＬＷＥ分布と一様分布とのどちらの確率分布からサンプルされた要素かを識別する問題である。決定性のＭＰＬＷＥ仮定とは、ＭＰＬＷＥ問題が任意の効率的なアルゴリズムによって解くことが困難であるという仮定である。
【００４９】
（ＭＰＬＷＥ問題の定義）
ｎ，ｄ＞０、ｑ≧２、χをＲ＜ｄ上の分布とする。ＭＰＬＷＥｎ，ｄ，ｑ，χ問題は、ＭＰＬＷＥｎ，ｄ，ｑ，χ（ｓ）からの任意個のサンプルと、Ｚｑ＜ｎ［ｘ］×Ｒｑ＜ｄからの同じ個数のサンプルとを識別する問題である。
任意の攻撃者Ａに対して、ＭＰＬＷＥｎ，ｄ，ｑ，χ問題についての攻撃者Ａの優位性は、数３０のように定義される。
【数３０】
0006818949.tif 000021
ここで、確率は、数３１と攻撃者の乱数上で取られる。
【数３１】
0006818949.tif 000022
任意の確率的多項式時間アルゴリズムＡに対して、ＭＰＬＷＥｎ，ｄ，ｑ，χ問題を解くことが困難であるとき、つまり、ＡｄｖＡＭＰＬＷＥ（λ）＝ｎｅｇｌ（λ）であるとき、ＭＰＬＷＥ仮定が成立しているという。
【００５０】
＜付随アルゴリズム＞
実施の形態１に係る署名システム１によって実現されるディジタル署名で用いられるアルゴリズムを説明する。
【００５１】
（記法）
アルゴリズムで用いられる記法を説明する。
任意の整数ｒと、任意の偶数（または奇数）である整数α＞０とについて、ｒ’＝ｒ  ｍｏｄ±  αをｒ’＝ｒ  ｍｏｄ  αを満たす一意の要素ｒ’∈（−α／２，α／２］（整数αが奇数の場合には、ｒ’∈［−（α−１）／２，（α−１）／２））とする。また、ｒ’＝ｒ  ｍｏｄ＋  αをｒ’＝ｒ  ｍｏｄ  αを満たす一意な整数ｒ’∈［０，α）とする。
【００５２】
Ｂが真であれば１、そうでなければ０となるビットを数３２で表す。
【数３２】
0006818949.tif 000023
【００５３】
（アルゴリズム）
このアルゴリズムは、文献（Ｌｅｏ  Ｄｕｃａｓ，  Ｅｉｋｅ  Ｋｉｌｔｚ，  Ｔａｎｃｒｅｄｅ  Ｌｅｐｏｉｎｔ，  Ｖａｄｉｍ  Ｌｙｕｂａｓｈｅｖｓｋｙ，  Ｐｅｔｅｒ  Ｓｃｈｗａｂｅ，  Ｇｒｅｇｏｒ  Ｓｅｉｌｅｒ，ａｎｄ  Ｄａｍｉｅｎ  Ｓｔｅｈｌｅ．  ＣＲＹＳＴＡＬＳ  −  Ｄｉｌｉｔｈｉｕｍ：  Ａ  Ｌａｔｔｉｃｅ−ｂａｓｅｄ  Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅ  Ｓｃｈｅｍｅ．  Ｉｎ  ＣＨＥＳ，  ｐａｇｅｓ  ２３８-２６８，  ２０１８．）に記載されている。
アルゴリズムは整数上で定義されている。しかし、係数毎にアルゴリズムを適用することで多項式に対しても簡単に一般化することができる。
【００５４】
（Ｐｒｏｗｅｒ２Ｒｏｕｎｄｑ（ｒ，ｄ）アルゴリズム）
Ｐｒｏｗｅｒ２Ｒｏｕｎｄｑ（ｒ，ｄ）アルゴリズムは、ｒを２ｄで区切った上位ビットを出力するアルゴリズムである。
具体的には、Ｐｒｏｗｅｒ２Ｒｏｕｎｄｑ（ｒ，ｄ）アルゴリズムでは、ｒ：＝ｒ  ｍｏｄ＋  ｑが計算され、さらにｒ０：＝ｒ  ｍｏｄ±  ２ｄが計算される。そして、（ｒ−ｒ０）／２ｄが出力される。
【００５５】
（Ｄｅｃｏｍｐｏｓｅｑ（ｒ，α）アルゴリズム）
Ｄｅｃｏｍｐｏｓｅｑ（ｒ，α）アルゴリズムは、ｒをαで区切った上位ビットｒ１と下位ビットｒ０とを出力するアルゴリズムである。
具体的には、Ｄｅｃｏｍｐｏｓｅｑ（ｒ，α）アルゴリズムでは、ｒ：＝ｒ  ｍｏｄ＋  ｑが計算され、さらにｒ０：＝ｒ  ｍｏｄ±  αが計算される。もし、ｒ−ｒ０＝ｑ−１なら、ｒ１：＝０が設定され、ｒ０：＝ｒ０−１が設定される。そうでなければ、ｒ１：＝（ｒ−ｒ０）／αが設定される。そして、ｒ１及びｒ０が出力される。
【００５６】
（ＨｉｇｈＢｉｔｓｑ（ｒ，α）アルゴリズム）
ＨｉｇｈＢｉｔｓｑ（ｒ，α）アルゴリズムは、ｒをαで区切った上位ビットｒ１を出力するアルゴリズムである。
具体的には、ＨｉｇｈＢｉｔｓｑ（ｒ，α）アルゴリズムでは、（ｒ０，ｒ１）：＝Ｄｅｃｏｍｐｏｓｅｑ（ｒ，α）が計算され、ｒ１が出力される。
【００５７】
（ＬｏｗＢｉｔｓｑ（ｒ，α）アルゴリズム）
ＬｏｗＢｉｔｓｑ（ｒ，α）アルゴリズムは、ｒをαで区切った下位ビットｒ０を出力するアルゴリズムである。
具体的には、ＬｏｗＢｉｔｓｑ（ｒ，α）アルゴリズムでは、（ｒ０，ｒ１）：＝Ｄｅｃｏｍｐｏｓｅｑ（ｒ，α）が計算され、ｒ０が出力される。
【００５８】
（ＵｓｅＨｉｎｔｑ（ｈ，ｒ，α）アルゴリズム）
ＵｓｅＨｉｎｔｑ（ｈ，ｒ，α）アルゴリズムは、後述するＭａｋｅＨｉｎｔｑ（ｚ，ｒ，α）アルゴリズムの情報に応じて、ｒ＋ｚの上位ビットを復元する。
具体的には、ＵｓｅＨｉｎｔｑ（ｈ，ｒ，α）アルゴリズムでは、ｍ：＝（ｑ−１）／αが設定され、（ｒ０，ｒ１）：＝Ｄｅｃｏｍｐｏｓｅｑ（ｒ，α）が計算される。ｈ＝１かつｒ０＞０であれば、（ｒ１＋１）  ｍｏｄ＋  ｍが出力される。ｈ＝１かつｒ０≦０であれば、（ｒ１−１）  ｍｏｄ＋  ｍが出力される。
【００５９】
（ＭａｋｅＨｉｎｔｑ（ｚ，ｒ，α）アルゴリズム）
ＭａｋｅＨｉｎｔｑ（ｚ，ｒ，α）アルゴリズムは、ｒに小さい値ｚを足した場合に、ｒの上位ビットが変化するか否かを示す情報を出力する。
具体的には、ＭａｋｅＨｉｎｔｑ（ｚ，ｒ，α）アルゴリズムでは、ｒ１：＝ＨｉｇｈＢｉｔｓｑ（ｒ，α）と、ｖ１：＝ＨｉｇｈＢｉｔｓｑ（ｒ＋ｚ，α）とが計算される。そして、数３３が出力される。
【数３３】
0006818949.tif 000024
【００６０】
（補題３）
ｑとαとは、ｑ＞２αと、数３４とを満たし、αは偶数である正の整数とする。ｒとｚとはＲｑ＜ｎの要素であり、数３５であり、ｈ，ｈ’は二進ベクトルであるとする。
【数３４】
0006818949.tif 000025
【数３５】
0006818949.tif 000026
このとき、ＨｉｇｈＢｉｔｓｑ（ｒ，α）アルゴリズムと、ＵｓｅＨｉｎｔｑ（ｈ，ｒ，α）アルゴリズムと、ＭａｋｅＨｉｎｔｑ（ｚ，ｒ，α）アルゴリズムとは、以下の性質を満たす。
性質１：ＵｓｅＨｉｎｔｑ（ＭａｋｅＨｉｎｔｑ（ｚ，ｒ，α），ｒ，α）＝ＨｉｇｈＢｉｔｓｑ（ｒ＋ｚ，α）である。
性質２：ｖ１：＝ＵｓｅＨｉｎｔｑ（ｈ，ｒ，α）とすると、数３６となる。
【数３６】
0006818949.tif 000027
性質３：任意のｈ，ｈ’に対して、ＵｓｅＨｉｎｔｑ（ｈ，ｒ，α）＝ＵｓｅＨｉｎｔｑ（ｈ’，ｒ，α）であれば、ｈ＝ｈ’である。
【００６１】
（補題４）
数３７かつ数３８であれば、数３９となる。
【数３７】
0006818949.tif 000028
【数３８】
0006818949.tif 000029
【数３９】
0006818949.tif 000030
【００６２】
＊＊署名システム１の動作＊＊
以下では、Ｃは多項式の集合である。要素のＬ∞ノルムは、１であり、Ｌ２ノルムは多項式がλビットのｍｉｎ−エントロピーを持つように制限される。また、以下の説明におけるβ、β’、γ、γ’、δは、安全性を考慮して決定される値であり、高い安全性を設定するほど、大きい値が設定される。
【００６３】
＜鍵生成装置１０の動作＞
図５を参照して、実施の形態１に係る鍵生成装置１０の動作を説明する。
実施の形態１に係る鍵生成装置１０の動作は、実施の形態１に係る鍵生成方法に相当する。また、実施の形態１に係る鍵生成装置１０の動作は、実施の形態１に係る鍵生成プログラムの処理に相当する。
鍵生成装置１０は、ディジタル署名の３つのアルゴリズムのうち、ＫｅｙＧｅｎアルゴリズムを実現する。
【００６４】
（ステップＳ１１：受付処理）
受付部１１１は、セキュリティパラメータλの入力を受け付ける。
具体的には、受付部１１１は、鍵生成装置１０の利用者によって入力装置が操作され入力されたセキュリティパラメータλを受け付ける。受付部１１１は、セキュリティパラメータλをメモリ１２に書き込む。
【００６５】
（ステップＳ１２：鍵生成処理）
鍵生成部１１２は、セキュリティパラメータλをメモリ１２から読み出す。鍵生成部１１２は、セキュリティパラメータλを入力として、秘密鍵ｓｋと、公開鍵ｐｋとのペアを生成する。
【００６６】
図６を参照して、実施の形態１に係る鍵生成処理を説明する。
（ステップＳ１２１：パラメータ設定処理）
鍵生成部１１２は、セキュリティパラメータλをメモリ１２から読み出す。鍵生成部１１２は、ｎ＝ｎ（λ）、ｄ＝ｄ（λ）、ｋ＝ｋ（λ）、ｑ＝ｑ（λ）を設定する。つまり、ｎ，ｄ，ｋ，ｑはセキュリティパラメータλによって決まる値である。
【００６７】
（ステップＳ１２２：乱数生成処理）
鍵生成部１１２は、一様ランダムにａ∈Ｒｑ＜ｎを生成する。
具体的には、鍵生成部１１２は、数４０に示すようにランダムにシードρを選択する。
【数４０】
0006818949.tif 000031
そして、鍵生成部１１２は、シードρを入力として疑似乱数生成アルゴリズムによりａ∈Ｒｑ＜ｎを生成する。
【００６８】
（ステップＳ１２３：秘密鍵要素生成処理）
鍵生成部１１２は、数４１に示すように、秘密鍵ｓｋの要素ｓ１及び要素ｓ２を一様ランダムに生成する。
【数４１】
0006818949.tif 000032
【００６９】
（ステップＳ１２４：公開鍵要素生成処理）
鍵生成部１１２は、数４２に示すように、公開鍵ｐｋの要素ｔ０及び要素ｔ１を生成する。
【数４２】
0006818949.tif 000033
【００７０】
（ステップＳ１２５：鍵設定処理）
鍵生成部１１２は、秘密鍵ｓｋ：＝（ａ，ｓ１，ｓ２，ｔ０）を設定する。また、鍵生成部１１２は、公開鍵ｐｋ：＝（ａ，ｔ０，ｔ１）を設定する。鍵生成部１１２は、秘密鍵ｓｋ及び公開鍵ｐｋをメモリ１２に書き込むとともに、鍵記憶部１３１に書き込む。
【００７１】
（ステップＳ１３：送信処理）
送信部１１３は、秘密鍵ｓｋ及び公開鍵ｐｋをメモリ１２から読み出す。送信部１１３は、秘密鍵ｓｋを通信インタフェース１４及び通信路４０を介して署名装置２０に秘密裡に送信する。すると、署名装置２０の受付部２１１は、秘密鍵ｓｋを受け付け、鍵記憶部２３１に書き込む。また、送信部１１３は、公開鍵ｐｋを通信インタフェース１４及び通信路４０を介して検証装置３０に送信する。すると、検証装置３０の受付部３１１は、公開鍵ｐｋを受け付け、鍵記憶部３３１に書き込む。
ここで、密裡に送信するとは、例えば、既存の暗号化方式により暗号化した上で送信することである。なお、秘密鍵ｓｋ及び公開鍵ｐｋは、可搬記憶媒体に記憶した上で郵送などにより直接的に送信してもよい。公開鍵と秘密鍵は外部の装置で生成されてもよい。
【００７２】
＜署名装置２０の動作＞
図７を参照して、実施の形態１に係る署名装置２０の動作を説明する。
実施の形態１に係る署名装置２０の動作は、実施の形態１に係る署名生成方法に相当する。また、実施の形態１に係る署名装置２０の動作は、実施の形態１に係る署名生成プログラムの処理に相当する。
署名装置２０は、ディジタル署名の３つのアルゴリズムのうち、Ｓｉｇｎアルゴリズムを実現する。
【００７３】
（ステップＳ２１：受付処理）
受付部２１１は、メッセージμの入力を受け付ける。
具体的には、受付部２１１は、署名装置２０の利用者によって入力装置が操作され入力されたメッセージμを受け付ける。受付部２１１は、メッセージμをメモリ２２に書き込む。
【００７４】
（ステップＳ２２：署名生成処理）
署名生成部２１２は、秘密鍵ｓｋを鍵記憶部２３１から読み出すとともに、メッセージμをメモリ２２から読み出す。署名生成部２１２は、秘密鍵ｓｋ及びメッセージμを入力として、メッセージμに対する署名σを生成する。
【００７５】
図８を参照して、実施の形態１に係る署名生成処理を説明する。
（ステップＳ２２１：乱数生成処理）
署名生成部２１２は、数４３に示すように、乱数ｙを生成する。
【数４３】
0006818949.tif 000034
【００７６】
（ステップＳ２２２：ハッシュ値ｃ生成処理）
署名生成部２１２は、数４４に示すように、要素ｗを生成する。
【数４４】
0006818949.tif 000035
署名生成部２１２は、数４５に示すように要素ｗ１を生成する。
【数４５】
0006818949.tif 000036
署名生成部２１２は、要素ｗ１及びメッセージμ入力として、ハッシュ関数Ｈによりハッシュ値ｃを計算する。つまりｃ：＝Ｈ（ｗ１，μ）∈Ｃである。
【００７７】
（ステップＳ２２３：要素ｚ生成処理）
署名生成部２１２は、ハッシュ値ｃと、秘密鍵ｓｋの要素ｓ１と、乱数ｙとを入力として、数４６に示すように、署名σの要素ｚを生成する。
【数４６】
0006818949.tif 000037
つまり、署名生成部２１２は、メッセージμのハッシュ値ｃと秘密鍵ｓｋの要素ｓ１とのＭｉｄｄｌｅ−Ｐｒｏｄｕｃｔを計算して署名要素ｚを生成する。より詳しくは、署名生成部２１２は、ハッシュ値ｃと秘密鍵とのＭｉｄｄｌｅ−Ｐｒｏｄｕｃｔを計算して得られた値に小さな係数を持つランダムな値ｙを加えて署名要素ｚを生成する。
【００７８】
（ステップＳ２２４：要素ｈ生成処理）
署名生成部２１２は、数４７と数４８とのいずれかであるか否かを判定する。
【数４７】
0006818949.tif 000038
【数４８】
0006818949.tif 000039
署名生成部２１２は、数４７と数４８とのいずれかである場合には、署名要素ｚ及び署名要素ｈに署名生成不可を示す⊥を設定する。つまり、（ｚ，ｈ）：＝（⊥，⊥）である。
一方、署名生成部２１２は、数４７と数４８とのいずれでもない場合には、数４９に示すように署名要素ｈを生成する。
【数４９】
0006818949.tif 000040
【００７９】
（ステップＳ２２５：署名設定処理）
署名生成部２１２は、署名σ：＝（ｈ，ｚ，ｃ）を設定する。署名生成部２１２は、署名σをメモリ２２に書き込む。
【００８０】
（ステップＳ２３：出力処理）
出力部２１３は、署名生成部２１２によって生成された署名要素ｈと署名要素ｚとハッシュ値ｃとを含む署名σ及びメッセージμを出力する。
具体的には、出力部２１３は、通信インタフェース２４及び通信路４０を介して、署名σ及びメッセージμを検証装置３０に送信する。すると、検証装置３０の受付部３１１は、署名σ及びメッセージμを受け付け、メモリ３２に書き込む。
【００８１】
＜検証装置３０の動作＞
図９を参照して、実施の形態１に係る検証装置３０の動作を説明する。
実施の形態１に係る検証装置３０の動作は、実施の形態１に係る検証方法に相当する。また、実施の形態１に係る検証装置３０の動作は、実施の形態１に係る検証プログラムの処理に相当する。
検証装置３０は、ディジタル署名の３つのアルゴリズムのうち、Ｖｅｒｉｆｙアルゴリズムを実現する。
【００８２】
（ステップＳ３１：読出処理）
検証部３１２は、公開鍵ｐｋを鍵記憶部３３１から読み出すとともに、署名σ及びメッセージμをメモリ３２から読み出す。
【００８３】
（ステップＳ３２：要素ｗ’１生成処理）
検証部３１２は、数５０に示すように要素ｗ’１を生成する。
【数５０】
0006818949.tif 000041
つまり、検証部３１２は、署名σに含まれる署名要素ｚと公開鍵ｐｋの要素ａとのＭｉｄｄｌｅ−Ｐｒｏｄｕｃｔを計算するとともに、署名σに含まれるハッシュ値ｃと公開鍵ｐｋの要素ｔ１とのＭｉｄｄｌｅ−Ｐｒｏｄｕｃｔを計算して、要素ｗ’１を生成する。
【００８４】
（ステップＳ３３：ノルム判定処理）
検証部３１２は、数５１が成立するか否かを判定する。
【数５１】
0006818949.tif 000042
検証部３１２は、数５１が成立するなら処理をステップＳ３４に進める。一方、検証部３１２は、数５１が成立しないなら処理をステップＳ３６に進める。
【００８５】
（ステップＳ３４：ハッシュ値判定処理）
検証部３１２は、要素ｗ’１及びメッセージμ入力として、ハッシュ関数Ｈによりハッシュ値ｃ’を計算する。つまりｃ：＝Ｈ（ｗ’１，μ）である。検証部３１２は、署名σに含まれるハッシュ値ｃと、計算されたハッシュ値ｃ’とが等しいか否かを判定する。
検証部３１２は、ハッシュ値ｃとハッシュ値ｃ’とが等しい場合には、処理をステップＳ３５に進める。一方、検証部３１２は、ハッシュ値ｃとハッシュ値ｃ’とが等しくない場合には、処理をステップＳ３６に進める。
【００８６】
（ステップＳ３５：正当判定処理）
検証部３１２は、メッセージμが正当であると判定する。メッセージμが正当であるとは、メッセージμが改ざんされておらず、かつ、メッセージμが秘密鍵ｓｋの保有者によって送信されたという意味である。
そして、検証部３１２は、メッセージμが正当であることを示す値１を出力する。
【００８７】
（ステップＳ３６：不当判定処理）
検証部３１２は、メッセージμが不当であると判定する。メッセージμが不当であるとは、メッセージμが改ざんされている場合と、メッセージμが秘密鍵ｓｋの保有者以外によって送信された場合との少なくともいずれかの場合であるという意味である。
そして、検証部３１２は、メッセージμが不当であることを示す値０を出力する。
【００８８】
検証装置３０の動作の正当性を説明する。
図８のステップＳ２２２で生成された要素ｗ１と、図９のステップＳ３２で生成された要素ｗ’１とが等しければ、ハッシュ値ｃとハッシュ値ｃ’とが等しくなる。そこで、ここでは、要素ｗ１と要素ｗ’１とが等しくなることを説明する。
【００８９】
数５０のＵｓｅＨｉｎｔｑ（ｈ，ｒ，α）アルゴリズムにおけるｒに相当する部分は、数５２に示すようになる。
【数５２】
0006818949.tif 000043
【００９０】
ここで、数５３に示すｚ及びｔ１に基づき、数５２の１行目から２行目に変形される。
【数５３】
0006818949.tif 000044
括弧を展開することにより、数５２の２行目から３行目に変形される。
数５４に示すｔを代入することにより、数５２の３行目から４行目に変形される。
【数５４】
0006818949.tif 000045
括弧を展開することにより、数５２の４行目から５行目に変形される。
数５２における数５５及び数５６をキャンセルすることにより、数５２の５行目から６行目に変形される。ここで、補題２に基づき、数５５及び数５６はキャンセル可能である。
【数５５】
0006818949.tif 000046
【数５６】
0006818949.tif 000047
数５７に基づき、数５２の６行目から７行目に変形される。
【数５７】
0006818949.tif 000048
【００９１】
次に、数５０は、数５８に示すようになる。
【数５８】
0006818949.tif 000049
【００９２】
ここで、補題３の性質１に示すＵｓｅＨｉｎｔｑ（ＭａｋｅＨｉｎｔｑ（ｚ，ｒ，α），ｒ，α）＝ＨｉｇｈＢｉｔｓｑ（ｒ＋ｚ，α）におけるｚ，ｒ，ａは数５９に示す通りである。
【数５９】
0006818949.tif 000050
なぜなら、数５２に示すように、ＵｓｅＨｉｎｔｑ（ｈ，ｒ，α）アルゴリズムにおけるｒに相当する部分は、数６０であり、図８のステップＳ２２４では、署名要素ｈを数６１に示すように生成しているためである。
【数６０】
0006818949.tif 000051
【数６１】
0006818949.tif 000052
これにより、数５８の１行目から２行目に変形される。
【００９３】
数６２と数６３とをキャンセルすることにより、数５８の２行目から３行目に変形される。
【数６２】
0006818949.tif 000053
【数６３】
0006818949.tif 000054
数５８の３行目における数６４は小さい値である。そのため、上位ビットを出力するＨｉｇｈＢｉｔｓｑ（ｒ，α）アルゴリズムでは、無視し得る。したがって、数５８の３行目から４行目に変形される。
【００９４】
＊＊＊実施の形態１の効果＊＊＊
以上のように、実施の形態１に係る署名システム１では、署名装置２０は、メッセージμのハッシュ値ｃと秘密鍵ｓｋの要素ｓ１とのＭｉｄｄｌｅ−Ｐｒｏｄｕｃｔを計算して署名σの要素である署名要素ｚを生成する。また、検証装置３０は、署名σの要素である署名要素ｚと公開鍵ｐｋの要素ａとのＭｉｄｄｌｅ−Ｐｒｏｄｕｃｔを計算するとともに、署名σの要素であるハッシュ値ｃと公開鍵ｐｋの要素ｔ１とのＭｉｄｄｌｅ−Ｐｒｏｄｕｃｔを計算して、署名σを検証する。
これにより、ＭＰＬＷＥ仮定を安全性の根拠とすることが可能となり、量子コンピュータに対しても安全性が保証可能なディジタル署名方式を構成可能にすることができる。
【００９５】
＊＊＊他の構成＊＊＊
＜変形例１＞
実施の形態１では、各機能構成要素がソフトウェアで実現された。しかし、変形例１として、各機能構成要素はハードウェアで実現されてもよい。この変形例１について、実施の形態１と異なる点を説明する。
【００９６】
図１０を参照して、変形例１に係る鍵生成装置１０の構成を説明する。
各機能構成要素がハードウェアで実現される場合には、鍵生成装置１０は、プロセッサ１１とメモリ１２とストレージ１３とに代えて、電子回路１５を備える。電子回路１５は、各機能構成要素と、メモリ１２と、ストレージ１３との機能とを実現する専用の回路である。
【００９７】
図１１を参照して、変形例１に係る署名装置２０の構成を説明する。
各機能構成要素がハードウェアで実現される場合には、署名装置２０は、プロセッサ２１とメモリ２２とストレージ２３とに代えて、電子回路２５を備える。電子回路２５は、各機能構成要素と、メモリ２２と、ストレージ２３との機能とを実現する専用の回路である。
【００９８】
図１２を参照して、変形例１に係る検証装置３０の構成を説明する。
各機能構成要素がハードウェアで実現される場合には、検証装置３０は、プロセッサ３１とメモリ３２とストレージ３３とに代えて、電子回路３５を備える。電子回路３５は、各機能構成要素と、メモリ３２と、ストレージ３３との機能とを実現する専用の回路である。
【００９９】
電子回路１５，２５，３５としては、単一回路、複合回路、プログラム化したプロセッサ、並列プログラム化したプロセッサ、ロジックＩＣ、ＧＡ（Ｇａｔｅ  Ａｒｒａｙ）、ＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）、ＦＰＧＡ（Ｆｉｅｌｄ−Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ）が想定される。
各機能構成要素を１つの電子回路１５，２５，３５で実現してもよいし、各機能構成要素を複数の電子回路１５，２５，３５に分散させて実現してもよい。
【０１００】
＜変形例２＞
変形例２として、一部の各機能構成要素がハードウェアで実現され、他の各機能構成要素がソフトウェアで実現されてもよい。
【０１０１】
プロセッサ１１，２１，３１とメモリ１２，２２，３２とストレージ１３，２３，３３と電子回路１５，２５，３５とを処理回路という。つまり、各機能構成要素の機能は、処理回路により実現される。
【符号の説明】
【０１０２】
１  署名システム、１０  鍵生成装置、１１  プロセッサ、１２  メモリ、１３  ストレージ、１４  通信インタフェース、１５  電子回路、１１１  受付部、１１２  鍵生成部、１１３  送信部、１３１  鍵記憶部、２０  署名装置、２１  プロセッサ、２２  メモリ、２３  ストレージ、２４  通信インタフェース、２５  電子回路、２１１  受付部、２１２  署名生成部、２１３  出力部、２３１  鍵記憶部、３０  検証装置、３１  プロセッサ、３２  メモリ、３３  ストレージ、３４  通信インタフェース、３５  電子回路、３１１  受付部、３１２  検証部、３３１  鍵記憶部、４０  通信路。
【図１】
0006818949.tif 000066
【図２】
0006818949.tif 000067
【図３】
0006818949.tif 000068
【図４】
0006818949.tif 000069
【図５】
0006818949.tif 000070
【図６】
0006818949.tif 000071
【図７】
0006818949.tif 000072
【図８】
0006818949.tif 000073
【図９】
0006818949.tif 000074
【図１０】
0006818949.tif 000075
【図１１】
0006818949.tif 000076
【図１２】
0006818949.tif 000077