|
電子情報通信学会 - IEICE会誌 試し読みサイト
© Copyright IEICE. All rights reserved.
|
|
|
電子情報通信学会 - IEICE会誌 試し読みサイト
© Copyright IEICE. All rights reserved.
|
耐量子計算機暗号の最新動向
10.
耐量子計算機暗号の安全性評価動向
Recent Progress in the Security Analysis of Post-quantum Cryptography
近年の量子コンピュータの性能進化に伴い，RSA暗号・だ円曲線暗号の危殆化が現実味を帯びてきた．2010年代後半から耐量子計算機暗号の開発が進み，それぞれ目的は異なるが米国・中国・韓国による暗号方式の募集が行われ現在も選定プロセスの途上である．合計で100以上の暗号方式が提案され，実用化に向けた評価と選定により候補が絞られる中で，暗号の安全性評価技術がかつてないほどの進展を見せている．本稿では，耐量子計算機暗号の安全性評価技術に関して，近年の評価理論と解読計算量評価の発展を概説する．
キーワード：暗号理論，耐量子計算機暗号，安全性評価，ポストムーア
耐量子計算機暗号の呼称でどの範囲の暗号技術を指すかは文献により微妙な差異があるが，本稿では公開鍵暗号と署名の中で古典・量子双方の計算機による攻撃が現実的なリソースでは困難であると信じられているものとする(1)．以下，これらを総称して暗号方式と呼ぶ．暗号方式の安全性評価は，求められる安全性要件の計算問題への還元を行う安全性証明と，具体的なパラメータ設定のための解読計算量評価の2段階に大別される．
安全性証明では公開鍵暗号のIND-CCA2，署名のEUF-CMAのようなデファクトスタンダードの安全性要件について，それらを破ることが別の計算問題を解くよりも困難であることを示す．具体的には，安全性を破る攻撃者の存在を仮定しオラクルとして呼ぶことで計算問題を効率的に解くという還元の議論を用いる．これにより，個別の暗号方式の安全性を同じ計算問題を土台として議論可能となる．
還元先の計算問題は安全性の根拠となる問題と呼ばれ，その種類により暗号が分類される．代表的な耐量子計算機暗号の分類として，格子問題を根拠とする格子暗号，符号問題を根拠とする符号ベース暗号，多変数方程式の求解問題を根拠とする多変数多項式暗号，代数曲面の求セクション問題を根拠とする代数曲面暗号，同種写像問題を根拠とする同種写像暗号，ハッシュ関数の第二原像攻撃の困難性を根拠とするハッシュベース署名などが存在する．
暗号方式の種類と安全性の根拠となる問題の対応を表1にまとめる．以下の2．では安全性証明の理論，3．では計算問題の困難性評価について述べる．
耐量子公開鍵暗号の形式による分類と根拠となる計算問題の対応について解説する．以下，公開鍵暗号
(KeyGen,Enc,Dec）の公開鍵，秘密鍵，平文，暗号文をそれぞれ
，
，
，
と表現する．一般的な構成手法として，落し戸一方向性関数
と対応する落し戸
により鍵を
，
，暗号化と復号を
，
とすることができる．関数が単射であれば
の逆元計算の困難性からOW-CPA安全性が示される．鍵復元の困難性は
から
を計算する問題の困難性となる．多変数公開鍵暗号は主にこの方式であり，一方向性関数と落し戸にそれぞれ多変数の2次関数が，平文復元，鍵復元の問題はそれぞれ連立2次方程式の求解問題（MQ問題），EIP問題が対応する．McEliece暗号（Niederreiter暗号）などの古典的な符号ベース暗号もこの形式を取っており，一方向性関数と落し戸は正則行列と線形符号の生成行列（パリティ検査行列）が，平文復元の問題にはMcEliece仮定（Niederreiter仮定）の下での探索版LPN問題が対応する．格子暗号ではNTRUがこの形式を用いており，平文復元，鍵復元の問題がそれぞれ最近ベクトル問題，最短ベクトル問題の変種に対応する．
一方向性関数からの直接の構成ではなく，ElGamal式の構成による公開鍵暗号も多く存在する．形式的には共有パラメータ
を用いて秘密鍵
，公開鍵
の順に鍵生成を行い，暗号化はEnc数内で生成した乱数
を用いて暗号文を暗号ランダムネス
とマスクされた平文
の組とする．復号は
の形で復号される．ここで，演算
は暗号系ごとに適切なものを用いるものとする．公開鍵暗号のIND-CPA安全性は攻撃者の
，
に対して
がランダムに選ばれ，
から元の
を推測する問題であるが，多くのElGamal式の暗号では生成された
に対して
が
であるか乱数であるかを識別する問題に還元される．この識別問題はElGamal暗号ではDDH問題であり，耐量子計算機暗号の中では多少の修正が必要なものの，格子暗号（Regev暗号(2)）の判定版LWE問題，代数曲面暗号（Giophantus(3)）のIE-LWE問題，同種写像暗号（SIKE(4)）のSSDDH問題が対応する．
ElGamal式の公開鍵暗号は双対形を定義することが可能である(5)．具体的には，
と
，
と
の役割を入れ替えることで
，
にそれぞれ秘密鍵，公開鍵の役割を与えることができ，暗号化時の乱数
を用いて暗号ランダムネス
とマスクされた平文
を計算，復号は
により行う形の公開鍵暗号が構成可能である．この対応は格子暗号のRegev暗号とGPV暗号の関係に相当する．双対形の識別問題は
から
を復元する問題で，
において
が
であるか乱数であるかを識別する問題に還元される．なお，この問題は元の暗号系では
から
に関わる情報を引き出す鍵復元問題に対応する．格子暗号では両方の問題がLWE問題へと還元されるため，平文と鍵の安全性が同じ問題を用いて議論可能となる．
続きを読みたい方は、以下のリンクより電子情報通信学会の学会誌の購読もしくは学会に入会登録することで読めるようになります。 また、会員になると豊富な豪華特典が付いてきます。
電子情報通信学会 - IEICE会誌はモバイルでお読みいただけます。
電子情報通信学会 - IEICE会誌アプリをダウンロード
