证明系统安全的技术

Question

到目前为止，我已经看到了用约简技术证明密码系统的安全保证的证明，我们认为破解密码系统就像解决一个困难的数学问题一样困难。用于证明密码系统安全性的其他证明技术是什么？如果简明扼要地说明这一技术，那将是有益的。

Answer 1

这个问题提到了将证明归结为一个困难的数学问题(例如计算Diffie-Hellman)。这并不是证明密码系统安全性的唯一常用方法:我们通常假设存在一个密码构造块，它具有一些假定的密码性质，比如在密钥是随机的情况下，计算无法与随机排列区分的块，或者假设对手只能作为随机预言才能访问的散列，而不是数学问题的难度。

对于某些系统，我们通过信息论的论证直接证明了完全安全，例如在一次Pad中不能从密文中获得任何关于明文的信息。问题是，通过这条证明线可以证明安全性的系统都需要一个与所传输的整个明文一样大的密钥(如果假定明文是随机的)，因此是不切实际的。特别是，根据数学定义，任何密码都不可能是安全密码。因此，对于实际密码体制的证明，必须将信息论的论证线与证明相结合，通过约简和假设来证明。

我不知道密码系统的其他数学安全证明方法。我不知道有一个完整的安全数学证明的实用密码系统。即使我们在实用性上走捷径，安全密码的存在也意味着P≠NP，而我们并不存在。

然而，我们也有关于安全的论点。我们可以设计带有参数(特别是轮数和变量宽度)的密码系统或构建块(例如块密码或哈希)，检查当这些参数增长时用已知的密码分析方法打破它的难度有多大，并说服自己这种趋势会持续下去(这是最困难和最不确定的)；然后得出结论，如果参数足够大，我们就不会受到这些已知的攻击。

除了一次性Pad (可能与量子密钥分发相结合)这一罕见的例外，所有部署的密码系统都是合理的，可以信任地使用这一后来的论证。