A STUDY OF BINARY DECISION DIAGRAM CHARACTERISTICS OF BENT BOOLEAN FUNCTIONS

Miloš Radmanović

DOI Number
doi.org/10.2298/FUEE2302285R
First page
285
Last page
298

Abstract


Bent Boolean functions exist only for an even number of variables, moreover, they are unbalanced. Therefore, they are used in coding theory and in many areas of computer science. General form of bent functions is still unknown. One way of representing Boolean functions is with a reduced ordered binary decision diagram (ROBDD). The strength of ROBDDs is that they can represent Boolean functions data with a high level of redundancy in a compact form, as long as the data is encoded in such a way that the redundancy is exposed. This paper investigates characteristics of bent functions with focus on their ROBDD parameters. Decision diagram experimental framework has been used for implementation of a program for calculation of the ROBDD parameters. The results presented in this paper are intended to be used to create methods for the construction of bent functions using a ROBDD as a data structure from which the bent functions can be discovered.


Keywords

Coding theory, Boolean functions, bent functions, binary decision diagram

Full Text:

PDF

References


O. Rothaus, "On Bent Functions", J. Comb. Theory Ser. A, vol. 20, pp. 300-305, 1976.

O. Logachev, A. Salnikov and V Yashchenko, Boolean Functions in Coding Theory and Cryptography, American Mathematical Society, 2012.

S. Mesnager, Bent Functions, Fundamentals and Results, Springer International Publishing, 2016.

N. Tokareva, Bent Functions, Results and Applications to Cryptography, Academic Press, 2015.

M. Stanković, C. Moraga and R. Stanković, "An improved spectral classification of Boolean functions based on an extended set of invariant operations", FU: Elect. Energ., vol. 31, no. 2, pp. 189-205, 2018.

P. Langevin and G. Leander, "Counting all bent functions in dimension eight 99270589265934370305785861242880", in Designs, Codes and Cryptography, vol. 59, pp. 193-201, 2011.

T. Sasao and M. Fujita, Representations of Discrete Functions, Kluwer Academic Publishers, Boston, 1996.

R. Drechsler and B. Becker, Binary Decision Diagrams: Theory and Implementation, Springer US, 2013.

N. Schafer, "The Characteristics of the Binary Decision Diagrams of Bent Functions", M.S. Thesis, Naval Postgraduate School, Monterey, CA, September 2009.

M. Radmanović, "Efficient Discovery of Bent Function Using Reed-Muller Subsets", In. Proceedings of the 55th Int. Scientific Conference on Information, Communication and Energy Systems and Technologies (ICEST 2020), pp. 7-10, 2020.

M. G. Karpovsky, R. S. Stanković and J. T. Astola, Spectral Logic and Its Applications for the Design of Digital Devices, Wiley, 2008.

M. Thornton, R. Drechsler and D. Miller, Spectral Techniques in VLSI CAD, Springer US, 2012.

S. Nagayama, A. Mishchenko, T. Sasao and J. T. Butler, "Minimization of average path length in BDDs by variable reordering", In Proceedings of the International Workshop on Logic and Synthesis, 2003, pp. 207-213.

K. Brace, R. Rudell and R. Bryant, "Efficient implementation of a BDD package", In Proceedings of the 27th ACM/IEEE Design Automation Conference, 1990, pp. 40-45.

F. Somenzi, "Efficient manipulation of decision diagrams", Software Tools for Technology Transfer, vol. 3, no. 2, pp. 171-181, 2001.


Refbacks

  • There are currently no refbacks.


ISSN: 0353-3670 (Print)

ISSN: 2217-5997 (Online)

COBISS.SR-ID 12826626