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