(57)【要約】      （修正有）【課題】格子代数に基づくポスト量子非対称鍵生成システムを提供する。【解決手段】ポスト量子非対称鍵生成システム１０は、ｐ（素数）ベクトルを生成するｐベクトル生成モジュール１１と、ｐベクトルに基づいてｐ配列を生成するｐ配列生成モジュール１３と、ｐ配列に基づいて関連行列を生成する関連行列生成モジュール１４と、関連行列と第１の基準素数ｐ１とに基づいて、第１の基準逆ｐ配列を取得する逆ｐ配列生成モジュール１５と、秘密鍵を生成する秘密鍵生成モジュール１７と、第２の逆ｐ配列に基づいて、秘密鍵とペアとなる公開鍵を取得する公開鍵生成モジュール１８を備える。第２の逆ｐ配列は、関連行列と、第１の素数ｐ１と、第２の素数ｐ２と、ランダム化配列とに基づいて取得される。【選択図】図２
2020052393.tif 000002
【特許請求の範囲】
【請求項１】
処理ユニットによって実施されるポスト量子非対称鍵生成方法であって、
【数１】
2020052393.tif 000062
【数２】
2020052393.tif 000063
【数３】
2020052393.tif 000064
【数４】
2020052393.tif 000065
【数５】
2020052393.tif 000066
【数６】
2020052393.tif 000067
【数７】
2020052393.tif 000068
ポスト量子非対称鍵生成方法。
【請求項２】
プロセッサ（２２）によって実行される暗号化方法であって、
請求項１に記載のポスト量子非対称鍵生成方法に従って生成された
【数８】
2020052393.tif 000069
暗号化方法。
【請求項３】
【数９】
2020052393.tif 000070
請求項２に記載の暗号化方法。
【請求項４】
前記暗号化の手順は、
【数１０】
2020052393.tif 000071
請求項２に記載の暗号化方法。
【請求項５】
プロセッサ（３２）によって実行される復号化方法であって、
【数１１】
2020052393.tif 000072
て生成される、
復号化方法。
【請求項６】
前記復号化の手順は、
【数１２】
2020052393.tif 000073
請求項５に記載の復号化方法。
【請求項７】
素数ｐと、シードとしての算術関数及び古典的な文字列の１つと、に基づいて、前記素数ｐに関連すると共に、
【数１３】
2020052393.tif 000074
【数１４】
2020052393.tif 000075
【数１５】
2020052393.tif 000076
【数１６】
2020052393.tif 000077
【数１７】
2020052393.tif 000078
【数１８】
2020052393.tif 000079
【数１９】
2020052393.tif 000080
ポスト量子非対称鍵生成システム（１０）。
【請求項８】
前記ｐ配列生成モジュール（１３）、前記基準素数判定モジュール（１６）、前記秘密鍵生成モジュール（１７）、前記公開鍵生成モジュール（１８）、と連結すると共に、
【数２０】
2020052393.tif 000081
請求項７に記載のポスト量子非対称鍵生成システム（１０）。
【請求項９】
前記公開鍵生成モジュール（１８）は、
【数２１】
2020052393.tif 000082
請求項８に記載のポスト量子非対称鍵生成システム（１０）。
【請求項１０】
鍵サーバ（１）と、送信端（２）と、受信端（３）と、を含んでいる暗号化通信システム（１００）であって
該鍵サーバ（１）は、
【数２２】
2020052393.tif 000083
【数２３】
2020052393.tif 000084
【数２４】
2020052393.tif 000085
【数２５】
2020052393.tif 000086
【数２６】
2020052393.tif 000087
【数２７】
2020052393.tif 000088
【数２８】
2020052393.tif 000089
【数２９】
2020052393.tif 000090
【数３０】
2020052393.tif 000091
【数３１】
2020052393.tif 000092
暗号化通信システム（１００）。
【請求項１１】
【数３２】
2020052393.tif 000093
請求項１０に記載の暗号化通信システム（１００）。
【請求項１２】
前記第１のプロセッサ（２２）は、暗号化ランダム化関数生成モジュール（２２２）と、前記テキスト変換モジュール（２２１）及び前記暗号化ランダム化関数生成モジュール（２２２）と連結する暗号文生成モジュール（２２３）と、を有し、且つ、
【数３３】
2020052393.tif 000094
請求項１１に記載の暗号化通信システム（１００）。
【請求項１３】
前記第２のプロセッサ（３２）は、第１の畳み込みモジュール（３２１）と、前記第１の畳み込みモジュール（３２１）と連結する第２の畳み込みモジュール（３２２）と、を有し、
【数３４】
2020052393.tif 000095
【数３５】
2020052393.tif 000096
請求項１０に記載の暗号化通信システム（１００）。
【請求項１４】
【数３６】
2020052393.tif 000097
請求項１０に記載の暗号化通信システム（１００）。
【請求項１５】
前記鍵サーバ（１）は、前記ｐ配列生成モジュール（１３）、前記基準素数判定モジュール（１６）、前記秘密鍵生成モジュール（１７）、前記公開鍵生成モジュール（１８）、と連結する記憶モジュール（１９）を更に含み、且つ、
【数３７】
2020052393.tif 000098
請求項１４に記載の暗号化通信システム（１００）。
【請求項１６】
前記公開鍵生成モジュール（１８）は、
【数３８】
2020052393.tif 000099
前記鍵サーバ（１）は、前記第２の通信チャネル（Ｃ２）を介して前記更新された公開鍵K*publicを前記送信端（２）に送信し、
前記鍵サーバ（１）から前記更新された公開鍵K*publicを前記送信端（２）を受信すると、前記第１のプロセッサ（２２）は前記第１の記憶ユニット（２１）に記憶されている前記公開鍵Kpublicを前記更新された公開鍵K*publicになるように更新し、
【数３９】
2020052393.tif 000100
【数４０】
2020052393.tif 000101
請求項１５に記載の暗号化通信システム（１００）。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、非対称鍵生成方法に関し、特に、格子代数に基づくポスト量子非対称鍵生成方法及びシステム、鍵リフレッシュ方法、暗号化の方法、復号化の方法、及び暗号化通信システムに関する。
【背景技術】
【０００２】
従来の暗号システムは、対称鍵アルゴリズムと非対称鍵アルゴリズムの２つの主要なカテゴリに分類することができる。ＡＥＳ（Advanced Encryption Standard）のような対称鍵アルゴリズムは、共有鍵を使用して暗号化と復号化を実行する。非対称鍵アルゴリズムは、異なっている鍵、具体的には公開鍵と秘密鍵のペアを利用して暗号化と復号化を実行する。例えば、ＲＳＡは、最初の公開鍵暗号システムの1つであり、且つ、データの安全な伝送に広く使用されている（「Rivest, R.L., Shamir. A., Adleman, L.：デジタル署名を取得するための方法及び公開鍵暗号システム。Communications of the ACM 21（2）、120-126（1978）」を参照）。ＮＴＲＵ（number theory research unit）は、他の非対称鍵アルゴリズムであり（「J. Hoffstein, J. Pipher, and J. H. Silverman, 『Ntru: リングベースの公開鍵暗号システム』、International Algorithmic Number Theory Symposium, pp. 261-288, Springer, 1998」を参照）、そして、ＥＣＣ（elliptic curve cryptography）は、楕円曲線の代数構造に基づく公開鍵暗号へのアプローチである。対称鍵アルゴリズムの実施には、２者間の鍵交換用のセキュア通信路を必要とする。セキュア通信路は、非対称鍵アルゴリズムの実施に必要ではないが、非対称鍵アルゴリズムは、鍵ペアの生成、暗号化、及び復号化のために、比較的大きな計算が必要とされ得る。ＲＳＡと比較して、ＥＣＣはより優れた安全性を提供することができるが、暗号化と復号化にはより多くの時間を要する。
【０００３】
古典的な暗号システムには、次の欠点を有する。
１．暗号化と復号化は一度に１文字ずつ実行されるため、現在の非対称鍵アルゴリズムのプロトコルは短時間に大量のデータを送信することができない。
【０００４】
２．現在の非対称鍵アルゴリズムは、同じ代数群、環又はベクトル空間に属すると共に、本質的に類似しているような同じ数学的特性を有する公開鍵と、秘密鍵と、を利用するため、平文攻撃、又は、総当たり攻撃に遭い易い。
【０００５】
３．現在の非対称鍵アルゴリズムに対しては、ユーザが自分の公開鍵を新しいものに変更する場合に、他のすべてのユーザが新しい公開鍵とペアになるように自分の秘密鍵を更新する必要があり、そうでなければ、さもないと、古い秘密鍵を使い続けているユーザから試みられ得るあらゆる通信が無効にされる。
【０００６】
４．システムのセットアップのためにユーザ全員が鍵のリフレッシュを実行する必要がある場合に、鍵のリフレッシュ時間を示す集中エンティティを必要とする。
【０００７】
５．整数因数分解に基づくアルゴリズム(例えば、ＲＳＡ、ＤＳＡ)、或いは、離散対数問題に基づくアルゴリズム(例えば、ＥＣＣ)は、ショアのアルゴリズム、及び、グローバーのアルゴリズムに基づくポスト量子攻撃に対して弱い。
【０００８】
６．ＲＳＡ、ＡＥＳ、ＮＴＲＵを使用しているネットワークにおいては、分散鍵リフレッシュがこれらの暗号システム用のプロトコルの基本定義の一部ではないので、分散鍵リフレッシュが存在しない。
【０００９】
７．古典的な公開鍵暗号システムは、密結合としている公開-秘密鍵（即ち、各公開鍵は唯一の秘密鍵とのみペアになっている）を有する。ペアになっている鍵の１つへの攻撃は、他の１つの鍵の情報をしばしば表す。
【発明の概要】
【発明が解決しようとする課題】
【００１０】
したがって、本発明の目的は、従来技術の少なくとも１つの欠点を軽減することができる格子代数に基づくポスト量子非対称鍵生成方法及びシステム、鍵リフレッシュメカニズム、暗号化の方法、復号化の方法、暗号化通信システム、を提供することにある。
【課題を解決するための手段】
【００１１】
本発明によれば、処理ユニットによって実施されるポスト量子非対称鍵生成方法であって、
【００１２】
【数１】
2020052393.tif 000003
【００１３】
（Ｂ）インスタンスの概念をＩ＝（ｐ、ｓ、ｔ）として定義し、ｐが素数であり、そしてｓとｔがユーザ定義の正の整数であり、
【００１４】
【数２】
2020052393.tif 000004
【００１５】
【数３】
2020052393.tif 000005
【００１６】
【数４】
2020052393.tif 000006
【００１７】
【数５】
2020052393.tif 000007
【００１８】
【数６】
2020052393.tif 000008
【００１９】
【数７】
2020052393.tif 000009
【００２０】
本発明によれば、プロセッサによって実行される暗号化方法であって、
【００２１】
【数８】
2020052393.tif 000010
【００２２】
本発明によれば、プロセッサによって実行される復号化方法であって、
【００２３】
【数９】
2020052393.tif 000011
【００２４】
本発明によれば、ポスト量子非対称鍵生成システムは、
【００２５】
【数１０】
2020052393.tif 000012
【００２６】
【数１１】
2020052393.tif 000013
【００２７】
【数１２】
2020052393.tif 000014
【００２８】
【数１３】
2020052393.tif 000015
【００２９】
【数１４】
2020052393.tif 000016
【００３０】
【数１５】
2020052393.tif 000017
【００３１】
【数１６】
2020052393.tif 000018
【００３２】
本発明によれば、鍵サーバと、送信端と、受信端と、を含んでいる暗号化通信システムであって、
該鍵サーバは、
【００３３】
【数１７】
2020052393.tif 000019
【００３４】
【数１８】
2020052393.tif 000020
【００３５】
【数１９】
2020052393.tif 000021
【００３６】
【数２０】
2020052393.tif 000022
【００３７】
【数２１】
2020052393.tif 000023
【００３８】
【数２２】
2020052393.tif 000024
【００３９】
【数２３】
2020052393.tif 000025
【００４０】
【数２４】
2020052393.tif 000026
【００４１】
【数２５】
2020052393.tif 000027
【００４２】
【数２６】
2020052393.tif 000028
【００４３】
【数２７】
2020052393.tif 000029
【００４４】
本発明の他の特徴および利点は、添付の図面を参照する以下の実施形態の詳細な説明において明白になるであろう。
【図面の簡単な説明】
【００４５】
【図１】本発明に係る暗号化通信システムの一実施形態を示すブロック図である。
【図２】暗号化通信システムの鍵サーバを示すブロック図である。
【図３】本発明に係る鍵生成の手順のステップを示すフローチャートである。
【図４】本発明に係る鍵生成の手順のステップを示すフローチャートである。
【図５】該暗号化通信システムの送信端を示すブロック図である。
【図６】該暗号化通信システムの受信端を示すブロック図である。
【図７】本発明に係る暗号化の手順のステップを示すフローチャートである。
【図８】本発明に係る復号化の手順のステップを示すフローチャートである。
【発明を実施するための形態】
【００４６】
本発明をより詳細に説明する前に、適切と考えられる場合において、符号又は符号の末端部は、同様の特性を有し得る対応の又は類似の要素を示すために各図面間で繰り返し用いられることに留意されたい。
【００４７】
図１に示されているように、本発明に係る暗号化通信システム１００の実施形態は、鍵サーバ１と、複数のユーザエンドと、を含むように示されている。各ユーザエンドは、暗号化の手順、及び、復号化の手順を使用する通信プロトコルに基づいて他のユーザエンドと通信することができる。各ユーザエンドは、メッセージを送信する場合には送信端と成り得ると共に、メッセージを受信する場合に、受信端と成り得る。図１は、１つが送信端２となり、他の１つが受信端３となる２つのユーザエンドを単に例示しているが、本発明はこれに限定されない。送信端２は、記憶ユニット２１と、記憶ユニット２１に連結されているプロセッサ２２とを含む。送信端３は、記憶ユニット３１と、記憶ユニット３１に連結されているプロセッサ２２とを含む。本実施形態では、鍵サーバ１は送信端２及び受信端３から独立している。しかしながら、他の実施形態では、鍵サーバ１は送信端２内に組み込まれ得る。
【００４８】
鍵サーバ１は、ポスト量子非対称鍵生成システム１０によって構成されている処理装置（図示せず）を有することができる。図２に示されているように、ポスト量子非対称鍵生成システム１０は、ｐベクトル（素数ベクトル）生成モジュール１１と、ｐベクトル生成モジュール１１と連結するｐ配列（素数配列）生成モジュール１３と、ｐ配列生成モジュール１３と連結する関連行列生成モジュール１４と、関連行列生成モジュール１４と連結する逆ｐ配列生成モジュール１５と、基準素数判定モジュール１６と、逆ｐ配列生成モジュール１５及び基準素数判定モジュール１６と連結する秘密鍵生成モジュール１７と、逆ｐ配列生成モジュール１５及び基準素数判定モジュール１６と連結する公開鍵生成モジュール１８と、ｐ配列生成モジュール１３、基準素数判定モジュール１６、秘密鍵生成モジュール１７、公開鍵生成モジュール１８と連結する記憶モジュール１９と、を含む。ここで、ｐベクトル生成モジュール１１と、ｐ配列生成モジュール１３と、関連行列生成モジュール１４と、逆ｐ配列生成モジュール１５と、基準素数判定モジュール１６と、秘密鍵生成モジュール１７と、公開鍵生成モジュール１８とは、プロセッサ（図示せず）内に統合され得るが、本発明はこれに限定されない。
【００４９】
暗号化通信システム１００を使用する前に、鍵サーバ１は、暗号化及び復号化のために、非対称鍵（例えば、秘密鍵と、秘密鍵とペアになっている少なくとも１つの公開鍵）を生成する。図３と図４は、図２に例示されているポスト量子非対称鍵生成システム１０がどのように非対称鍵生成手順を実行するかを共に例示する。
【００５０】
【数２８】
2020052393.tif 000030
【００５１】
【数２９】
2020052393.tif 000031
【００５２】
【数３０】
2020052393.tif 000032
【００５３】
【数３１】
2020052393.tif 000033
【００５４】
上記した２つの例は、シード及び第１のパラメータセットＩに基づいてｐ配列がどのように生成されるかを例示的に示している。第１のパラメータセットＩを保存することによって、対応するｐ配列は、いつでもシードに基づいて取得され得る。
【００５５】
【数３２】
2020052393.tif 000034
【００５６】
ｐ配列生成モジュール１３は、ｐ配列のいずれか１つのｍ個の成分が０であると判定する場合に、ユーザに異なる第１のパラメータセットＩを適用するために（即ち、新しい第１のパラメータセットＩ内の素数ｐ、及び、パラメータｓ、ｔの少なくとも１つが、元の第１のパラメータセットＩ内のものと異なっている）、フローはステップＳ３２に戻る。ステップＳ３３における判定が肯定的になるまで、ステップＳ３２は異なる第１のパラメータセットＩで繰り返され得る。
【００５７】
【数３３】
2020052393.tif 000035
【００５８】
【数３４】
2020052393.tif 000036
【００５９】
【数３５】
2020052393.tif 000037
【００６０】
【数３６】
2020052393.tif 000038
【００６１】
【数３７】
2020052393.tif 000039
【００６２】
【数３８】
2020052393.tif 000040
【００６３】
【数３９】
2020052393.tif 000041
【００６４】
【数４０】
2020052393.tif 000042
【００６５】
【数４１】
2020052393.tif 000043
【００６６】
本実施形態では、プロセッサ２２は、テキスト変換モジュール２２１と、暗号化ランダム化関数生成モジュール２２２と、テキスト変換モジュール２２１及び暗号化ランダム化関数生成モジュール２２２と連結する暗号文生成モジュール２２３と、を有するように構成されている。
【００６７】
【数４２】
2020052393.tif 000044
【００６８】
【数４３】
2020052393.tif 000045
【００６９】
【数４４】
2020052393.tif 000046
【００７０】
言い換えると、暗号化ランダム化関数生成モジュール２２２は、異なる暗号化ランダム化配列を使用することによって、異なる暗号化ランダム化関数を生成することができる。
【００７１】
【数４５】
2020052393.tif 000047
【００７２】
【数４６】
2020052393.tif 000048
【００７３】
【数４７】
2020052393.tif 000049
【００７４】
【数４８】
2020052393.tif 000050
【００７５】
【数４９】
2020052393.tif 000051
【００７６】
【数５０】
2020052393.tif 000052
【００７７】
【数５１】
2020052393.tif 000053
【００７８】
【数５２】
2020052393.tif 000054
【００７９】
【数５３】
2020052393.tif 000055
【００８０】
【数５４】
2020052393.tif 000056
【００８１】
【数５５】
2020052393.tif 000057
【００８２】
【数５６】
2020052393.tif 000058
【００８３】
【数５７】
2020052393.tif 000059
【００８４】
【数５８】
2020052393.tif 000060
【００８５】
したがって、上記の詳細な説明より以下のことが分かる。
【００８６】
１．ポスト量子非対称鍵生成システム１０は、単一の算術関数、或いは、古典的な文字列のみで、第１のパラメータセットＩと第２のパラメータセットＳと第１の基準素数ｐ１及び第２の基準素数ｐ２との異なる組み合わせと共に利用することによって、非対称鍵生成の手順を実行して複数の秘密鍵を生成することができる。
【００８７】
２．特定の秘密鍵に対して、ポスト量子非対称鍵生成システム１０は、速やかであり、且つ、秘密鍵の再計算を必要としないソフト鍵リセットアルゴリズムの利用によってそれぞれが秘密鍵とペアになっている複数の公開鍵を生成することができることで、鍵サーバ１が鍵リフレッシュをより容易に実行することができる。
【００８８】
３．ｐ配列を生成するための方法が単一ではない。ゼロパディングによって、あるいはｐ配列の作成にランダム性を追加することによってランダム性をｐベクトルに追加することができる。
【００８９】
４．総当たり攻撃に対する難易度を高めるように、より大きいパラメータｍを選択することによって鍵空間を増加することができる。本実施形態では、ｍ＝５、ｐ１＝２５１とする選択は、説明の便宜上のためのみである。ｍ＝１６更にはｍ＝６４の場合に、可能な鍵空間が非常に大きくなるために、総当たり攻撃の成功には、べらぼうな時間がかかる。メッセージ空間と鍵空間のサイズは、膨大な数の可能性を含み、総当たり攻撃を不可能にする。
【００９０】
表１は、オクタコアプロセッサ、及び、３２ＧＢ  ＲＡＭ（ランダムアクセスメモリ）のハードウェアの仕様の下で、暗号化通信システム１００を利用して異なるメッセージの長さに対して行なう暗号化と復号化に必要な時間の実験結果を列挙する。
【００９１】
【表１】
2020052393.tif 000061
【００９２】
表１のデータに基づくと、本発明に係る暗号化通信システム１００を利用すると、メッセージの長さにかかわらず、従来のＡＥＳ及びＲＳＡプロトコルと比較して暗号化及び復号化に必要な時間を数百分の一に減らすことができることがわかる。明らかに、本発明に係る暗号化通信システム１００は、暗号化及び復号化の速度を大いに向上させることができる。
【００９３】
本発明に係る実施形態では、公開鍵と秘密鍵とは、算術関数又は古典的な文字列、ｐベクトル、本質的にベクトルであるｐ配列に基づいて生成され、比較的大量のデータに対する暗号化及び復号化を可能にし、それによって、暗号化及び復号化の速度を向上させ、データの安全性を確保する。提案された暗号化通信システムは、ポスト量子セキュリティ、具体的にはポスト量子コンピュータからの攻撃に効果的に抵抗することができることを確保することができる。ｐベクトル及びｐ配列の特性のため、本実施形態を実施するためのハードウェア要求は、記憶容量及び／又は計算能力に関して比較的に低い。本実施形態は、秘密鍵の使用に影響を与えることなく、公開鍵のリフレッシュを可能にし、同じネットワーク内のすべてのユーザに対して分散鍵リフレッシュを可能にする。更に、秘密鍵を作るために使用される算術関数fは、無限量のデータを生成することができる関数であるので、単一の関数だけで複数の異なる公開鍵を生成することができる。
【００９４】
上記の説明では、説明の目的のために、実施形態の完全な理解を提供するために多数の特定の詳細が述べられた。しかしながら、しかしながら、当業者であれば、一またはそれ以上の他の実施形態が具体的な詳細を示さなくとも実施され得ることが明らかである。また、本明細書における「一つの実施形態」「一実施形態」を示す説明において、序数などの表示を伴う説明はすべて、特定の態様、構造、特徴を有する本発明の具体的な実施に含まれ得るものであることと理解されたい。更に、本説明において、時には複数の変化例が一つの実施形態、図面、またはこれらの説明に組み込まれているが、これは本説明を合理化させるためのもので、本発明の多面性が理解されることを目的としたものであり、また、一実施形態における一またはそれ以上の特徴あるいは特定の具体例は、適切な場合には、本開示の実施において、他の実施形態における一またはそれ以上の特徴あるいは特定の具体例と共に実施され得る。
【００９５】
以上、本発明の好ましい実施形態および変化例を説明したが、本発明はこれらに限定されるものではなく、最も広い解釈の精神および範囲内に含まれる様々な構成として、すべての修飾および均等な構成を包含するものとする。
【符号の説明】
【００９６】
１  鍵サーバ
２  送信端
３  受信端
１０  ポスト量子非対称鍵生成システム
１１  ｐベクトル生成モジュール
１３  ｐ配列生成モジュール
１４  関連行列生成モジュール
１５  逆ｐ配列生成モジュール
１６  基準素数判定モジュール
１７  秘密鍵生成モジュール
１８  公開鍵生成モジュール
１９  記憶モジュール
２１  記憶ユニット
２２  プロセッサ
３１  記憶ユニット
３２  プロセッサ
【図１】
2020052393.tif 000102
【図２】
2020052393.tif 000103
【図３】
2020052393.tif 000104
【図４】
2020052393.tif 000105
【図５】
2020052393.tif 000106
【図６】
2020052393.tif 000107
【図７】
2020052393.tif 000108
【図８】
2020052393.tif 000109
【外国語明細書】
2020052393000001.pdf