Enumerative encoding of correlation-immune Boolean functions

作     者：Carrasco, Nicolas Le Bars, Jean-Marie Viola, Alfredo 

作者机构：Univ Republica Montevideo Uruguay Univ Caen Basse Normandie UMR GREYC 6072 F-14032 Caen France ENSICAEN UMR GREYC 6072 F-14050 Caen France CNRS UMR GREYC 6072 F-14032 Caen France 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2013年第487卷

页      面：23-36页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Universidad de la Republica, Uruguay [CSIC 2008-2010] ECOS project [U08E02] French Agence Nationale de la Recherche [NT09_432755] 

主　　题：Enumerative encoding Uniform random generation Decomposable structures Boolean functions Correlation-immune functions 1-resilient functions 

摘      要：Le Bars and Viola have recently proposed an innovative recursive decomposition of the first-order correlation-immune Boolean functions. Based on their work this paper presents the design of an enumerative encoding of these Boolean functions. This is the first enumerative encoding of a class of Boolean functions defined by a cryptographic property. In this paper we study three major milestones to do this encoding: the conceptual computational tree, the use of normal classes and signed permutations, and a dynamic selection of the decomposition. Our enumerative encoding algorithm is practicable up to 8 variables which is the best result we may expect due to the combinatorial explosion of the numbers of classes. (C) 2013 Elsevier B.V. All rights reserved.