【难解任务】

在计算复杂性理论下，密码学通常把那些不能由概率多项式时间模型完成的任务视为难解任务（Intractable Tasks）。也就是说，如果一个攻击任务不能被任何概率多项式时间模型有效完成，那么它就可以作为密码学安全性的基础

这里之所以使用概率多项式时间敌手模型，是因为密码学中的敌手通常被允许使用随机性。例如，敌手在进行攻击加密方案、伪造数字签名等任务时，都可以采用随机化攻击策略。因此，密码学中的高效敌手通常不是确定性多项式时间模型，而是概率多项式时间模型

【非均匀多项式时间模型的两种观点】

非均匀多项式时间（Non-uniform Polynomial Time）模型，是一种比普通多项式时间模型更强的计算模型。在普通的多项式时间模型模型中，同一个算法必须处理所有输入长度，而在非均匀多项式时间模型中，计算过程可以针对不同输入长度 $n$ 使用不同的辅助信息

这种模型主要以否定的方式出现在密码学中。也就是说，如果能够证明即使敌手拥有这种更强的非均匀多项式时间模型的计算能力，也仍然无法完成某种攻击任务，那么该安全性结论就更强

【随机化算法】

随机化算法（Randomized Algorithms）在密码学中具有核心作用。因此，在密码学中讨论“高效计算”时，不能只考虑确定性多项式时间模型，还需要考虑概率多项式时间（Probabilistic Polynomial Time）模型

引入：随机化算法实例

【基本思想】

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

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

【概述】

密码学（Cryptography）一直与设计和分析加密方案的问题相关，即通过不安全通信媒介提供秘密通信的方案。自 20 世纪 70 年代以来，诸如构建不可伪造的数字签名、设计容错协议等问题也被视为密码学范畴。事实上，密码学可被视为一门研究如何设计任何需要抵御恶意滥用企图的系统的学科

单向函数（One-way Function）是在密码学中具重要意义的函数，其是一个单射函数，对于每一个输入 $x$，可以在多项式时间内计算出函数值 $f(x)$，但是给定一个函数值 $y$，要找到一个输入 $x$ 使得 $f(x)=y$ 在计算上是困难的

【概述】

随着机器学习、深度学习的发展，语音、图像、自然语言处理逐渐取得了很大的突破，语音、图像、文本都是简单的序列或网格数据，深度学习很擅长处理该类的结构化数据

但现实世界中并非所有事物都是结构化数据，即并非都可以表示为一个序列或者一个网络，例如社交网络、知识图谱、复杂的文件系统等

【概述】

对于 DDPM 来说，一个最大的缺点是需要设置较长的扩散步数才能得到好的效果，这导致了生成样本的速度较慢，比如扩散步数为 $1000$ 的话，那么生成一个样本就要模型推理 $1000$ 次

为此 Jiaming Song 等学者在《Denoising Diffusion Implicit Models》 中针对 DDPM 进行了改进，提出了去噪扩散隐式模型（Denoising Diffusion Implicit Models，DDIM），不再限制前向和反向过程必须是马尔卡夫链，在不牺牲质量的情况下，允许更少的采样步数来加速反向生成过程