Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

On equivalence classes of Boolean functions

Wang, Qichun and Johansson, Thomas LU orcid (2011) ICISC 2010 In Lecture Notes in Computer Science 6829. p.311-324
Abstract
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... (More)
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. (Less)
Please use this url to cite or link to this publication:
author
and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
Stream ciphers, Boolean functions, Equivalence, Algebraic immunity, Nonlinearity
host publication
Information Security and Cryptology - ICISC 2010 : 13th International Conference, Seoul, Korea, December 1-3, 2010, Revised Selected Papers - 13th International Conference, Seoul, Korea, December 1-3, 2010, Revised Selected Papers
series title
Lecture Notes in Computer Science
volume
6829
pages
311 - 324
publisher
Springer
conference name
ICISC 2010
conference dates
2010-12-01 - 2010-12-03
ISSN
0302-9743
1611-3349
ISBN
978-3-642-24208-3
978-3-642-24209-0
DOI
10.1007/978-3-642-24209-0_21
language
English
LU publication?
yes
id
836e6eaa-f351-489c-85cf-3877162572eb (old id 1789355)
date added to LUP
2016-04-04 12:51:36
date last changed
2023-09-23 02:53:15
@inbook{836e6eaa-f351-489c-85cf-3877162572eb,
  abstract     = {{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.<br/><br/>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.}},
  author       = {{Wang, Qichun and Johansson, Thomas}},
  booktitle    = {{Information Security and Cryptology - ICISC 2010 : 13th International Conference, Seoul, Korea, December 1-3, 2010, Revised Selected Papers}},
  isbn         = {{978-3-642-24208-3}},
  issn         = {{0302-9743}},
  keywords     = {{Stream ciphers; Boolean functions; Equivalence; Algebraic immunity; Nonlinearity}},
  language     = {{eng}},
  pages        = {{311--324}},
  publisher    = {{Springer}},
  series       = {{Lecture Notes in Computer Science}},
  title        = {{On equivalence classes of Boolean functions}},
  url          = {{http://dx.doi.org/10.1007/978-3-642-24209-0_21}},
  doi          = {{10.1007/978-3-642-24209-0_21}},
  volume       = {{6829}},
  year         = {{2011}},
}