Cryptographic properties of the hidden weighted bit function
Loading...
Authors
Wang, Qichun
Carlet, Claude
Stănică, Pantelimon
Tan, Chik How
Subjects
hidden weight bit function
algebraic immunity
nonlinearity
BDD-based attack
algebraic immunity
nonlinearity
BDD-based attack
Advisors
Date of Issue
2013-12-23
Date
Publisher
Language
Abstract
The hidden weighted bit function (HWBF), introduced by R. Bryant in IEEE Trans. Comp. 40 and revisited by D. Knuth in Vol. 4 of The Art of Computer Programming, is a function that seems to be the simplest one with expoential Binary Decision Diagram (BDD) size. This property is interesting from a cryptographic viewpoint since BDD-based attacks are receiving more attention in the cryptographic community. But, to be usable in stream ciphers, the functions must also satisfy all the other main criteria. In this paper we investigate the cryptographic properties of HWBF and prove that it is balanced, with optimum algebraic degree and satisfies the strict avalanche criterion. We calculate its exact noninearity and give a lower bound on its algebraic immunity. Moreover, we investigate its normality and its resistance against fast algebraic attacks. The HWBF is simple, can be implemented efficiently, has a high BDD size and rather good cryptographic properties, if we take into account that its number of variables can be much larger than for other functions with the same implementation efficiency. Therefore, the HWBF is a good candidate for being used in real ctphers. Indeed, contrary to the case of symmetric functions, which allow such fast implementation but also offer to the attacker some specific possibilities due to their symmetry, its structure is not suspected to be related to such dedicated attacks.
Type
Article
Description
Series/Report No
Department
Applied Mathematics
Organization
Naval Postgraduate School (U.S.)
Identifiers
NPS Report Number
Sponsors
Funder
Format
Citation
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.