Computational Resolution of a Boolean Equation of 21 Variables

The Alienor method has been elaborated at the beginning of the 1980s by Yves Cherruault and Arthur Guillez (1983). The following people have also greatly contributed to the improvement of this new optimization method: Blaise Somé, Gaspar Mora, Balira Konfé, Jean Claude Mazza and Esther Claudine Bityé Mvondo. The basic idea consists in using a reducing transformation allowing us to simplify a multivariable optimization problem to a new optimization problem according to a single variable. The rational gestion of enterprises leads generally to the use of Operational Research, often called management science. The term Operational Research means a scientific approach to decision making, that seeks optimization in a system. Consequently, it is better to take the right decisions. Otherwise, fatal consequences can occur instantaneously [1]. Generally, we have to maximize the global profit margin, taking into account some constraints. For instance, in an integer programming problem, some or all the variables are required to be nonnegative integers. In this paper, we present new reducing transformations for global optimization in integer, binary and mixed variables as well as the applications in Boolean algebra by solving a Boolean Equation of 21 variables. The applications in Operational Research are presented on various examples, resolved by using the tabulator Excel of Microsoft.

A CHARACTERISTIC SET METHOD FOR SOLVING BOOLEAN EQUATIONS AND APPLICATIONS IN CRYPTANALYSIS OF STREAM CIPHERS

This paper presents a characteristic more efficient and has better properties than the set method for solving Boolean equations, which is general characteristic set method. In particular, the authors give a disjoint and monic zero decomposition algorithm for the zero set of a Boolean equation system and an explicit formula for the number of solutions of a Boolean equation system. The authors also prove that a characteristic set can be computed with a polynomial number of multiplications of Boolean polynomials in terms of the number of variables. As experiments, the proposed method is used to solve equations from cryptanalysis of a class of stream ciphers based on nonlinear filter generators. Extensive experiments show that the method is quite effective.

Quantum Algorithm for Boolean Equation Solving and Quantum Algebraic Attack on Cryptosystems

This paper presents a quantum algorithm to decide whether a Boolean equation system F has a solution and to compute one if F does have solutions with any given success probability.The runtime complexity of the algorithm is polynomial in the size of F and the condition number of certain Macaulay matrix associated with F.As a consequence,the authors give a polynomial-time quantum algorithm for solving Boolean equation systems if their condition numbers are polynomial in the size of F.The authors apply the proposed quantum algorithm to the cryptanalysis of several important cryptosystems:The stream cipher Trivum,the block cipher AES,the hash function SHA-3/Keccak,the multivariate public key cryptosystems,and show that they are secure under quantum algebraic attack only if the corresponding condition numbers are large.This leads to a new criterion for designing such cryptosystems which are safe against the attack of quantum computers:The corresponding condition number.

Boolean approaches to graph embeddings related to VLSI

This paper discusses the development of Boolean methods in some topics on graph em-beddings which are related to VLSI. They are mainly the general theory of graph embeddability, the orientabilities of a graph and the rectilinear layout of an electronic circuit.