Fonction booléenne | EPFL Graph Search

vignette|Arbre de décision binaire Une fonction booléenne est une fonction prenant en entrée une liste de bits et donnant en sortie un unique bit. Les fonctions booléennes sont très utilisées en informatique théorique, notamment en théorie de la complexité et en cryptologie (par exemple dans les boîtes-S et les chiffrements par flot -- fonction de filtrage ou de combinaison de registres à décalage à rétroaction linéaire). Définition, exemple et circuits Une fonction booléenne est une fonction de \mathbb{F}^n dans \mathbb{F} où \mathbb{F} désigne le corps fini à 2 éléments. Un exemple de fonction booléenne est la fonction parité, dont la sortie dépend de la parité du nombre de 1 dans l'entrée. Une fonction booléenne peut être représentée par un circuit booléen. Propriétés Forme algébrique normale Les corps finis et les polynômes interpolateurs de Lagrange conduisent rapidement à une propriété fondamentale des f

Analysis of lightweight stream ciphers

Simon Fischer

Stream ciphers are fast cryptographic primitives to provide confidentiality of electronically transmitted data. They can be very suitable in environments with restricted resources, such as mobile devices or embedded systems. Practical examples are cell phones, RFID transponders, smart cards or devices in sensor networks. Besides efficiency, security is the most important property of a stream cipher. In this thesis, we address cryptanalysis of modern lightweight stream ciphers. We derive and improve cryptanalytic methods for different building blocks and present dedicated attacks on specific proposals, including some eSTREAM candidates. As a result, we elaborate on the design criteria for the development of secure and efficient stream ciphers. The best-known building block is the linear feedback shift register (LFSR), which can be combined with a nonlinear Boolean output function. A powerful type of attacks against LFSR-based stream ciphers are the recent algebraic attacks, these exploit the specific structure by deriving low degree equations for recovering the secret key. We efficiently determine the immunity of existing and newly constructed Boolean functions against fast algebraic attacks. The concept of algebraic immunity is then generalized by investigating the augmented function of the stream cipher. As an application of this framework, we improve the cryptanalysis of a well-known stream cipher with irregularly clocked LFSR's. Algebraic attacks can be avoided by substituting the LFSR with a suitable nonlinear driving device, such as a feedback shift register with carry (FCSR) or the recently proposed class of T-functions. We investigate both replacement schemes in view of their security, and devise different practical attacks (including linear attacks) on a number of specific proposals based on T-functions. Another efficient method to amplify the nonlinear behavior is to use a round-based filter function, where each round consists of simple nonlinear operations. We use differential methods to break a reduced-round version of eSTREAM candidate Salsa20. Similar methods can be used to break a related compression function with a reduced number of rounds. Finally, we investigate the algebraic structure of the initialization function of stream ciphers and provide a framework for key recovery attacks. As an application, a key recovery attack on simplified versions of eSTREAM candidates Trivium and Grain-128 is given.

EPFL2008

Logic Resynthesis of Majority-Based Circuits by Top-Down Decomposition

Giovanni De Micheli, Siang-Yun Lee, Heinz Riener

Logic resynthesis is the problem of finding a dependency function to re-express a given Boolean function in terms of a given set of divisor functions. In this paper, we study logic resynthesis of majority-based circuits, which is motivated by the increasing interest in majority logic optimization due to the recent development of beyond-CMOS technologies. To meet the need for an efficient majority resynthesis heuristic, we propose a top-down decomposition algorithm, whose complexity is linear to both n and m, where n is the number of divisors and m is the number of majority operations in the dependency function. We evaluate the resynthesis algorithms by using them in a resubstitution run applied on the EPFL benchmark suite. The experimental results show that, comparing to the state-of-the-art enumeration algorithm whose complexity grows exponentially with m, using the proposed decomposition Algorithm 1eads to 1.5% more circuit size reduction by lifting the limitation on m, within comparable runtime.

IEEE2021

A Dichotomy for Real Weighted Holant Problems

Sangxia Huang

Holant is a framework of counting characterized by local constraints. It is closely related to other well-studied frameworks such as the counting constraint satisfaction problem (#CSP) and graph homomorphism. An effective dichotomy for such frameworks can immediately settle the complexity of all combinatorial problems expressible in that framework. Both #CSP and graph homomorphism can be viewed as subfamilies of Holant with the additional assumption that the equality constraints are always available. Other subfamilies of Holant such as Holant() and Holant (c) problems, in which we assume some specific sets of constraints to be freely available, were also studied. The Holant framework becomes more expressive and contains more interesting tractable cases with less or no freely available constraint functions, while, on the other hand, it also becomes more challenging to obtain a complete characterization of its time complexity. Recently, a complexity dichotomy for a variety of subfamilies of Holant such as #CSP, graph homomorphism, Holant(), and Holant (c) for Boolean domain was proved. In this paper, we prove a dichotomy for the general Holant framework where all the constraints are real symmetric functions on Boolean inputs. This setting already captures most of the interesting combinatorial counting problems defined by local constraints, such as (perfect) matching. This is the first time a dichotomy is obtained for general Holant problems without any auxiliary functions. One benefit of working with the Holant framework is some powerful new reduction technique such as the holographic reduction. Along the proof of our dichotomy, we introduce a new reduction technique, namely realizing a constraint function by approximating it. This new technique is employed in our proof in a situation where it seems that all previous reduction techniques fail; thus, this new idea of reduction might also be of independent interest. Besides proving a dichotomy and developing a new technique, we also obtained some interesting by-products. We prove a dichotomy for #CSP, restricting to instances where each variable appears a multiple of d times for any d. We also prove that counting the number of Eulerian orientations on 2k-regular graphs is #P-hard for any .