On equivalence classes of Boolean functions
Författare
Summary, in English
In FSE 2010, Rønjom and Cid put forward a nonlinear equivalence for Boolean functions and demonstrated that many cryptographic properties are not invariant among functions within the same equivalence class by providing some special examples. Their paper presented the idea and many problems were left open.
In this paper, we investigate equivalence of Boolean functions more deeply using a new method and discuss the number of Boolean functions in each equivalence class. We investigate further the cryptographic properties including algebraic immunity, algebraic degree and nonlinearity of equivalence classes, and deduce tight bounds on them. We find that there are many equivalence classes of Boolean functions with optimum algebraic immunity, optimum algebraic degree and a good nonlinearity. Moreover, we discuss how to construct equivalence classes with desired properties and show that it is possible to construct practical Boolean functions such that their equivalence classes have guaranteed cryptographic properties.
In this paper, we investigate equivalence of Boolean functions more deeply using a new method and discuss the number of Boolean functions in each equivalence class. We investigate further the cryptographic properties including algebraic immunity, algebraic degree and nonlinearity of equivalence classes, and deduce tight bounds on them. We find that there are many equivalence classes of Boolean functions with optimum algebraic immunity, optimum algebraic degree and a good nonlinearity. Moreover, we discuss how to construct equivalence classes with desired properties and show that it is possible to construct practical Boolean functions such that their equivalence classes have guaranteed cryptographic properties.
Avdelning/ar
Publiceringsår
2011
Språk
Engelska
Sidor
311-324
Publikation/Tidskrift/Serie
Lecture Notes in Computer Science
Volym
6829
Dokumenttyp
Del av eller Kapitel i bok
Förlag
Springer
Ämne
- Electrical Engineering, Electronic Engineering, Information Engineering
Nyckelord
- Stream ciphers
- Boolean functions
- Equivalence
- Algebraic immunity
- Nonlinearity
Conference name
ICISC 2010
Conference date
2010-12-01 - 2010-12-03
Status
Published
Forskningsgrupp
- Crypto and Security
ISBN/ISSN/Övrigt
- ISSN: 0302-9743
- ISSN: 1611-3349
- ISBN: 978-3-642-24209-0
- ISBN: 978-3-642-24208-3