检索结果-内蒙古大学图书馆

symmetric boolean functions depending on an odd number of variables with maximum algebraic immunity

IEEE TRANSACTIONS ON INFORMATION THEORY 2006年第5期52卷 2271-2273页

作者： Li, N Qi, WF Zhengzhou Informat Engn Univ Dept Math Appl Zhengzhou 450002 Peoples R China

To resist algebraic attacks, boolean functions should possess high algebraic immunity. In 2003, Courtois and Meier showed that the algebraic immunity of an n-variable boolean function is upper bounded by [(2)/(n)]. And then several papers studied how to find symmetric boolean functions with maximum algebraic immunity. In this correspondence, we prove that for each odd n, there is exactly one trivially balanced n-variable symmetric boolean function achieving the maximum algebraic immunity.

关键词： algebraic attacks algebraic immunity annihilators symmetric boolean functions trivially balanced

来源：评论

学校读者我要写书评

暂无评论

On the equal-weight symmetric boolean functions

引用

中国高等学校学术文摘·计算机科学 2009年第4期3卷 485-493页

作者： Yu ZHOU Guozhen XIAO National Key Lab of Integrated Service Networks Xidian UniversityXi'an 710071China

Two important classes of symmetric boolean functions are the equal-weight boolean functions and the elementary (or homogeneous) symmetric boolean *** this paper we studied the equal-weight symmetric boolean *** the Walsh spectra of the equalweight symmetric boolean functions are *** the sufficient and necessary condition on correlation-immunity of the equal-weight symmetric boolean function is derived and other cryptology properties such as the nonlinearity,balance and propagation criterion are taken into *** particular,the nonlinearity of the equal-weight symmetric boolean functions with n (n≥10) variables is determined by their Hamming *** these properties will be helpful in further investigations of symmetric boolean functions.

关键词： boolean functions symmetric boolean functions Krawtchouk polynomial nonlinearity correlation immunity propagation criterion

来源：评论

学校读者我要写书评

暂无评论

Modular periodicity of exponential sums of symmetric boolean functions

引用

DISCRETE APPLIED MATHEMATICS 2017年第Part3期217卷 455-473页

作者： Castro, Francis N. Medina, Luis A. Univ Puerto Rico Dept Math San Juan PR 00931 USA

This work brings techniques from the theory of recurrent integer sequences to the problem of balancedness of symmetric boolean functions. In particular, the periodicity modulo p (p odd prime) of exponential sums of symmetric boolean functions is considered. Periods modulo p, bounds for periods and relations between them are obtained for these exponential sums. The concept of avoiding primes is also introduced. This concept and the bounds presented in this work are used to show that some classes of symmetric boolean functions are not balanced. In particular, every elementary symmetric boolean function of degree not a power of 2 and less than 2048 is not balanced. For instance, the elementary symmetric boolean function inn variables of degree 1292 is not balanced because the prime p = 176129 does not divide its exponential sum for any positive integer n. It is showed that for some symmetric boolean functions, the set of primes avoided by the sequence of exponential sums contains a subset that has positive density within the set of primes. Finally, in the last section, a brief study for the set of primes that divide some term of the sequence of exponential sums is presented. (C) 2016 Elsevier B.V. All rights reserved.

关键词： symmetric boolean functions Exponential sums Recurrences Pisano periods

来源：评论

学校读者我要写书评

暂无评论

Characterization of robust immune symmetric boolean functions

引用

CRYPTOGRAPHY AND COMMUNICATIONS-DISCRETE-STRUCTURES boolean functions AND SEQUENCES 2015年第3期7卷 297-315页

作者： Li, Yuan Univ Chicago Chicago IL 60637 USA

