【】

【归约论证的基本结构】

回顾弱单向函数的存在性定理中的证明结构：给定一个弱单向函数 $f$，首先构造一个多项式时间可计算函数 $g$，然后证明 $g$ 是强单向函数。

证明使用了归约论证（Reducibility Argument），其基本思想是：如果存在一个有效算法能够以不可忽略概率反演函数 $g$，从而否定 $g$ 的强单向性，那么就可以利用这个算法构造出一个有效算法来反演函数 $f$，从而否定 $f$ 的弱单向性。因此，只要 $f$ 的弱单向性成立，$g$ 就必须是强单向的。

【存在性定理】

弱单向函数与强单向函数的关系中函数 $g$ 的构造与证明说明，只要单向函数存在，就可以构造出一个弱单向但不是强单向的函数。因此，不能认为所有单向函数都是强单向函数

但是，也不能认为所有单向函数都只能是弱单向函数。事实上，弱单向函数的存在可以推出强单向函数的存在

【概述】

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

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

【概述】

在关于单向函数的定义中，负责反演函数的算法通常被限制为概率多项式时间算法。也就是说，安全性要求是：不存在任何高效随机算法能够以不可忽略概率从 $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\}^{*}$ 满足：