計算量的安全性を持つ暗号
計算量的安全性は、大きく分けて2つの要因により低下する。
新たな解読手法が発見され、解読に必要な計算量が減少する場合
新型の計算機 (パソコンからスーパーコンピュータまで含む) が登場することで、解読に利用できる計算機能力が増大する場合
暗号の歴史は、暗号作成者が解読の手間が莫大で事実上解読は不可能(つまり計算量的に安全)だと考えて使用した暗号を、暗号解読者が数学的抜け道を発見することで解読した歴史でもある。計算量的安全性に加えて証明可能安全性を与えることで抜け道が残存する可能性を少なくすることができるが、サイドチャネル攻撃のように安全性に関する既存の前提を覆すような攻撃条件が見つかることもある。
また例えば仮に、量子コンピュータによってショアのアルゴリズムが現実的に実行可能になれば、素因数分解問題を多項式時間で解くことができるため、大きな数の素因数分解の難しさに依存したRSA暗号が安全でなくなる、といったようなものもある。しかし、2017年現在、提案されている手法で素因数分解するために必要なqubit数と、実現可能な(量子ゲート型の)量子コンピュータのqubit数の大きな隔たりにより、当面は現実的な脅威とは考えられていない。