Fix a field F. The algebraic immunity over F of boolean function f : {0, 1}(n) -> {0, 1} is defined as the minimal degree of a nontrivial (multilinear) polynomial g(x) is an element of F [x(1),..., x(n)] such that f (x) is a constant (either 0 or 1) for all x is an element of {0, 1}(n) satisfying g(x) = 0. Function f is called k robust immune if the algebraic immunity of f is always not less than k no matter how one changes the value of f (x) for k <= |x| = n - k. For any field F, any integers n, k >= 0, we characterize all k robust immune symmetric boolean functions in n variables. The proof is based on a known symmetrization technique and constructing a partition of nonnegative integers satisfying certain (in) equalities about p-adic distance, where p is the characteristic of the field F.

关键词： Algebraic immunity symmetric boolean functions Characterization

来源：评论

学校读者我要写书评

暂无评论

Size-energy tradeoffs for unate circuits computing symmetric boolean functions

引用

THEORETICAL COMPUTER SCIENCE 2011年第8-10期412卷 773-782页

作者： Uchizawa, Kei Takimoto, Eiji Nishizeki, Takao Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 9808579 Japan Kyushu Univ Grad Sch Informat Sci & Elect Engn Dept Informat Fukuoka 8190395 Japan Kwansei Gakuin Univ Sch Sci & Technol Sanda 6691337 Japan

A unate gate is a logical gate computing a unate boolean function, which is monotone in each variable. Examples of unate gates are AND gates, OR gates, NOT gates, threshold gates, etc. A unate circuit C is a combinatorial logic circuit consisting of unate gates. Let f be a symmetric boolean function of n variables, such as the Parity function, MOD function, and Majority function. Let m(0) and m(1) be the maximum numbers of consecutive 0's and consecutive 1's in the value vector of f, respectively, and let l = min{m(0), m(1)} and m = max{m(0), m(1)}. Let C be a unate circuit computing f. Let s be the size of the circuit C, that is, C consists of s unate gates. Let e be the energy of C, that is, e is the maximum number of gates outputting "1" over all inputs to C. In this paper, we show that there is a tradeoff between the size s and the energy e of C. More precisely, we show that (n + 1 - l)/m <= s(e). We also present lower bounds on the size s of C represented in terms of n, 1 and m. Our tradeoff immediately implies that log n <= e logs for every unate circuit C computing the Parity function of n variables. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Energy complexity Parity function Size-energy tradeoff symmetric boolean functions Threshold circuits Unate circuits

来源：评论

学校读者我要写书评

暂无评论

Upper bounds on the multiplicative complexity of symmetric boolean functions

引用

CRYPTOGRAPHY AND COMMUNICATIONS-DISCRETE-STRUCTURES boolean functions AND SEQUENCES 2019年第6期11卷 1339-1362页

作者： Brandao, Luis T. A. N. Calik, Cagdas Sonmez Turan, Meltem Peralta, Rene NIST Cryptog Technol Grp 100 Bur Dr Gaithersburg MD 20899 USA

A special metric of interest about boolean functions is multiplicative complexity (MC): the minimum number of AND gates sufficient to implement a function with a boolean circuit over the basis {XOR, AND, NOT}. In this paper we study the MC of symmetric boolean functions, whose output is invariant upon reordering of the input variables. Based on the Hamming weight method from Muller and Preparata (J. ACM 22(2), 195-201, 1975), we introduce new techniques that yield circuits with fewer AND gates than upper bounded by Boyar et al. (Theor. Comput. Sci. 235(1), 43-57, 2000) and by Boyar and Peralta (Theor. Comput. Sci. 396(1-3), 223-246, 2008). We generate circuits for all such functions with up to 25 variables. As a special focus, we report concrete upper bounds for the MC of elementary symmetric functions Sigma kn and counting functions Ekn with up to n =25 input variables. In particular, this allows us to answer two questions posed in 2008: both the elementary symmetric Sigma 48 and the counting E48 functions have MC 6. Furthermore, we show upper bounds for the maximum MC in the class of n-variable symmetric boolean functions, for each n up to 132.

关键词： symmetric boolean functions Multiplicative complexity Upper bounds Logic minimization 94A60 06E30

来源：评论

学校读者我要写书评

暂无评论

