【基本思想】
预言机（Oracle）与预言机机器（Oracle Machine）是两个相关但不同的概念。简单来说，预言机是一个外部函数或外部接口，它能够对机器提出的查询给出回答；而预言机机器是一种被增强过的计算模型，它在普通图灵机的基础上增加了向预言机提出查询的能力
在计算复杂性理论中，预言机机器（Oracle Machine）最初主要用于刻画不同计算问题之间的归约关系（Reducibility）。也就是说，可以通过给一台机器访问某个外部函数的能力，来研究“如果能够调用某个问题的解答过程，那么是否可以解决另一个问题”
但在密码学中，预言机机器通常用于另一种目的：刻画敌手与密码系统之间的交互。敌手在攻击密码系统时，往往不只是被动观察，还可能主动向系统提交查询，并根据系统返回的结果继续攻击。例如，敌手可能向加密算法提交明文并获得密文，也可能向解密算法提交密文并观察解密结果。此时，加密算法或解密算法就可以被抽象为预言机，而敌手则被建模为一台能够访问这些预言机的机器
因此，在密码学语境下，预言机模型的核心作用是形式化描述：敌手可以在攻击过程中向密码系统发起查询，并获得系统的相应回答
【预言机与查询】
形式化地，预言机通常被表示为一个函数：
预言机 $f$ 接收一个二进制字符串作为输入，并返回一个二进制字符串作为输出。如果预言机机器向预言机提出一个查询 $q$，那么它得到的回答就是：
其中，$q$ 称为查询（Query），$f(q)$ 称为预言机回复（Oracle Reply）
需要注意的是，预言机对查询的回答是一致的（Consistent）。也就是说，对于同一个查询 $q$，预言机总是返回同一个结果 $f(q)$，而不会在不同时间给出不同回答
【预言机机器】
结构
预言机机器是在普通图灵机的基础上增加预言机访问能力得到的计算模型：
确定性 Oracle 预言机（Deterministic Oracle Machine）：在普通确定性图灵机的基础上增加了一个额外的磁带，称为预言机磁带（Oracle Tape），并增加了预言机调用状态（Oracle Invocation）、预言机出现状态（Oracle Appeared）这两个特殊状态
概率性 Oracle 预言机（Probabilistic Oracle Machine）：在普通概率图灵机的基础上进行相同扩展，也就是同样增加预言机磁带和两个特殊状态。它与确定性预言机机器的区别在于，机器本身的计算过程可以使用随机性
计算过程
设预言机机器为 $M$，输入为 $x$，并且 $M$ 可以访问预言机：
那么，机器 $M$ 的计算过程可通过配置之间的逐步转移来定义
对于状态不是预言机调用状态的配置，机器按照普通图灵机的方式进行下一步计算
特殊情况发生在机器进入预言机调用状态时。设机器当前的配置为 $\gamma$，并且此时预言机磁带上的内容为 $q$，那么下一步配置与 $\gamma$ 基本相同，唯一的区别是：
- 当前状态从调用状态变为出现状态
- 预言机磁带上的内容从 $q$ 变为 $f(q)$。
也就是说，机器在预言机磁带上写入查询 $q$，进入预言机调用状态；随后，预言机会在一步之内把磁带内容替换为 $f(q)$，并使机器进入预言机返回状态
这个过程可以概括为：
其中，$q$ 是机器提出的查询，$f(q)$ 是预言机返回的回复
输出表示
当预言机机器 $M$ 在输入 $x$ 上运行，并且可以访问预言机 $f$ 时，它的输出通常记为：
其中，上标 $f$ 表示机器 $M$ 在计算过程中可以调用预言机 $f$
如果 $M$ 是确定性预言机机器，那么在给定输入 $x$ 和预言机 $f$ 后，$M^f(x)$ 是一个确定的输出
如果 $M$ 是概率性预言机机器，那么由于机器内部可以使用随机性，$M^f(x)$ 通常表示一个输出分布，而不是单一固定结果
运行时间
需要特别注意的是，预言机机器的运行时间只计算机器自身执行的计算步数
在预言机机器模型中，预言机对每一次查询的回复都被视为在一步（Single Step）内完成。也就是说，不管函数 $f(q)$ 本身是否容易计算，只要机器提出查询 $q$，它就可以在一步之内得到回复 $f(q)$
因此，预言机机器模型关注的不是预言机内部如何计算答案，而是机器如何使用预言机的回答继续进行计算
这也是预言机模型的一个重要抽象：它把某些计算过程看作外部可调用的理想接口，从而便于研究机器在拥有这种接口时的计算能力或攻击能力
【在密码学中的作用】
在密码学中，预言机机器最常见的作用是建模敌手对密码系统的查询能力
例如，在某些加密安全性定义中，敌手可能可以访问一个加密预言机（Encryption Oracle）。敌手提交明文 $m$，预言机返回对应密文：
在某些更强的攻击模型中，敌手还可能访问一个解密预言机（Decryption Oracle）。敌手提交密文 $c$，预言机返回对应明文：
此时，敌手本身可以被看作一个预言机机器，它在攻击过程中不断选择查询，根据预言机的回答调整后续行为，并最终输出攻击结果
因此，预言机机器非常适合描述“交互式攻击过程”，它不是单纯描述一个算法如何独立运行，而是描述一个敌手如何在攻击过程中与密码系统交互
