【基本思想】

预言机（Oracle）与预言机机器（Oracle Machine）是两个相关但不同的概念。简单来说，预言机是一个外部函数或外部接口，它能够对机器提出的查询给出回答；而预言机机器是一种被增强过的计算模型，它在普通图灵机的基础上增加了向预言机提出查询的能力

在计算复杂性理论中，预言机机器（Oracle Machine）最初主要用于刻画不同计算问题之间的归约关系（Reducibility）。也就是说，可以通过给一台机器访问某个外部函数的能力，来研究“如果能够调用某个问题的解答过程，那么是否可以解决另一个问题”

【难解任务】

在计算复杂性理论下，密码学通常把那些不能由概率多项式时间模型完成的任务视为难解任务（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$ 在计算上是困难的

【概述】

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

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