|
電子情報通信学会 - IEICE会誌 試し読みサイト
© Copyright IEICE. All rights reserved.
|
|
|
電子情報通信学会 - IEICE会誌 試し読みサイト
© Copyright IEICE. All rights reserved.
|
耐量子計算機暗号の最新動向
6.
多変数多項式暗号の最近の研究について
Recent Study in Multivariate Public Key Cryptography
多変数多項式暗号は有限体上の多変数連立2次方程式の求解困難性を利用した暗号であり，耐量子計算機暗号の一種として活発に研究されている．その中でも署名方式UOVは安全な方式として知られており，その改良方式RainbowはNIST PQC標準化計画において第3ラウンドまで駒を進めた．しかし，Rainbow特有の構造を利用した有効な攻撃方法が最近発見され，標準化までには至らなかった．本稿では，この二つの方式の構成を解説し，更に最近行われているRainbowとは異なったUOVの改良に関する研究動向についても解説する．
キーワード：耐量子計算機暗号，多変数多項式暗号，UOV，Rainbow
多変数多項式暗号とは連立2次方程式の求解困難性を利用した公開鍵暗号である．例えば，図1のような有限体
上の連立2次方程式を考えてみる．この方程式の解を求める（難しい理論を使わない恐らく唯一の）手法として総当たり法がある．変数
に
から
までの整数をそれぞれ代入し等式が成り立つかをチェックする方法である．これは，一回の代入計算は四則演算のみで簡単に行えるが，解を探索するためには最大
回の代入を行う必要があるため，一般には短時間で解を見つけることは難しい．更に方程式のサイズ（変数や多項式の個数）が増えれば，計算時間は指数関数的に増えてしまう．また，難しい理論（グレブナー基底など）を使ったとしてもサイズが大きな連立2次方程式を短時間で解く方法は知られていない．実際，有限体
上の連立2次方程式の解を求める問題はMQ問題（Multivariate Quadratic equations problem）と呼ばれるが，これは計算量理論においてNP困難であるということが示されている．
続きを読みたい方は、以下のリンクより電子情報通信学会の学会誌の購読もしくは学会に入会登録することで読めるようになります。 また、会員になると豊富な豪華特典が付いてきます。
電子情報通信学会 - IEICE会誌はモバイルでお読みいただけます。
電子情報通信学会 - IEICE会誌アプリをダウンロード
