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

Boolean functions (06E30) Cryptography (94A60)

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

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)