主要观点：

• 密码学基于解决某些“困难”问题的计算难度，而非 NP-完全问题。
• NP-完全问题虽难快速求解但易验证解，且相互“等价”，如背包问题等。
• 密码学需要平均情况困难的问题，如 RSA 问题等，随机实例很难解（需超 2^128 次操作）。
• 利用 NP-完全问题做密码系统存在问题，因其不能保证随机实例困难。
• 有基于格的问题连接最坏情况和平均情况困难，但仍未基于 NP-完全问题的最坏情况困难得到加密方案。

关键信息：

• RSA 基于生成两个大随机质数 p 和 q，求其乘积 n = p·q 时求 p 的困难问题，且问题是随机化的，随机实例大多困难。
• NP-完全问题对所有实例无多项式时间算法求解，如三色地图着色问题，但随机实例不一定困难。
• 密码学需平均情况困难的问题，如椭圆曲线离散对数等。

重要细节：

• 2^128 是标准的大数字，有显著安全余量且是 2 的幂次方。
• 密码学方案依赖秘密钥使底层问题变简单，如 RSA 中 p 和 q 是秘密钥。
• 假设 P≠NP，否则世界会不同。
• 如 GapSVP 在某些参数设置下是 NP-难的，但不适用于密码学方案。