Fast Algebraic Attacks and Decomposition of Symmetric Boolean Functions

DOI10.1109/TIT.2011.2145690MaRDI QIDQ5273575zbMATH OpenOpenAlexFDO

Authors Meicheng Liu, Dongdai Lin, Dingyi Pei

Publication date 12 July 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0910.4632

Mathematics Subject Classification ID

Cryptography (94A60) Boolean functions (06E30)

Abstract: Algebraic and fast algebraic attacks are power tools to analyze stream ciphers. A class of symmetric Boolean functions with maximum algebraic immunity were found vulnerable to fast algebraic attacks at EUROCRYPT'06. Recently, the notion of AAR (algebraic attack resistant) functions was introduced as a unified measure of protection against both classical algebraic and fast algebraic attacks. In this correspondence, we first give a decomposition of symmetric Boolean functions, then we show that almost all symmetric Boolean functions, including these functions with good algebraic immunity, behave badly against fast algebraic attacks, and we also prove that no symmetric Boolean functions are AAR functions. Besides, we improve the relations between algebraic degree and algebraic immunity of symmetric Boolean functions.

Cited in

(20)

• Constructions of even-variable RSBFs with optimal algebraic immunity and high nonlinearity
• Convex continuations of some discrete functions
• Further construction of even-variable balanced rotation symmetric Boolean functions with optimal algebraic immunity
• Constructing even-variable RSBFs with higher nonlinearity, optimal AI and almost optimal FAI
• Boolean functions with maximum algebraic immunity: further extensions of the Carlet-Feng construction
• On the immunity of rotation symmetric Boolean functions against fast algebraic attacks
• Balanced 2p-variable rotation symmetric Boolean functions with optimal algebraic immunity
• Hamming weights of symmetric Boolean functions
• A note on the optimal immunity of Boolean functions against fast algebraic attacks
• On the order of smoothness of the maximal convex continuation of a Boolean function
• Results on highly nonlinear Boolean functions with provably good immunity to fast algebraic attacks
• Fast algebraic immunity of Boolean functions
• Balanced even-variable rotation symmetric Boolean functions with optimal algebraic immunity, maximum algebraic degree and higher nonlinearity
• Concave continuations of Boolean functions and some of their properties and applications
• Enhanced Boolean functions suitable for the filter model of pseudo-random generator
• Open questions on nonlinearity and on APN functions
• Constructions of balanced odd-variable rotation symmetric Boolean functions with optimal algebraic immunity and high nonlinearity
• On the construction of even-variable rotation symmetric Boolean functions with optimal algebraic immunity and high nonlinearity
• Balanced \(2^k\)-variable rotation symmetric Boolean functions with optimal algebraic immunity
• Progress in Cryptology – Mycrypt 2005

This page was built for publication: Fast Algebraic Attacks and Decomposition of Symmetric Boolean Functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5273575)