第 5章 单向函数
5.1 一般单向函数
? 5.1.1 单向函数的定义
? 定义 5.1 函数 称为正则的，若存在正多项式
p(n)使对任一,有 。正则函数的含意是
f(x)的长不比 x的长缩短太多。正则函数的一个重要的特殊
情形是保长函数，即对任一,有 。
? 定义 5.2 一个函数 称为强单向函数，若下列
两个条件成立,
（ 1）计算 f(x)是容易的，即 f(x)是多项式时间可计算的
（参看定义 4.10）；
（ 2）计算 f(x)的逆 是困难的，即对每一多项式时间
概率算法（参看定义 4.13）,每一正多项式 p(n)和一切充
分大的 有
? ? ? ?*1,01,0,* ?f
? ?*1,0?x xxfp ?))((
? ?*1,0?x xxf ?)(
? ? ? ?*1,01,0,* ?f
))((1 xff ?
'M
)( 0nnn ?
? ? )(1))(())((Pr 1' npUffUfM nn ?? ?
? （一）随机猜测算法
无论输入那个,, 总是输出 n次扔硬币结
果 r，作为对 x的猜测。将 代入（ 5.1）。因 与 r统计
独立，故得 （ 5.2）
其中 （ 5.3）
当 f(x)为 1－ 1映射时，（ 5.2）式中最后得不等式变为
等式。这是因为 中仅有 x一个原像。由（ 5.2）和
(5.3)可见,
1）若 f(x)为任一函数，则 的成功概率是一个正数
（大小可从 到 1），因此不能要求任一多项式时间概
率算法都不可计算函数 f(x)的逆；
2）若 f(x)为任一 1－ 1映射，则 的成功概率是可忽略
的，当然这并不表示 f(x)为单向函数，因为 只是一个
最简单的算法；
3）若 f(x)为一单向函数（不要求为 1－ 1映射），则由
于 为多项式时间概率算法，故（ 5.1）要求 的成功
概率是可忽略的。
)(xfy ? ? ?nx 1,0? 1M
1M nU
? ? ? ? ???? ??? x r nnnnn xrUffUfM 2),(22))(())((Pr 11 ?
??
? ?? ?
r
xffrxr
其它
若
0
))((1),( 1?
))((1 xff ?
1M
n?2
1M
1M
1M 1M
1M
? （二）固定输出算法
无论输入那个 y=f(x)，, 总是输出一个
固定的,将 代入（ 5.1）式得
（ 5.4）
其中 由（ 5.3）给出，（ 5.4）中第二个
等式是由于,
表示集 中的元素个数。当 是 的唯
一原像时，（ 5.4）中最后一个不等式变为
等式。由（ 5.4）可见,的成功概率与 有
类似的结论。
? ?nx 1,0? 2M
2M
? ?nx 1,0' ? 2M
? ? ? ?))((Pr))(())((Pr 1'12 nnn UffxUffUfM ?? ???
nn
x
n xffxx ???? ??? ? 22))((),(2 '1'?
),( ' xx?
))(())(( '11' xffxxffx ?? ??? ))(( '1 xff ?
))(( '1 xff ? 'x )( 'xf
2M 1M
? 定义 5.3 一个函数称为弱单向函数，若下列
两个条件成立,
（ 1）计算 f(x)是容易的，它与定义 5.2的 1）
相同；
（ 2）计算 f(x)的逆 是稍难的，即存在
一个正多项式 p(n)，使对每一多项式时间概
率算法 和一切充分大的 有
))((1 xff ?
'M )( 0nnn ?
? ? )(1))(())((Pr 1' npUffUfM nn ?? ?
5.1.2 候选单向函数
? 例 5.1 整数因子分解（参看例 4.1）
（ 5.6）
其中 分别表示整数 x,y和它们乘积的二进数
表示（参看（ 4.1）式
? 例 5.3 线性编码函数
设常数 满足
（ 5.8）
其中,C为 F上 距阵,m为 长消息,e为一
个 的错误。
yxyxyxf m u l t ???,),(
yxyx ?,,
0,,???k ))1((1 2 ????? Hk
),(),(),,( rGemGGemGf c o d e ???
? ? nkn ?2 ? ?kn
2/)( new ??
5.2 单向函数族
? 5.2.1单向函数族的定义
? 定义 5.4 一个函数族是由 {0,1} 的一个无穷子集 I（称为指
标集）和每个指标 对应一个函数 构成，
其 中为 {0,1} 的一个有穷子集。
? 定义 5.5 一个函数族 称为强单向函数族。
若存在三个多项式时间概率算法 A,D,F满足下列两个条件,
1） i和 x的抽取和 的计算是容易的，即若算法 A的输入
为 （ n个 1的比特串），则其输出为 {0,1} 上的一个随
机变量,若算法 D的输入为 {0,1}，则其输出为
上的一个随机变量,若算法 F的输入为 和,则
其输出为 ；
2）计算 的逆 是困难的，即对每一多项式时间概
率算法,每一正多项式 p(n)和一切充分大 n的有
（ 5.9）
其中 和 X 由条件 1）给出。
*
Ii? ? ?*1,0:)( ?ii Dxf
iD *
? ?? ?IiDf ii ?? ;1,0,*
)(xfi
n1 ?I n
nI ??Ii
n
iD
nX Ii? iDx?
)(xfi
)(xfi ))((1 xff ii?
'M
? ? )(1))(())(,(Pr 1' npXffXfIM nIInIn nnn ?? ?
nI n
? 定理 5.1 任一单向函数 可表示
为一个单向函数族，反之任一单向函数族
也可表示为一单向函数
,其中 E为 {0,1} 的一个无穷子集。
? ? ? ? *1,01,0,* ?f
? ?? ?IiDf ii ?? ;1,0,*
? ?*1,0,?Ef *
5.2.2 候选单向函数族
? 例 5.4 RSA函数族
? 例 5.5 Rabin函数族
? 例 5.6 Rabin－ Blum函数族
? 例 5.7 离散对数函数族
5,3 单向函数族的其它性质
? 5.3.1 单向陷门置换族
? 定义 5.6 设 为一单向置换族。由定义
5.5 及其后的说明知，存在多项式时间概率算法
和 D及多项式时间确定性算法 F满足定义 5.5中的
条件 1）和 2）（参看定义 5.5）。
? 单向置换族 称为单向陷门置换族，若
存在一个多项式时间概率算法 和一
个多项式时间确定性算法 满足如下条件，其中
。
? 3）,其中 和 分别
表示算法 A和 输入 时的输出，为 上的随机
变量，且对每对 和 每个有,
即陷门 作为求逆算法 的辅助输入。
? ?IiDDf iii ?? ;:
1A
? ?IiDDf iii ?? ;:
? ? ? ?*** 1,01,01,??A
1?F
? ??,2,1;11 * ?? nn
))(,())1((),1(()1( 11 nnnnn IIAAA ?? ?? )1(nA )1(1 nA
1A
n1
nI ? ?nI 1,0?
Iiii ?)),(,( ? iDx? xxfiF i ?? ))(),((1 ?
)(i? 1?F
5,3,2 单向无爪函数族
? 定义 5.7 设 为一成对单向函数族。
由定义 5.5及其后的说明知，对 都存在多项式时间概率算法
A,及多项式时间确定性算法 满足定义 5.5中的条件 1）和
2）。一个成对单向函数族称为单向无爪（ claw-free）函数族，
若存在多项式时间算法 满足下列条件,
1） 为 上的随机变量, 为 上的随机
变量 ( )，, ；
2）对每个,随机变量 和 有相同的分布；
3） 满足 称为对于指标 i的一个爪 (claw)，
记 为对于指标 i的一切爪构成的集，要求计算对于指标 i的爪
是困难的，即对每一多项式时间概率算法,每一正多项式
p(n)和一切充分大的 n有
（ 5.10）
? ?? ?IiRDfff iiiii ???,1,0,:);,( 10 ???
1,0??
?D ?F
),,( FDA
)1( nA ? ?nI 1,0? nI )(),( iDiD ?? ? ?iD
? ?1,0,?? ?Ii ???? ii DxxfxiFxiF ??? ),(),(),,( ? ?1,0,?? ?Ii
Ii? )),0((0 iDfi )),1((1 iDfi
),( 10 xx )()( 1100 xfxf ii ?
iC
'M
? ? )(1)(Pr ' npCIM nIn ??
5,4 单向函数的硬核
? 5,4,1 单向函数的硬核谓词
? 定义 5.8 一个布尔函数 称为一个
谓词 (predicate)。一个多项式时间可计算谓
词 b称为一个函数 的硬核谓词
（ hard-core predicate），若对每一多项式
时间概率算法,每个正多项式 p(n)和一切
充分大 n的有
（ 5.11）
? ? ? ?1,01,0,* ?b
? ? ? ?** 1,01,0,?f
'M
? ? )(121)())((Pr ' npUbUfM nn ???
? 定义 5.9 一个多项式时间可计算布尔函数族
称为函数族 的
硬核谓词族，若对每一多项式时间概率算法,
每一正多项式 p(n)和一切充分大的 n有
（ 5.12）
其中, A,D为函数族的随机抽样
算法
定理 5.2 设 f(x)为任一强单向函数。构造强单向函数
g为,其中 。定义
。则谓词 b为单向函数 g的硬核谓词。
? ?? ?IiDb ii ?? ;1,0,? ?? ?IiDf ii ?? ;1,0,*
'M
? ? )(121)())(,(Pr ' npXbXfIM nInIn nn ???
)(),( nnnn IDXlAI ??
)),((),( rxfrxg ? xr ? ??
j jj
rxrxb )2( m o d),(
5,4,2 单向函数的硬核函数
? 定义 5.10 设 是一个多项式时间可计
算函数，满足,对一切,记
。 h称为 f的硬核函数，若对每一多项式
时间概率算法,每一正多项式 p(n)和一切充分
大的 n有
(5.13)
其中 为在 上均匀分布的随机变量,为与
相互统计独立的在 上均匀分布的随机变量。
? 定理 5.3 设 f(x)为任一强单向函数，构造强单向函
数 为,其中, 。
定义,其中,
则函数 h为单向函数 的硬核函数。
?
? ? ? ?*1,01,0,* ?h
)()( yhxh ? xy ?
)()1()( nlhnl n ??
'M
? ? ? ? )(11)),((Pr1))(),((Pr )('' npRUfMUhUfM nlnnn ????
nU ? ?n1,0 )(nlR nU
? ? )(1,0 nl
1g )),((),(1 rxfrxg ? 1)( ??? xlxr ? ?nnl 2lo g)( ?
),(),(),(),( )(21 rxbrxbrxbrxh nl?? ? ???
??j kjjk nlkrxrxb ))(1(),( 1
1g
小结
? 专门介绍单向函数的理论（包括单向函数
的严格定义及其性质）
? 密码学中最常用的若干候选单向函数族。
5.1 一般单向函数
? 5.1.1 单向函数的定义
? 定义 5.1 函数 称为正则的，若存在正多项式
p(n)使对任一,有 。正则函数的含意是
f(x)的长不比 x的长缩短太多。正则函数的一个重要的特殊
情形是保长函数，即对任一,有 。
? 定义 5.2 一个函数 称为强单向函数，若下列
两个条件成立,
（ 1）计算 f(x)是容易的，即 f(x)是多项式时间可计算的
（参看定义 4.10）；
（ 2）计算 f(x)的逆 是困难的，即对每一多项式时间
概率算法（参看定义 4.13）,每一正多项式 p(n)和一切充
分大的 有
? ? ? ?*1,01,0,* ?f
? ?*1,0?x xxfp ?))((
? ?*1,0?x xxf ?)(
? ? ? ?*1,01,0,* ?f
))((1 xff ?
'M
)( 0nnn ?
? ? )(1))(())((Pr 1' npUffUfM nn ?? ?
? （一）随机猜测算法
无论输入那个,, 总是输出 n次扔硬币结
果 r，作为对 x的猜测。将 代入（ 5.1）。因 与 r统计
独立，故得 （ 5.2）
其中 （ 5.3）
当 f(x)为 1－ 1映射时，（ 5.2）式中最后得不等式变为
等式。这是因为 中仅有 x一个原像。由（ 5.2）和
(5.3)可见,
1）若 f(x)为任一函数，则 的成功概率是一个正数
（大小可从 到 1），因此不能要求任一多项式时间概
率算法都不可计算函数 f(x)的逆；
2）若 f(x)为任一 1－ 1映射，则 的成功概率是可忽略
的，当然这并不表示 f(x)为单向函数，因为 只是一个
最简单的算法；
3）若 f(x)为一单向函数（不要求为 1－ 1映射），则由
于 为多项式时间概率算法，故（ 5.1）要求 的成功
概率是可忽略的。
)(xfy ? ? ?nx 1,0? 1M
1M nU
? ? ? ? ???? ??? x r nnnnn xrUffUfM 2),(22))(())((Pr 11 ?
??
? ?? ?
r
xffrxr
其它
若
0
))((1),( 1?
))((1 xff ?
1M
n?2
1M
1M
1M 1M
1M
? （二）固定输出算法
无论输入那个 y=f(x)，, 总是输出一个
固定的,将 代入（ 5.1）式得
（ 5.4）
其中 由（ 5.3）给出，（ 5.4）中第二个
等式是由于,
表示集 中的元素个数。当 是 的唯
一原像时，（ 5.4）中最后一个不等式变为
等式。由（ 5.4）可见,的成功概率与 有
类似的结论。
? ?nx 1,0? 2M
2M
? ?nx 1,0' ? 2M
? ? ? ?))((Pr))(())((Pr 1'12 nnn UffxUffUfM ?? ???
nn
x
n xffxx ???? ??? ? 22))((),(2 '1'?
),( ' xx?
))(())(( '11' xffxxffx ?? ??? ))(( '1 xff ?
))(( '1 xff ? 'x )( 'xf
2M 1M
? 定义 5.3 一个函数称为弱单向函数，若下列
两个条件成立,
（ 1）计算 f(x)是容易的，它与定义 5.2的 1）
相同；
（ 2）计算 f(x)的逆 是稍难的，即存在
一个正多项式 p(n)，使对每一多项式时间概
率算法 和一切充分大的 有
))((1 xff ?
'M )( 0nnn ?
? ? )(1))(())((Pr 1' npUffUfM nn ?? ?
5.1.2 候选单向函数
? 例 5.1 整数因子分解（参看例 4.1）
（ 5.6）
其中 分别表示整数 x,y和它们乘积的二进数
表示（参看（ 4.1）式
? 例 5.3 线性编码函数
设常数 满足
（ 5.8）
其中,C为 F上 距阵,m为 长消息,e为一
个 的错误。
yxyxyxf m u l t ???,),(
yxyx ?,,
0,,???k ))1((1 2 ????? Hk
),(),(),,( rGemGGemGf c o d e ???
? ? nkn ?2 ? ?kn
2/)( new ??
5.2 单向函数族
? 5.2.1单向函数族的定义
? 定义 5.4 一个函数族是由 {0,1} 的一个无穷子集 I（称为指
标集）和每个指标 对应一个函数 构成，
其 中为 {0,1} 的一个有穷子集。
? 定义 5.5 一个函数族 称为强单向函数族。
若存在三个多项式时间概率算法 A,D,F满足下列两个条件,
1） i和 x的抽取和 的计算是容易的，即若算法 A的输入
为 （ n个 1的比特串），则其输出为 {0,1} 上的一个随
机变量,若算法 D的输入为 {0,1}，则其输出为
上的一个随机变量,若算法 F的输入为 和,则
其输出为 ；
2）计算 的逆 是困难的，即对每一多项式时间概
率算法,每一正多项式 p(n)和一切充分大 n的有
（ 5.9）
其中 和 X 由条件 1）给出。
*
Ii? ? ?*1,0:)( ?ii Dxf
iD *
? ?? ?IiDf ii ?? ;1,0,*
)(xfi
n1 ?I n
nI ??Ii
n
iD
nX Ii? iDx?
)(xfi
)(xfi ))((1 xff ii?
'M
? ? )(1))(())(,(Pr 1' npXffXfIM nIInIn nnn ?? ?
nI n
? 定理 5.1 任一单向函数 可表示
为一个单向函数族，反之任一单向函数族
也可表示为一单向函数
,其中 E为 {0,1} 的一个无穷子集。
? ? ? ? *1,01,0,* ?f
? ?? ?IiDf ii ?? ;1,0,*
? ?*1,0,?Ef *
5.2.2 候选单向函数族
? 例 5.4 RSA函数族
? 例 5.5 Rabin函数族
? 例 5.6 Rabin－ Blum函数族
? 例 5.7 离散对数函数族
5,3 单向函数族的其它性质
? 5.3.1 单向陷门置换族
? 定义 5.6 设 为一单向置换族。由定义
5.5 及其后的说明知，存在多项式时间概率算法
和 D及多项式时间确定性算法 F满足定义 5.5中的
条件 1）和 2）（参看定义 5.5）。
? 单向置换族 称为单向陷门置换族，若
存在一个多项式时间概率算法 和一
个多项式时间确定性算法 满足如下条件，其中
。
? 3）,其中 和 分别
表示算法 A和 输入 时的输出，为 上的随机
变量，且对每对 和 每个有,
即陷门 作为求逆算法 的辅助输入。
? ?IiDDf iii ?? ;:
1A
? ?IiDDf iii ?? ;:
? ? ? ?*** 1,01,01,??A
1?F
? ??,2,1;11 * ?? nn
))(,())1((),1(()1( 11 nnnnn IIAAA ?? ?? )1(nA )1(1 nA
1A
n1
nI ? ?nI 1,0?
Iiii ?)),(,( ? iDx? xxfiF i ?? ))(),((1 ?
)(i? 1?F
5,3,2 单向无爪函数族
? 定义 5.7 设 为一成对单向函数族。
由定义 5.5及其后的说明知，对 都存在多项式时间概率算法
A,及多项式时间确定性算法 满足定义 5.5中的条件 1）和
2）。一个成对单向函数族称为单向无爪（ claw-free）函数族，
若存在多项式时间算法 满足下列条件,
1） 为 上的随机变量, 为 上的随机
变量 ( )，, ；
2）对每个,随机变量 和 有相同的分布；
3） 满足 称为对于指标 i的一个爪 (claw)，
记 为对于指标 i的一切爪构成的集，要求计算对于指标 i的爪
是困难的，即对每一多项式时间概率算法,每一正多项式
p(n)和一切充分大的 n有
（ 5.10）
? ?? ?IiRDfff iiiii ???,1,0,:);,( 10 ???
1,0??
?D ?F
),,( FDA
)1( nA ? ?nI 1,0? nI )(),( iDiD ?? ? ?iD
? ?1,0,?? ?Ii ???? ii DxxfxiFxiF ??? ),(),(),,( ? ?1,0,?? ?Ii
Ii? )),0((0 iDfi )),1((1 iDfi
),( 10 xx )()( 1100 xfxf ii ?
iC
'M
? ? )(1)(Pr ' npCIM nIn ??
5,4 单向函数的硬核
? 5,4,1 单向函数的硬核谓词
? 定义 5.8 一个布尔函数 称为一个
谓词 (predicate)。一个多项式时间可计算谓
词 b称为一个函数 的硬核谓词
（ hard-core predicate），若对每一多项式
时间概率算法,每个正多项式 p(n)和一切
充分大 n的有
（ 5.11）
? ? ? ?1,01,0,* ?b
? ? ? ?** 1,01,0,?f
'M
? ? )(121)())((Pr ' npUbUfM nn ???
? 定义 5.9 一个多项式时间可计算布尔函数族
称为函数族 的
硬核谓词族，若对每一多项式时间概率算法,
每一正多项式 p(n)和一切充分大的 n有
（ 5.12）
其中, A,D为函数族的随机抽样
算法
定理 5.2 设 f(x)为任一强单向函数。构造强单向函数
g为,其中 。定义
。则谓词 b为单向函数 g的硬核谓词。
? ?? ?IiDb ii ?? ;1,0,? ?? ?IiDf ii ?? ;1,0,*
'M
? ? )(121)())(,(Pr ' npXbXfIM nInIn nn ???
)(),( nnnn IDXlAI ??
)),((),( rxfrxg ? xr ? ??
j jj
rxrxb )2( m o d),(
5,4,2 单向函数的硬核函数
? 定义 5.10 设 是一个多项式时间可计
算函数，满足,对一切,记
。 h称为 f的硬核函数，若对每一多项式
时间概率算法,每一正多项式 p(n)和一切充分
大的 n有
(5.13)
其中 为在 上均匀分布的随机变量,为与
相互统计独立的在 上均匀分布的随机变量。
? 定理 5.3 设 f(x)为任一强单向函数，构造强单向函
数 为,其中, 。
定义,其中,
则函数 h为单向函数 的硬核函数。
?
? ? ? ?*1,01,0,* ?h
)()( yhxh ? xy ?
)()1()( nlhnl n ??
'M
? ? ? ? )(11)),((Pr1))(),((Pr )('' npRUfMUhUfM nlnnn ????
nU ? ?n1,0 )(nlR nU
? ? )(1,0 nl
1g )),((),(1 rxfrxg ? 1)( ??? xlxr ? ?nnl 2lo g)( ?
),(),(),(),( )(21 rxbrxbrxbrxh nl?? ? ???
??j kjjk nlkrxrxb ))(1(),( 1
1g
小结
? 专门介绍单向函数的理论（包括单向函数
的严格定义及其性质）
? 密码学中最常用的若干候选单向函数族。
