密码学的计算复杂性

【基本思想】

在计算复杂性理论中，P 与 NP 都是复杂性类（Complexity Classes），它们不是单个问题，而是由一类判定问题构成的集合

为了形式化地讨论判定问题，通常将判定问题表示为语言（Language）。设 $\Sigma$ 为一个有限字母表，则 $\Sigma^{*}$ 表示由 $\Sigma$ 中字符组成的所有有限长度字符串的集合。如果 $L\subseteq \Sigma^{*}$，则称 $L$ 是 $\Sigma$ 上的一个语言

在这种表示下，一个判定问题可以理解为：给定输入字符串 $x$，判断它是否属于语言 $L$。如果 $x\in L$，则答案为是；如果 $x\notin L$，则答案为否

因此，复杂性类 P 和 NP 本质上都是语言类：P 描述可以被高效求解的语言，NP 描述可以被高效验证的语言

【复杂性类 P】

复杂性类 P（Complexity Class P）是指所有可以由确定性多项式时间图灵机（Deterministic Polynomial-Time Turing Machine）判定的语言所构成的集合

直观来说，如果一个判定问题存在某种确定性算法，使得对于规模为 $n$ 的输入，该算法能够在 $O(n^k)$ 的时间复杂度内给出正确答案，那么这个判定问题就属于 P

形式化地，若语言 $L\subseteq \Sigma^{*}$ 属于 P，则存在一个确定性图灵机 $M$ 和一个多项式 $\mathrm{poly}(\cdot)$，使得对于任意输入字符串 $x$，都有：

1. $M$ 在至多 $\mathrm{poly}(|x|)$ 步内停机
2. 当且仅当 $x\in L$ 时，$M(x)=1$

其中，$M(x)=1$ 表示机器接受输入 $x$，即判定 $x$ 属于语言 $L$；而 $M(x)=0$ 表示机器拒绝输入 $x$，即判定 $x\notin L$

因此，P 可以理解为能够在确定性多项式时间内被判定的语言类。在非严格表述中，有时会说 P 问题，但更准确的说法是：属于 P 的判定问题

【复杂性类 NP】

复杂性类 NP（Complexity Class NP）并不是指不能在多项式时间内解决的问题，其描述的是这样一类判定问题：也许不知道如何在多项式时间内找到答案，但如果给出一个候选答案，那么可以在确定性多项式时间内验证这个答案是否正确。因此，NP 的核心不是求解容易，而是验证容易

NP 是非确定性多项式时间（Nondeterministic Polynomial Time）的缩写

需要注意的是，P 中的语言也一定属于 NP，即：

$$\mathcal{P}\subseteq \mathcal{NP}$$

原因是：如果一个语言本身就可以在确定性多项式时间内被判定，那么自然可以在确定性多项式时间内被验证。换句话说，能够高效求解的问题，一定能够高效验证；但能够高效验证的问题，是否一定能够高效求解，目前并不知道

形式化地，语言 $L\in \mathcal{NP}$，可以有两种等价理解：

一种是机器观点。$L$ 可以由某个非确定性多项式时间图灵机（Nondeterministic Polynomial-Time Turing Machine）识别

另一种是验证观点：如果一个语言 $L\in \mathcal{NP}$，那么存在一个多项式时间可判定的布尔关系：

$$R_{L} \subseteq \{0,1\}^{*} \times \{0,1\}^{*}$$

以及一个多项式 $\text{poly}(\cdot)$，使得对任意输入 $x$ 都有：

$$x\in L \Leftrightarrow \exists y,|y|\leq \mathrm{poly}(|x|) \wedge (x,y)\in R_{L}$$

其中，$y$ 被称为 $x\in L$ 的证据（Witness）

这个定义的含义是：如果输入 $x$ 确实属于语言 $L$，那么一定存在一个长度不超过 $|x|$ 的某个多项式的证据 $y$，并且可以在多项式时间内验证 $(x,y)$ 是否满足关系 $R_L$。如果验证通过，就说明 $x \in L$

因此，NP 可以理解为一类“存在短证据，并且证据可以被高效验证”的语言。

在密码学中，这种“寻找困难、验证容易”的结构非常重要。许多密码学任务都具有类似特点：敌手想找到某个秘密、伪造某个对象或破解某个实例可能很困难，但一旦给出候选结果，其正确性往往可以被高效检查

