大n布尔函数代数性质高效估计概率算法研究

120 浏览量更新于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 deﬁnitions and notations related to Boolean functions are given. Let GF (2) denote the binary

Galois ﬁeld and GF (2)

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 ||.

Deﬁnition 1. A Boolean function is a mapping f : GF (2)

−→ GF (2) . The set of all Boolean functions f (x

, . . . , x

) is denoted

by B

Deﬁnition 2. The algebraic normal form ( ANF ) of an n -variable Boolean function is the multivariate polynomial expression

f (x

, . . . , x

) =



c∈ GF (2)





i =1



, (1)

where c = (c

, . . . , c

) ∈ GF (2)

, τ

, x

∈ 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 τ

 = 0. If τ

 = 0 for all c = (c

, . . . , c

) ∈ GF (2)

, the

Boolean function f ∈ B

is called the all term function. If deg ( f ) ≤ 1, a Boolean function f ∈ B

is called an aﬃne function.

Especially, for an aﬃne Boolean function, if its constant term is zero, then the function is linear.

Deﬁnition 3. Let f ∈ B

be a nonlinear Boolean function, and X = (x

, . . . , x

) ∈ GF (2)

, X



= (x

, . . . , x

) ∈ GF (2)

, X



n −i

i +1

, . . . , x

) ∈ GF (2)

n −i

, where { j

, . . . , j

} ⊂ { 1 , . . . , n } , { j

i +1

, . . . , j

} ⊂ { 1 , . . . , n } and { j

, . . . , j

} ∩ { j

i +1

, . . . , j

} = ∅ . If by

ﬁxing X



= a, the function f (a, X



n −i

) = f



= a



n −i

) is an (n − i ) -variable linear subfunction or a constant function, then



= a



n −i

) is called a partial linear relation with respect to a ∈ GF (2)

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 Deﬁnition 3 .

Theorem 1. Let X



= (x

, . . . , x

) ∈ GF (2)

, X



n −i

= (x

i +1

, . . . , x

) ∈ GF (2)

n −i

, and D

⊆ { 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

, there exist B

⊆GF (2)

and B



= B

× GF (2)

n −i

such that



n −1

i =1



= GF (2)

and B



∩ B



= ∅ , (1 ≤ i ≤ n − 1 , 1 ≤ i

< i

≤ n − 1) so that f can be decomposed and represented as below:

f (X ) = f (X



, X



n −i

) =

n −1



i =1



(i )

=(σ

(i )

, ... σ

(i )

) ∈ B





s = j

 σ

(i )

 1)



· f (σ

(i )

, X



n −i

) , (2)

where for any σ

( i )

∈ B

we have f (σ

(i )

, X



n −i

) ∈ D

Proof. For any nonlinear Boolean function f ∈ B

, for a given X



= (x

, . . . x

) = σ

(i )

∈ GF (2)

, the restriction f (σ

(i )

, X



n −i

) =



= σ

(i )



n −i

) is either a partial linear relation or a nonlinear function. Let B

= { X



= σ

(i )

| f (σ

(i )

, X



n −i

) ∈ D

, σ

(i )

∈ GF (2)

}

be a collection of those σ

( i )

∈ GF (2)

for which f (σ

(i )

, X



n −i

) is a linear (aﬃne) function in X



n −i

variables, where B

may be

empty. Moreover, if some ﬁxed X



∈ GF (2)

\ B

, let X



i +1

= (X



, x

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

⊆GF (2)

and B



= B

× GF (2)

n −i

such that



n −1

i =1



= GF (2)

and B



∩ B



= ∅ , 1 ≤

< i

≤ n − 1 , where 1 ≤ i ≤ n − 1 and for any σ

( i )

∈ B

we have f (σ

(i )

, X



n −i

) ∈ D

. 

The

following corollary is an easy consequence of the above result.

Corollary 1. Using the notation of Theorem 1 the sets B

, (i = 1 , . . . , n − 1) satisﬁes the relations below.



n −1

i =1

|| B

|| × 2

n −i

= 2

, || B

|| ≤ 2

2. || B

|| ≤ || B

|| for non-empty sets B

and B

employed in decomposition (2) , ( i < j ) .

3. If f (x

, . . . , x

) is an aﬃne function, then || B

|| = 2 and || B

|| = 0 , (i = 2 , . . . , n − 1) .

4. If f (x

, . . . , x

) = x

· x

. . . x

, then || B

n −1

|| = 2 and || B

|| = 1 , (i = 1 , . . . , n − 2) .

5. If f (x

, . . . , x

) is a full term function, then || B

n −1

|| = 2

n −1

and || B

|| = 0 , (i = 1 , . . . , n − 2) .

剩余13页未读，继续阅读

weixin_38597970

粉丝: 4
资源: 919

大n布尔函数代数性质高效估计概率算法研究

布尔函数的设计与分析

布尔代数和数字逻辑 计算机组成原理PPT教案.pptx

"代数和余代数在函数规划中的新方法

"通信与计算权衡的研究：布尔函数在不同计算模型中的表现

布尔函数与布尔码的关系解析

计算机硬件基本原理：布尔逻辑与逻辑代数

布尔函数与逻辑电路设计：解决逻辑电路优化问题

用布尔代数算法求解极小碰集算法

逻辑函数的代数化简法，应该具有怎么样思维能高效化简

matlab中bdSolve

最新资源

布尔代数和数字逻辑计算机组成原理PPT教案.pptx