第 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
小结
? 专门介绍单向函数的理论(包括单向函数
的严格定义及其性质)
? 密码学中最常用的若干候选单向函数族。