量子計算機時代と数式処理

摘要

私が暗号に関する研究を本格的に始めてから10年くらいが経とうとしています.不可抗力的な流れで，近年の私の研究課題や仕事は耐量子計算機暗号に関するものが多くなっています.耐量子計算機暗号を説明するために，まずはRSA暗号と楕円曲線暗号から話を始めます.RSA暗号と楕円曲線暗号は現在広く使用されている公開鍵暗号です.RSA暗号の安全性は「二っの相異なる素数の積を素因数分解する計算」の困難性に依存しています.また，楕円曲線暗号の安全性は「楕円曲線上の有理点のなす群における離散対数問題を解く計算」の困難性を基盤としています.これら二っの計算問題は大規模な量子計算機とShorのアルゴリズムによって多項式時間で計算できるため，量子計算機時代ではRSA暗号と楕円曲線暗号の安全性が大きく低下することが懸念されています.整数の素因数分解や離散対数問題とは別の計算問題を安全性の根拠とする暗号は，現時点では耐量子計算機暗号とよばれており，代表的なものとして格子暗号，符号暗号，多変数公開鍵暗号，同種写像暗号等が挙げられます.（注意として，これは現時点での話であり，例えば，格子暗号の安全性の根拠とされる計算問題（最近ベクトル問題等）を効率よく解く量子アルゴリズムが発見されてしまうと格子暗号は耐量子計算機暗号ではなくなってしまいます.）