Vol.106 No.11 (2023/11)　目次へ

耐量子計算機暗号の最新動向

現行の公開鍵暗号方式に対するShorのアルゴリズムの脅威

Threat of Shor’s Algorithm to Current Public Key Cryptography

國廣　昇　高安　敦

区切り

國廣　昇　正員：シニア会員　筑波大学システム情報系情報工学域

高安　敦　東京大学大学院情報理工学系研究科数理情報学専攻

Noboru KUNIHIRO, Senior Member (Institute of Systems and Information Engineering, University of Tsukuba, Tsukuba-shi, 305-8573 Japan) and Atsushi TAKAYASU, Nonmember (Graduate School of Information Science and Technology, The University of Tokyo, Tokyo, 113-8656 Japan).

電子情報通信学会誌　Vol.106 No.11 pp.977-981 2023年11月

©電子情報通信学会2023

abstract

　RSA暗号やだ円曲線暗号は現在広く利用されている公開鍵暗号方式であり，情報社会の安全性の根幹を支える基盤技術となっている．これらの暗号方式が安全であるためには，それぞれ素因数分解やだ円曲線上の離散対数が効率的に計算できないことが必要となるが，Shorの量子アルゴリズムはこれらを多項式時間で計算できることが分かっている．問題の簡潔さから，素因数分解に対するShorのアルゴリズムは活発に議論されているが，それと比べてだ円曲線上の離散対数計算に関する研究はまだ発展途上である．そのため本稿では，だ円曲線上の離散対数計算を中心に，現行の公開鍵暗号方式に対するShorのアルゴリズムの脅威に関する結果を紹介する．

キーワード：量子コンピュータ，安全性評価，Shorのアルゴリズム，だ円曲線暗号

1．は　じ　め　に

1.1　公開鍵暗号と量子コンピュータ

　RSA暗号⁽¹⁾やだ円曲線暗号⁽²⁾は，現在実用的に利用されている代表的な公開鍵暗号方式である．一般に，公開鍵暗号方式の安全性は数学的問題の計算量的困難性との関連がある．特に，RSA暗号が安全であるためには素因数分解問題が計算量的に困難であることが必要であり，同様に，だ円曲線暗号が安全であるためにはだ円曲線上の離散対数問題が困難であることが必要である．素因数分解問題や離散対数問題は，現在一般的に普及している計算機を用いても効率的に解くことはできないと信じられている．例えば，これまで実験的に素因数分解された最大の合成数は795ビットである⁽³⁾が，RSA暗号では2,048ビットの合成数を用いることが2023年現在推奨されている．よって，現実的な攻撃が実用化されている暗号パラメータの問題を破るのは難しいと考えられる．

　この状況は，量子アルゴリズムを考慮に入れると大幅に変化し，Shorの量子アルゴリズム⁽⁴⁾により，素因数分解問題や離散対数問題は多項式時間で解けることが分かっている．そのため，量子コンピュータが使えるならば，現行の公開鍵暗号方式は安全性を保てないことになってしまい，情報社会に大きな影響を与えることが分かっている．より詳しい解説は，文献(５)を参照されたい．

続きを読みたい方は、以下のリンクより電子情報通信学会の学会誌の購読もしくは学会に入会登録することで読めるようになります。また、会員になると豊富な豪華特典が付いてきます。

続きを読む(PDF)　　　バックナンバーを購入する　　　　入会登録

電子情報通信学会 - IEICE会誌はモバイルでお読みいただけます。

電子情報通信学会誌会誌アプリのお知らせ

電子情報通信学会 - IEICE会誌アプリをダウンロード

特集 3. 現行の公開鍵暗号方式に対するShorのアルゴリズムの脅威

1．は じ め に

1.1 公開鍵暗号と量子コンピュータ

1．は　じ　め　に

1.1　公開鍵暗号と量子コンピュータ