In this paper,a new method to analyze boolean functions is *** this method,one can analyze the balancedness,the nonlinearity,and the input-output correlation of vectorial boolean *** basic idea of this method is to co...
详细信息
In this paper,a new method to analyze boolean functions is *** this method,one can analyze the balancedness,the nonlinearity,and the input-output correlation of vectorial boolean *** basic idea of this method is to compute the refined covers of some parametric boolean polynomial systems which are equivalent to these *** a refined cover,the parameter space is divided into several disjoint components,and on each component,the parametric boolean polynomial system has a fixed number of *** efficient algorithm based on the characteristic set method to compute refined covers of parametric boolean polynomial systems is *** experimental results about some instances generated from cryptanalysis show that this new method is efficient and can solve some instances which can not be solved in reasonable time by other methods.
boolean functions in Answer Set Programming have proven a useful modelling tool. They are usually specified by means of aggregates or external atoms. A crucial step in computing answer sets for logic programs containi...
详细信息
ISBN:
(纸本)9781577357605
boolean functions in Answer Set Programming have proven a useful modelling tool. They are usually specified by means of aggregates or external atoms. A crucial step in computing answer sets for logic programs containing boolean functions is verifying whether partial interpretations satisfy a boolean function for all possible values of its undefined atoms. In this paper, we develop a new methodology for showing when such checks can be done in deterministic polynomial time. This provides a unifying view on all currently known polynomial time decidability results, and furthermore identifies promising new classes that go well beyond the state of the art. Our main technique consists of using an ordering on the atoms to significantly reduce the necessary number of model checks. For many standard aggregates, we show how this ordering can be automatically obtained.
This paper presents a construction for a class of 1-resilient functions with optimal algebraic immunity on an even number of variables. The construction is based on the concatenation of two balanced functions in assoc...
详细信息
This paper presents a construction for a class of 1-resilient functions with optimal algebraic immunity on an even number of variables. The construction is based on the concatenation of two balanced functions in associative classes. For some n, a part of 1-resilient functions with maximum algebraic immunity constructed in the paper can achieve almost optimal nonlinearity. Apart from their high nonlinearity, the functions reach Siegenthaler＇s upper bound of algebraic degree. Also a class of l-resilient functions on any number n 〉 2 of variables with at least sub-optimal algebraic immunity is provided.
If f(x1,…,xn) is a boolean function on the variables x1,…,xn then f(*1,…,*n) where *i ∈ {0, 1, xi}, i = l,…,n, is called subfunction of f. The number of subfunctions of f is at most 3n. Intuition suggests that a ...
详细信息
Generalizations of the bent property of a boolean function are presented, by proposing spectral analysis with respect to a well-chosen set of local unitary transforms. Quadratic boolean functions are related to simple...
详细信息
Generalizations of the bent property of a boolean function are presented, by proposing spectral analysis with respect to a well-chosen set of local unitary transforms. Quadratic boolean functions are related to simple graphs and it is shown that the orbit generated by successive local complementations on a graph can be found within the transform spectra under investigation. The flat spectra of a quadratic boolean function are related to modified versions of its associated adjacency matrix.
Very recently, Carlet, Meaux and Rotella have studied the main cryptographic features of boolean functions when, for a given number n of variables, the input to these functions is restricted to some subset E of F2n. T...
详细信息
Very recently, Carlet, Meaux and Rotella have studied the main cryptographic features of boolean functions when, for a given number n of variables, the input to these functions is restricted to some subset E of F2n. Their study includes the particular case when E equals the set of vectors of fixed Hamming weight, which is important in the robustness of the boolean function involved in the FLIP stream cipher. In this paper we focus on the nonlinearity of boolean functions with restricted input and present new results related to the analysis of this nonlinearity improving the upper bound given by Carlet et al.
Determine the number of the rational zeros of any given linearized polynomial is one of the vital problems in finite field theory, with applications in modern symmetric cryptosystems. But, the known general theory for...
详细信息
Determine the number of the rational zeros of any given linearized polynomial is one of the vital problems in finite field theory, with applications in modern symmetric cryptosystems. But, the known general theory for this task is much far from giving the exact number when applied to a specific linearized polynomial. The first contribution of this paper is a better general method to get a more precise upper bound on the number of rational zeros of any given linearized polynomial over arbitrary finite field. We anticipate this method would be applied as a useful tool in many research branches of finite field and cryptography. Really we apply this result to get tighter estimations of the lower bounds on the second-order nonlinearities of general cubic boolean functions, which has been an active research problem during the past decade. Furthermore, this paper shows that by studying the distribution of radicals of derivatives of a given boolean function one can get a better lower bound of the second-order nonlinearity, through an example of the monomial boolean functions g mu=Tr(mu x22r+2r+1) defined over the finite field F(2)n.
Fixed polarity Reed-Muller(RM) expression(FPRM) has several practical applications due to its multitude of properties. In order to generate an FPRM with minimum power, based on a genetic algorithm, we propose a Power ...
详细信息
Fixed polarity Reed-Muller(RM) expression(FPRM) has several practical applications due to its multitude of properties. In order to generate an FPRM with minimum power, based on a genetic algorithm, we propose a Power optimization approach(POA-FPRMs) of Fixed Polarity RM expressions for incompletely specified boolean functions. Simulation results on MCNC benchmark circuits show that POAFPRMs can effectively reduce power, compared with the traditional polarity optimization approach, where the don't care terms are neglected.
In this correspondence, it is shown that the boolean functions constructed by Pasalic (Cryptogr Commun 4(1):25-45, 2012) do not always have the high degree product of order n - 1 as expected.
In this correspondence, it is shown that the boolean functions constructed by Pasalic (Cryptogr Commun 4(1):25-45, 2012) do not always have the high degree product of order n - 1 as expected.
Recently, Deshpande et al. introduced a new measure of the complexity of a boolean function. We call this measure the "goal value" of the function. The goal value of f is defined in terms of a monotone, subm...
详细信息
Recently, Deshpande et al. introduced a new measure of the complexity of a boolean function. We call this measure the "goal value" of the function. The goal value of f is defined in terms of a monotone, submodular utility function associated with f. As shown by Deshpande et al., proving that a boolean function f has small goal value can lead to a good approximation algorithm for the Stochastic boolean Function Evaluation problem for f. Also, if f has small goal value, it indicates a close relationship between two other measures of the complexity off, its average-case decision tree complexity and its average case certificate complexity. In this paper, we explore the goal value measure in detail. We present bounds on the goal values of arbitrary and specific boolean functions, and present results on properties of the measure. We compare the goal value measure to other, previously studied, measures of the complexity of boolean functions. Finally, we discuss a number of open questions suggested by our work. (C) 2017 Elsevier B.V. All rights reserved.
暂无评论