A note on fast algebraic attacks and higher order nonlinearities

Summary, in English

In this note, we deduce a bound between fast algebraic immunity and higher order nonlinearity (it is the first time that a bound between these two cryptographic criteria is given), and find that a Boolean function should have high r-order nonlinearity to resist fast algebraic attacks. As a corollary, we find that no matter how much effort we make, the Tu-Deng functions cannot be repaired in a standard way to behave well against fast algebraic attacks. Therefore, we should give up repairing this class of Boolean functions and try to find other classes of functions with good cryptographic properties or to prove that the Carlet-Feng function behaves well.

• Författare: Qichun Wang; Thomas Johansson
• Avdelning/ar: Institutionen för elektro- och informationsteknik; ELLIIT: the Linköping-Lund initiative on IT and mobile communication
• Publiceringsår: 2011
• Språk: Engelska
• Sidor: 404-414
• Publikation/Tidskrift/Serie: Lecture Notes in Computer Science
• Volym: 6584
• Länkar: http://dx.doi.org/10.1007/978-3-642-21518-6_28
• Dokumenttyp: Del av eller Kapitel i bok
• Förlag: Springer
• Ämne: Electrical Engineering, Electronic Engineering, Information Engineering
• Nyckelord: Boolean functions; Stream ciphers; Fast algebraic attacks; High order nonlinearities
• Conference name: INSCRYPT 2010
• Conference date: 2010-10-20 - 2010-10-24
• Conference place: Shanghai, China
• Status: Published
• Forskningsgrupp: Crypto and Security
• ISBN/ISSN/Övrigt: ISSN: 0302-9743; ISSN: 1611-3349; ISBN: 978-3-642-21517-9; ISBN: 978-3-642-21518-6