Page 215 - 《软件学报》2021年第9期

尚方舟 等:概率积分及其在 PUFFIN 算法中的应用 2839

deg(f)≤s−1,
s
则对此位置上出现的所有 2 个元素求和为 0,此时认为该比特是平衡的.
1.2 概率积分区分器的构造
在传统的积分分析中,一般只考虑 deg(f)≤s−1 的比特位置,将 deg(f)=s 的比特位置视为无用信息.而概率积
分的思想是考虑多项式代数次数达到最大时,常数 c 0 ,c 1 ,…,c n−s−1 对首项系数的影响.
令 p(c i =1)=p i ,0≤i≤n−s−1,由此可计算得到首项系数为 0 的概率,即平衡概率.若平衡概率与 50%存在偏差,
那么就认为此情况能够与随机情况区分,就说构造了一个概率积分区分器.
例 1:若某一比特位置的多项式函数可写作:
y=f(x 0 ,x 1 ,c 0 ,c 1 )=c 0 c 1 x 0 x 1 +c 0 x 0 +c 1 x 1 +c 0 c 1 ,
则当且仅当 c 0 =c 1 =1 时,该比特位置 deg(f)=2.根据引理 1,该比特位置不平衡.因此,不平衡概率为 p 0 p 1 ,平衡概率
为 1−p 0 p 1 .
由此,我们引入概率布尔多项式的概念.
ˆ
定义 1. 设 f 为 n 变元布尔函数,其对应的概率布尔多项式 f 可表示为
(, ,..., x = ∑
ˆ f xx 2 n ) ˆ a x
I
,
1
I
∈
IP ()N
其中, ˆ a = I ( p a = I 1),0≤ ˆ a ≤ I 1.
在概率积分区分器中,常数 c 0 ,c 1 ,…,c n−s−1 的概率 p 0 ,p 1 ,…,p n−s−1 可以通过选择明文进行控制.本文为体现概
率积分区分器存在的普适性,考虑最一般的情况,即令所有涉及到的常数随机生成,故其取 0 或 1 的概率相同,均
为 0.5.在例 1 中,令 p 0 =p 1 =0.5,则其概率布尔多项式表示为
ˆ y = ˆ f ( , )x x = 0 1 0.25x x + 0 1 0.5x + 0 0.5x + 1 0.25.
并由此得到概率布尔多项式首项系数与平衡概率之间的关系:
推论 1. 设 n 元概率布尔多项式 (, ,..., x = ∑ ˆ a x I ,0≤ a ≤ I 1,则:
ˆ
fx x
)
1
2
n
I
∈
()
IP N
⎛ ⎞
p⎜ ∑ f ˆ () x = 0⎟ = 1 a ˆ ,
−
⎜ ⎟ I
⎝ x∈ 2 n ,sup ( )p x ⊆F I ⎠
其中,supp(x)={1≤i≤n|x i =1}.
推论 1 表明:由某一比特位置的概率布尔多项式,可以求得该比特位置的平衡概率.
下面在布尔多项式系数彼此独立的条件下,给出概率布尔多项式的运算法则.
性质 1(加法法则). 设 n 元概率布尔多项式:
ˆ f xx 2 n ) ˆ a x g x x 2 n ) ∑ b x I ,
ˆ , ( , ,..., x = ∑
ˆ
I
( , ,..., x =
I
I
1
1
∈
∈
()
( )
IP N I P N
则:
ˆ
ˆ
( , ,..., x +
I
ˆ( , ,..., x =
f xx ) g x x ) ˆ (a + b − ∑ ˆ ˆ 2a b x
) .
1 2 n 1 2 n I I I I
∈
IP ()N
证明:由概率布尔多项式的定义可知:f(x 1 ,x 2 ,…,x n )中,单项 x 系数为 1 的概率为 ˆ a ,系数为 0 的概率为1 a− ˆ .
I
I I
ˆ
同理,多项式 g(x 1 ,x 2 ,…,x n )中,单项 x 系数为 1 的概率为 b ,系数为 0 的概率为1 b− ˆ .因此,若要多项式 f(x 1 ,x 2 ,…,
I
I I
x n )+g(x 1 ,x 2 ,…,x n )中单项 x I 系数为 1,则多项式 f,g 中有且仅有一个包含 x I ,x I 系数为 1 的概率为
ˆ
a ˆ (1 b− I ˆ I ) (1 a+ − ˆ )b = I ˆ I ˆ a + I b − ˆ I ˆ 2a b
.
I I
故而:
ˆ
ˆ
ˆ( , ,..., x =
( , ,..., x +
I
f xx 2 n ) g x x 2 n ) ˆ (a + I b − ∑ ˆ I ˆ 2a b x □
) .
1
I I
1
IP ()N
∈
下面通过一个例子,直观说明概率布尔多项式的乘法法则.