【现代密码学中的计算差距】
现代密码学建立在一种基本差距之上：对于合法用户来说，某些算法应当是高效可用的；对于非法敌手来说，滥用或破解这些算法应当在计算上不可行
可以集中考虑一个典型密码学任务：安全数据通信（Secure Data Communication），即加密方案（Encryption Schemes）。
在安全的加密方案中，合法用户应当能够利用自己掌握的某些私有信息轻松解密消息，而没有这些私有信息的敌手，即使获得了密文，也不应当能够高效地解密。另一方面，一个非确定性机器可以快速解密密文，例如它可以通过猜测私有信息的方式完成解密
因此，如果安全加密方案存在，就意味着存在某些任务，可以由非确定性多项式时间机器完成，但不能由确定性多项式时间机器，甚至不能由随机化多项式时间机器完成。
因此，安全加密方案存在的一个必要条件是：
由于 $\mathrm{P}\subseteq \mathrm{BPP}$，这也意味着：
虽然 $\mathrm{P}\neq \mathrm{NP}$ 是现代密码学成立的必要条件，但它并不是充分条件。原因在于，密码学安全性不能只依赖最坏情形困难性
假设某个加密方案的破解问题是 NP 完全的，那么 $\mathrm{P}\neq \mathrm{NP}$ 只能说明这个加密方案在最坏情形下难以破解，但这并不能排除另一种可能：该加密方案在绝大多数情况下都很容易被破解
事实上，可以构造某些加密方案，其破解问题是 NP 完全的，但仍然存在一个高效破解算法，能够在 $99\%$ 的情况下成功破解。因此，最坏情形困难性并不是衡量安全性的合适标准
密码学安全性需要的是大多数情况下的困难性，或者至少是平均情形困难性。因此，安全加密方案存在的一个必要条件是：在 NP 中存在平均情形下困难的语言
但目前尚不清楚 $\mathrm{P}\neq \mathrm{NP}$ 是否能够推出 NP 中存在平均情形困难的语言，即使存在平均情形困难的问题，也仍然不足以直接支撑安全加密方案。原因在于，合法用户也需要能够高效解决相关问题
为了让这类平均困难问题在密码学中发挥作用，不仅需要能够生成困难实例，还需要同时生成某种辅助信息，使合法用户可以利用该辅助信息快速解决这些困难实例。否则，这些困难实例不仅对敌手困难，对合法用户同样困难，合法用户就无法相对于敌手获得计算优势
因此，安全加密方案的存在进一步意味着：存在一种高效方式，也就是一个概率多项式时间算法，能够生成实例及其对应的辅助输入，并满足：
- 给定辅助输入时，实例容易求解：合法用户掌握辅助信息，因此可以高效完成解密或求解任务
- 不给定辅助输入时，实例在平均意义下难以求解：敌手没有辅助信息，因此即使面对大量随机生成的实例，也难以高效求解
【单向函数的动机】
宽泛来说，单向函数是一类容易正向计算、但在平均意义下难以反向求逆的函数。即给定输入 $x$，计算 $f(x)$ 是容易的，但仅给定输出 $f(x)$，想要恢复出某个对应的输入 $x$，在平均情形下是困难的
因此，单向函数刻画的是这样一种困难性：生成实例的过程是高效的，但想要反向恢复生成过程中的辅助信息却是困难的
正是这种正向容易、反向困难的不对称性，造成了合法用户和敌手之间的计算差距
单向函数存在性假设可以看作日常经验在计算复杂性理论中的类比，有些过程天然具有方向性，正向发生容易，反向恢复困难。例如，点燃一根火柴很容易，但想要把燃烧后的状态恢复为未点燃的火柴则非常困难
密码学正是把这种直观现象形式化为计算意义下的困难性，并以此作为构造安全机制的基础
【单向函数的基本定义】
宽泛来说，单向函数是一类容易计算但难以反演的函数，其包含两个条件：
- 容易计算：存在一个多项式时间算法，给定输入 $x$ 后可以输出 $f(x)$
- 难以反演：任意概率多项式时间算法，在给定 $y=f(x)$ 后，想要找到某个满足 $f(x’)=y$ 的原像 $x’$，其成功概率都是可忽略的
难以反演不是说反演永远不可能成功，而是说任何高效反演算法的成功概率都必须非常小，即随着输入长度增长而快于任意多项式倒数趋近于 $0$
