大規模な誤り耐性量子コンピュータが実現したとき、ショアのアルゴリズムによって安全性が大きく損なわれると考えられている暗号はどれか。

正解：A. RSA暗号や楕円曲線暗号などの公開鍵暗号

RSA暗号の安全性は大きな数の素因数分解の難しさに、楕円曲線暗号は離散対数問題の難しさに基づいています。ショアのアルゴリズムは、量子フーリエ変換を使って周期を求めることで、これらの問題を多項式時間で解けます。古典のコンピュータでは現実的な時間で解けない長さの鍵でも、十分大きな誤り耐性量子コンピュータがあれば解読できるようになります。AES などの共通鍵暗号に対しては、グローバーのアルゴリズムによる2乗の高速化しかなく、鍵を長くすることで対応できます。

• A. 正しい。素因数分解や離散対数問題が、多項式時間で解けるようになります。
• B. 共通鍵暗号への影響はグローバーのアルゴリズムによる2乗の高速化で、鍵を長くすれば対応できます。ショアのアルゴリズムが脅かすのは公開鍵暗号です。
• C. 真の乱数の鍵を1回だけ使うワンタイムパッドは、計算能力によらず解読できないことが証明されています。