【概述】

某些函数虽然在某个不可忽略比例的输入上难以反演，但在大部分输入上可能仍然容易反演，因此它只能满足弱单向性，而不能满足强单向性

但是，从存在性角度看，弱单向函数和强单向函数是等价的，即：

【概述】

在关于单向函数的定义中，负责反演函数的算法通常被限制为概率多项式时间算法。也就是说，安全性要求是：不存在任何高效随机算法能够以不可忽略概率从 $f(x)$ 中恢复出某个原像

在此基础上，考虑更强的安全性定义：不仅要求概率多项式时间算法不能反演函数，还要求即使是非均匀的多项式规模电路族也不能反演函数

【概述】

下面介绍密码学中常被视为单向函数的三类函数，但目前并不知道这些函数是否真正是单向函数，它们只能被看作基于大量研究经验提出的猜想，到目前为止，还没有找到能够以明显成功概率高效求逆这些函数的算法

也就是说，这些函数之所以被认为可能是单向函数，并不是因为已经被严格证明难以求逆，而是因为它们对应的求逆问题长期以来没有被有效解决

【线性码的基本定义】

长度为 $n$ 且维度为 $k$ 的线性码（Linear Code）是定义在 $n$ 维有限域 $\mathbb{F}_q^n$ 中维度为 $k$ 的线性子空间 $C$，其中 $\mathbb{F}_q$ 是具有 $q$ 个元素的有限域，通常称为 q 元码

如果 $q=2$ 或 $q=3$，则分别称为二进制线性码、三进制线性码，线性子空间 $C$ 中的向量称为码字（Codeword），线性码的大小是码字的数量，即 $q^k$

【长度规则函数】

定义

对于单向函数，有一个常用的约定：假设函数 $f$ 是长度规则的（Length Regular）

【在部分长度上定义的单向函数】

基本思想

单向函数默认定义在整个字符串集合上，即：

【强单向函数】

定义

若函数 $f:\{0,1\}^{*} \to \{0,1\}^{*}$ 满足：

【现代密码学中的计算差距】

现代密码学建立在一种基本差距之上：对于合法用户来说，某些算法应当是高效可用的；对于非法敌手来说，滥用或破解这些算法应当在计算上不可行

可以集中考虑一个典型密码学任务：安全数据通信（Secure Data Communication），即加密方案（Encryption Schemes）。

【严格化处理】

密码学需要一种严格化处理（Rigorous Treatment），即通过精确定义、形式化模型和严格证明来讨论安全性问题。严格化处理主要涉及三个方面：

1. 为什么密码学本身需要严格化处理
2. 严格化处理在实践中具有什么意义和后果
3. 为什么这种处理方式往往具有某种“保守性”

【基本思想】

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

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