Paper 2009/049
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.
Note: This paper is a revision of a previous eprint submission "Extensions of the Cube Attack". It is currently in submission.
Metadata
- Available format(s)
-
PDF
- Publication info
- Published elsewhere. Unknown where it was published
- Keywords
- Cube AttackAlgebraic AttackLow-Degree Annihilators.
- Contact author(s)
- kkhoongm @ gmail com
- History
- 2009-06-19: last of 2 revisions
- 2009-01-29: received
- See all versions
- Short URL
- https://ia.cr/2009/049
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2009/049,
author = {Aileen Zhang and Chu-Wee Lim and Khoongming Khoo and Wei Lei and Josef Pieprzyk},
title = {Extensions of the Cube Attack based on Low Degree Annihilators},
howpublished = {Cryptology {ePrint} Archive, Paper 2009/049},
year = {2009},
url = {https://eprint.iacr.org/2009/049}
}
