**Extensions of the Cube Attack based on Low Degree Annihilators**

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

**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.

**Category / Keywords: **Cube Attack, Algebraic Attack, Low-Degree Annihilators.

**Date: **received 28 Jan 2009, last revised 19 Jun 2009

**Contact author: **kkhoongm at gmail com

**Available format(s): **PDF | BibTeX Citation

**Note: **This paper is a revision of a previous eprint submission "Extensions of the Cube Attack". It is currently in submission.

**Version: **20090619:064234 (All versions of this report)

**Short URL: **ia.cr/2009/049

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]