Extensions of the cube attack based on low degree annihilators

Aileen Zhang*, Chu Wee Lim, Khoongming Khoo, Lei Wei, Josef Pieprzyk

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

2 Citations (Scopus)

Abstract

At Crypto 2008, Shamir introduced a new algebraic attack called the cube attack, which allows us to solve black-box polynomials if we are able to tweak the inputs by varying an initialization vector. In a stream cipher setting where the filter function is known, we can extend it to the cube attack with annihilators: By applying the cube attack to Boolean functions for which we can find low-degree multiples (equivalently annihilators), the attack complexity can be improved. When the size of the filter function is smaller than the LFSR, we can improve the attack complexity further by considering a sliding window version of the cube attack with annihilators. Finally, we extend the cube attack to vectorial Boolean functions by finding implicit relations with low-degree polynomials.

Original languageEnglish
Title of host publicationCryptology and Network Security - 8th International Conference, CANS 2009, Proceedings
EditorsJuan A. Garay, Atsuko Miyaji, Akira Otsuka
Place of PublicationBerlin, Germany
PublisherSpringer, Springer Nature
Pages87-102
Number of pages16
Volume5888 LNCS
ISBN (Print)3642104320, 9783642104329
DOIs
Publication statusPublished - 2009
Event8th International Conference on Cryptology and Network Security, CANS 2009 - Kanazawa, Japan
Duration: 12 Dec 200914 Dec 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5888 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Other

Other8th International Conference on Cryptology and Network Security, CANS 2009
CountryJapan
CityKanazawa
Period12/12/0914/12/09

Fingerprint Dive into the research topics of 'Extensions of the cube attack based on low degree annihilators'. Together they form a unique fingerprint.

Cite this