【多项式时间规约】

在讨论 NP 问题时，一个核心问题是：是否存在某些最难的 NP 问题，使得只要能够高效解决他们，就能高效解决所有 NP 问题？

为刻画这种问题之间的难度关系，复杂性理论引入了多项式规约（Polynomial Reduction）。直观来说，若问题 $A$ 能够在多项式时间内转换为问题 $B$，并且这种转化保持答案一致性，那么就说问题 $A$ 可以多项式时间归约到问题 $B$，记作：

$$A\leq _p B$$

其含义是：问题 $B$ 至少和问题 $A$ 一样难。也就是说，如果有一个能够高效解决问题 $B$ 的算法，那么就可以先把问题 $A$ 的输入转化为问题 $B$ 的输入，再调用问题 $B$ 的算法，从而高效解决问题 $A$

形式化地，对于两个语言 $L$ 和 $L’$，若存在一个多项式时间可计算函数 $f$，使得对任意输入 $x$，都有：

$$x \in L \Longleftrightarrow f(x) \in L'$$

则称语言 $L$ 可以多项式时间归约到语言 $L’$，记作：

$$L \leq_p L'$$

其中，函数 $f$ 的作用是把语言 $L$ 中的实例转化为语言 $L’$ 中的实例，并且保持答案不变

因此，若 $L \leq_p L’$，并且 $L’$ 可以在多项式时间内被判定，那么 $L$ 也可以在多项式时间内被判定

【NP-hard 与 NP-complete】

在多项式时间归约的基础上，可以定义 NP 难（NP-hard） 和 NP 完全（NP-complete）

若一个问题 $B$ 满足，对于任意语言 $L\in\mathcal{NP}$，都有：

$$L\leq_p B$$

则称 $B$ 是 NP 难（NP-hard） 的。这说明 NP 中的所有问题都可以在多项式时间归约到 $B$。因此，只要能够高效解决 $B$，就能够高效解决所有 NP 问题

需要注意的是，NP-hard 问题本身不一定属于 NP，也就是说，它不一定是一个证据可高效验证的判定问题，甚至可能不是判定问题

进一步，如果一个问题 $B$ 同时满足：

1. $B\in\mathcal{NP}$；
2. 对任意 $L\in\mathcal{NP}$，都有 $L\leq_p B$；

则称 $B$ 是 NP 完全（NP-complete） 的。因此，NP-complete 问题可以理解为 NP 内部最难的一类问题。它们一方面属于 NP，即解的正确性可以被高效验证；另一方面又足够难，因为所有 NP 问题都可以多项式时间归约到它们

【P=NP?】

有了 NP-complete 的概念之后，P 与 NP 的关系就可以更清楚地表达出来

如果存在某个 NP-complete 问题可以在确定性多项式时间内被解决，那么由于所有 NP 问题都可以多项式时间归约到它，因此所有 NP 问题都可以在确定性多项式时间内解决。此时就有：

$$\mathcal{P} = \mathcal{NP}$$

反过来说，如果能够证明某个 NP 问题不能在确定性多项式时间内解决，那么就可以证明：

$$\mathcal{P} \neq \mathcal{NP}$$

目前，P 与 NP 是否相等仍然是计算复杂性理论中的核心未解问题，但人们普遍相信 $\mathcal{P} \neq \mathcal{NP}$，即确实存在无法由确定性多项式时间算法判定的问题

【与密码学的关系】

P 与 NP 的讨论为密码学提供了重要的复杂性背景

密码学希望构造一些任务，使得合法用户可以高效完成，而敌手难以完成。因此，许多密码学问题都具有“验证容易、寻找困难”的形式。例如，给定一个候选解或候选密钥时，验证它是否正确可能很容易；但从公开信息中直接找到这个解或密钥则可能非常困难

不过，仅仅假设

$$\mathcal{P}\neq\mathcal{NP}$$

还不足以直接支撑现代密码学安全性，原因是密码学通常需要的是更强、更细致的困难性假设

因此，P 与 NP 的关系可以看作密码学复杂性基础的起点，但不是完整的密码学安全假设。现代密码学还需要进一步讨论概率多项式时间、非均匀多项式时间、平均情形复杂性以及具体的难解性假设