Generalized Walsh transforms of symmetric and rotation symmetric boolean functions are linear recurrent

引用

APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING 2018年第5期29卷 433-453页

作者： Castro, Francis N. Medina, Luis A. Stanica, Pantelimon Univ Puerto Rico Dept Math San Juan PR 00936 USA Naval Postgrad Sch Dept Appl Math Monterey CA 93943 USA

Exponential sums of symmetric boolean functions are linear recurrent with integer coefficients. This was first established by Cai, Green and Thierauf in the mid nineties. Consequences of this result has been used to study the asymptotic behavior of symmetric boolean functions. Recently, Cusick extended it to rotation symmetric boolean functions, which are functions with good cryptographic properties. In this article, we put all these results in the general context of Walsh transforms and some of its generalizations (nega-Hadamard transform, for example). Precisely, we show that Walsh transforms, for which exponential sums are just an instance, of symmetric and rotation symmetric boolean functions satisfy linear recurrences with integer coefficients. We also provide a closed formula for the Walsh transform and nega-Hadamard transform of any symmetric boolean functions. Moreover, using the techniques presented in this work, we show that some families of rotation symmetric boolean functions are not bent when the number of variables is sufficiently large and provide asymptotic evidence to a conjecture of Stnic and Maitra.

关键词： Walsh transform Nega-Hadamard transform symmetric boolean functions Rotation symmetric boolean functions Linear recurrences

来源：评论

学校读者我要写书评

暂无评论

Constructing symmetric boolean functions With Maximum Algebraic Immunity

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2009年第5期55卷 2406-2412页

作者： Qu, Longjiang Feng, Keqin Liu, Feng Wang, Lei Natl Univ Def Technol Dept Math & Syst Sci Coll Sci Changsha 410073 Hunan Peoples R China Southeast Univ Natl Mobile Commun Res Lab Nanjing 210096 Peoples R China Tsinghua Univ Dept Math Beijing 100084 Peoples R China Georgia Inst Technol Dept Math Atlanta GA 30332 USA

symmetric boolean functions with even variables 2k and maximum algebraic immunity AI(f) = k have been constructed in Bracken's thesis (2006). In this paper, we show more constructions of such boolean functions inc... 详细信息

关键词： Algebraic immunity symmetric boolean functions

来源：评论

学校读者我要写书评

暂无评论

Circuit complexity of symmetric boolean functions in antichain basis

引用

DISCRETE MATHEMATICS AND APPLICATIONS 2016年第1期26卷 31-39页

作者： Podolskaya, Olga V. Moscow MV Lomonosov State Univ Moscow 117234 Russia

We study the circuit complexity of boolean functions in an infinite basis consisting of all characteristic functions of antichains over the boolean cube. For an arbitrary symmetric function we obtain the exact value of its circuit complexity in this basis. In particular, we prove that the circuit complexities of the parity function and the majority function of n variables for all integers n 1 in this basis are [n+1/2] and [n/2] + 1 respectively. For the maximum circuit complexity of n-variable boolean functions in this basis, we show that its order of growth is equal ton.

关键词： boolean circuit complexity antichain functions boolean circuits symmetric boolean functions the Shannon function

来源：评论

学校读者我要写书评

暂无评论

On the complexity of monotone circuits for threshold symmetric boolean functions

引用

DISCRETE MATHEMATICS AND APPLICATIONS 2021年第5期31卷 345-366页

作者： Sergeev, Igor S. FSUE RDI Kvant Moscow Russia

The complexity of implementation of a threshold symmetric n-place boolean function with threshold k = O(1) via circuits over the basis {boolean OR, boolean AND} is shown not to exceed 2 log(2) k . n + o(n). Moreover, the complexity of a threshold-2 function is proved to be 2n + Theta(root n), and the complexity of a threshold-3 function is shown to be 3n + O(log n), the corresponding lower bounds are put forward.

关键词： monotone circuits complexity symmetric boolean functions threshold functions

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：