【概述】

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

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

【线性码的基本定义】

长度为 $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）。也就是说，可以通过给一台机器访问某个外部函数的能力，来研究“如果能够调用某个问题的解答过程，那么是否可以解决另一个问题”

【难解任务】

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

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

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

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

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