大n布尔函数代数性质高效估计概率算法研究
108 浏览量
更新于2024-08-28
收藏 539KB PDF 举报
本研究论文探讨了"估计大n布尔函数的代数性质的有效概率算法"，发表在2017年的《信息科学》(Information Sciences)第402期，91-104页。该文章关注的是密码学领域中的一个重要课题，尤其是在流密码（streamciphers）的安全性评估上。流密码的性能往往受到其抵抗快速代数攻击的能力的影响，这些攻击通常利用布尔函数的代数特性来破解加密系统。
研究者们提出了一个高效的概率算法，旨在准确估计大数量变量（n）的布尔函数的代数性质，如代数免疫性（algebraic immunity），这是一个衡量布尔函数抵抗代数攻击的重要指标。高代数免疫性的函数更难以被解析，因此对于设计安全的密码体制至关重要。
算法的主要目标是通过减少计算复杂度，提升估计这些关键属性的效率。作者们可能采用了统计方法或者优化的计算策略，以便在处理大规模布尔函数时能够节省时间和资源。论文中可能会涉及多项式时间复杂度分析，以确保算法的实用性，并与其他现有方法进行比较，以展示其优越性。
此外，文中还可能包含了算法的具体实现步骤、实验结果以及对算法在实际应用中可能的改进空间的讨论。作者们从2016年7月接收修订稿到同年3月接受并在线发布，展示了严谨的科研过程和对学术界的贡献。
这篇论文不仅提供了理论分析，还可能包含了一些关键的数学证明和技术细节，对于理解大n布尔函数的代数性质估计具有很高的参考价值，对于密码学研究人员、信息安全专家以及从事代数密码学的学者来说，是一篇不可多得的研究成果。
Y. Wei et al. / Information Sciences 402 (2017) 91–104 93
2. Preliminaries
In this section, some basic definitions and notations related to Boolean functions are given. Let GF (2) denote the binary
Galois field and GF (2)
n
an n -dimensional vector space spanned over GF (2). The operation “”will denote the addition over
GF (2). Throughout this article | ·| will denote the absolute value of an integer and the cardinality of a set B will be denoted
as || B ||.
Definition 1. A Boolean function is a mapping f : GF (2)
n
−→ GF (2) . The set of all Boolean functions f (x
1
, . . . , x
n
) is denoted
by B
n
.
Definition 2. The algebraic normal form ( ANF ) of an n -variable Boolean function is the multivariate polynomial expression
f (x
1
, . . . , x
n
) =
c∈ GF (2)
n
τ
c
n
i =1
x
c
i
i
, (1)
where c = (c
1
, . . . , c
n
) ∈ GF (2)
n
, τ
c
, x
i
∈ GF (2) , (i = 1 , . . . , n ) . Moreover, the algebraic degree of f , denoted by deg ( f ), is the
maximal value of the Hamming weight of c satisfying the condition τ
c
= 0. If τ
c
= 0 for all c = (c
1
, . . . , c
n
) ∈ GF (2)
n
, the
Boolean function f ∈ B
n
is called the all term function. If deg ( f ) ≤ 1, a Boolean function f ∈ B
n
is called an affine function.
Especially, for an affine Boolean function, if its constant term is zero, then the function is linear.
Definition 3. Let f ∈ B
n
be a nonlinear Boolean function, and X = (x
1
, . . . , x
n
) ∈ GF (2)
n
, X
i
= (x
j
1
, . . . , x
j
i
) ∈ GF (2)
i
, X
n −i
=
(x
j
i +1
, . . . , x
j
n
) ∈ GF (2)
n −i
, where { j
1
, . . . , j
i
} ⊂ { 1 , . . . , n } , { j
i +1
, . . . , j
n
} ⊂ { 1 , . . . , n } and { j
1
, . . . , j
i
} ∩ { j
i +1
, . . . , j
n
} = ∅ . If by
fixing X
i
= a, the function f (a, X
n −i
) = f
X
i
= a
(X
n −i
) is an (n − i ) -variable linear subfunction or a constant function, then
f
X
i
= a
(X
n −i
) is called a partial linear relation with respect to a ∈ GF (2)
i
.
3. A probabilistic decomposition algorithm for nonlinear Boolean functions
In this section, a probabilistic decomposition algorithm for nonlinear Boolean functions which decomposes any Boolean
functions into a set of partial linear relations is discussed. This decomposition is generic, deterministic and valid for arbitrary
Boolean functions (fully specifying a given function) but it is not unique. The consequence is that different choices of such
a decomposition may yield different estimates of algebraic properties, though since the number of these decompositions
is not large the algorithm may exhaustively check for the best decomposition. For brevity, in the result below we use the
notation introduced in Definition 3 .
Theorem 1. Let X
i
= (x
1
, . . . , x
i
) ∈ GF (2)
i
, X
n −i
= (x
i +1
, . . . , x
n
) ∈ GF (2)
n −i
, and D
i
⊆ { L (X
n −i
) | L (X
n −i
) = c · X
n −i
b, c ∈
GF (2)
n −i
, b ∈ GF (2) } . Then given any nonlinear Boolean function f ∈ B
n
, there exist B
i
⊆GF (2)
i
and B
i
= B
i
× GF (2)
n −i
such that
n −1
i =1
B
i
= GF (2)
n
and B
i
1
∩ B
i
2
= ∅ , (1 ≤ i ≤ n − 1 , 1 ≤ i
1
< i
2
≤ n − 1) so that f can be decomposed and represented as below:
f (X ) = f (X
i
, X
n −i
) =
n −1
i =1
σ
(i )
=(σ
(i )
j
1
, ... σ
(i )
j
i
) ∈ B
i
j
i
s = j
1
(x
s
σ
(i )
s
1)
· f (σ
(i )
, X
n −i
) , (2)
where for any σ
( i )
∈ B
i
we have f (σ
(i )
, X
n −i
) ∈ D
i
.
Proof. For any nonlinear Boolean function f ∈ B
n
, for a given X
i
= (x
j
1
, . . . x
j
i
) = σ
(i )
∈ GF (2)
i
, the restriction f (σ
(i )
, X
n −i
) =
f
X
i
= σ
(i )
(X
n −i
) is either a partial linear relation or a nonlinear function. Let B
i
= { X
i
= σ
(i )
| f (σ
(i )
, X
n −i
) ∈ D
i
, σ
(i )
∈ GF (2)
i
}
be a collection of those σ
( i )
∈ GF (2)
i
for which f (σ
(i )
, X
n −i
) is a linear (affine) function in X
n −i
variables, where B
i
may be
empty. Moreover, if some fixed X
i
∈ GF (2)
i
\ B
i
, let X
i +1
= (X
i
, x
j
i +1
) , then either X
i +1
∈ B
i +1
or not. If X
i +1
∈ GF (2)
i +1
\ B
i +1
,
then we can increase the size of X
i +1
to X
i +2
. Iteratively, we reach the case i = n − 1 for which X
n −1
∈ B
n −1
always holds.
Consequently, we can obtain a collection B
i
⊆GF (2)
i
and B
i
= B
i
× GF (2)
n −i
such that
n −1
i =1
B
i
= GF (2)
n
and B
i
1
∩ B
i
2
= ∅ , 1 ≤
i
1
< i
2
≤ n − 1 , where 1 ≤ i ≤ n − 1 and for any σ
( i )
∈ B
i
we have f (σ
(i )
, X
n −i
) ∈ D
i
.
The
following corollary is an easy consequence of the above result.
Corollary 1. Using the notation of Theorem 1 the sets B
i
, (i = 1 , . . . , n − 1) satisfies the relations below.
1.
n −1
i =1
|| B
i
|| × 2
n −i
= 2
n
, || B
i
|| ≤ 2
i
.
2. || B
i
|| ≤ || B
j
|| for non-empty sets B
i
and B
j
employed in decomposition (2) , ( i < j ) .
3. If f (x
1
, . . . , x
n
) is an affine function, then || B
1
|| = 2 and || B
i
|| = 0 , (i = 2 , . . . , n − 1) .
4. If f (x
1
, . . . , x
n
) = x
1
· x
2
. . . x
n
, then || B
n −1
|| = 2 and || B
i
|| = 1 , (i = 1 , . . . , n − 2) .
5. If f (x
1
, . . . , x
n
) is a full term function, then || B
n −1
|| = 2
n −1
and || B
i
|| = 0 , (i = 1 , . . . , n − 2) .
剩余13页未读，继续阅读
101 浏览量
146 浏览量
147 浏览量
112 浏览量
2021-03-18 上传
105 浏览量
点击了解资源详情
点击了解资源详情
123 浏览量
weixin_38597970
- 粉丝: 4
- 资源: 919
我的内容管理
展开
