計算量的安全性を持つ暗号
暗号理論における計算量的安全性（けいさんりょうてきあんぜんせい）とは、以下のことを言う。
- 解読にかかる計算量が、膨大であるので安全ということ
- 計算量は、場合の数（順列組み合わせ）で計算している
- 暗号を解読する事が出来るが、情報の重要性、新鮮性によって、必要な時間の間だけ解読不可能であること。
- 例えば、最大3年かかる合併交渉に使う暗号は、スーパーコンピュータで10年解読出来ない暗号を使えば大丈夫であろう。
- しかし、例えば巨大国際企業が、自分の全てのコンピュータの空き時間を競争相手の暗号解読に使う事態を考えると、安全性は急速に消滅する。
また暗号の歴史は、作成者が計算量的に安全であると言われたものを数学的抜け道の発見で解読した歴史でもある。また、ムーアの法則でコンピュータの性能が増加しているので、安全性は常に減少している。
量子コンピュータを使うと、RSA暗号、ElGamal暗号といった代表的な公開鍵暗号方式を数秒以内に解読できると言われる。また、全ての秘密鍵暗号も数秒以内に解読可能といわれている。
計算量的安全性が信頼されない典型的な例は、単一換字暗号である。（例えばＡをＧ、ＺをＰになど。「黄金虫」で使用）組み合わせ的には26！あるはずで、人智では解けないはずだが、普通のプロの暗号解読者は普通文と同じ速さで読める。素人でも「黄金虫」「踊る暗号」を読めば簡単に解読できるようになる。