Extensions of the cube attack based on low degree annihilators

Aileen Zhang; Chu Wee Lim; Khoongming Khoo; Lei Wei; Josef Pieprzyk

doi:10.1007/978-3-642-10433-6_7

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

School of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

4 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 language	English
Title of host publication	Cryptology and Network Security - 8th International Conference, CANS 2009, Proceedings
Editors	Juan A. Garay, Atsuko Miyaji, Akira Otsuka
Place of Publication	Berlin, Germany
Publisher	Springer, Springer Nature
Pages	87-102
Number of pages	16
Volume	5888 LNCS
ISBN (Print)	3642104320, 9783642104329
DOIs	https://doi.org/10.1007/978-3-642-10433-6_7
Publication status	Published - 2009
Event	8th International Conference on Cryptology and Network Security, CANS 2009 - Kanazawa, Japan Duration: 12 Dec 2009 → 14 Dec 2009

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5888 LNCS
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Other

Other	8th International Conference on Cryptology and Network Security, CANS 2009
Country/Territory	Japan
City	Kanazawa
Period	12/12/09 → 14/12/09

Access to Document

10.1007/978-3-642-10433-6_7

Cite this

Zhang, A., Lim, C. W., Khoo, K., Wei, L., & Pieprzyk, J. (2009). Extensions of the cube attack based on low degree annihilators. In J. A. Garay, A. Miyaji, & A. Otsuka (Eds.), Cryptology and Network Security - 8th International Conference, CANS 2009, Proceedings (Vol. 5888 LNCS, pp. 87-102). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5888 LNCS). Springer, Springer Nature. https://doi.org/10.1007/978-3-642-10433-6_7

Zhang, Aileen ; Lim, Chu Wee ; Khoo, Khoongming et al. / Extensions of the cube attack based on low degree annihilators. Cryptology and Network Security - 8th International Conference, CANS 2009, Proceedings. editor / Juan A. Garay ; Atsuko Miyaji ; Akira Otsuka. Vol. 5888 LNCS Berlin, Germany : Springer, Springer Nature, 2009. pp. 87-102 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{089def01800a4562b2f483111f4db35e,

title = "Extensions of the cube attack based on low degree annihilators",

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.",

author = "Aileen Zhang and Lim, {Chu Wee} and Khoongming Khoo and Lei Wei and Josef Pieprzyk",

year = "2009",

doi = "10.1007/978-3-642-10433-6_7",

language = "English",

isbn = "3642104320",

volume = "5888 LNCS",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer, Springer Nature",

pages = "87--102",

editor = "Garay, {Juan A.} and Atsuko Miyaji and Akira Otsuka",

booktitle = "Cryptology and Network Security - 8th International Conference, CANS 2009, Proceedings",

address = "United States",

note = "8th International Conference on Cryptology and Network Security, CANS 2009 ; Conference date: 12-12-2009 Through 14-12-2009",

}

Zhang, A, Lim, CW, Khoo, K, Wei, L & Pieprzyk, J 2009, Extensions of the cube attack based on low degree annihilators. in JA Garay, A Miyaji & A Otsuka (eds), Cryptology and Network Security - 8th International Conference, CANS 2009, Proceedings. vol. 5888 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5888 LNCS, Springer, Springer Nature, Berlin, Germany, pp. 87-102, 8th International Conference on Cryptology and Network Security, CANS 2009, Kanazawa, Japan, 12/12/09. https://doi.org/10.1007/978-3-642-10433-6_7

Extensions of the cube attack based on low degree annihilators. / Zhang, Aileen; Lim, Chu Wee; Khoo, Khoongming et al.
Cryptology and Network Security - 8th International Conference, CANS 2009, Proceedings. ed. / Juan A. Garay; Atsuko Miyaji; Akira Otsuka. Vol. 5888 LNCS Berlin, Germany: Springer, Springer Nature, 2009. p. 87-102 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5888 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

TY - GEN

T1 - Extensions of the cube attack based on low degree annihilators

AU - Zhang, Aileen

AU - Lim, Chu Wee

AU - Khoo, Khoongming

AU - Wei, Lei

AU - Pieprzyk, Josef

PY - 2009

Y1 - 2009

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

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

UR - http://www.scopus.com/inward/record.url?scp=71549167320&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-10433-6_7

DO - 10.1007/978-3-642-10433-6_7

M3 - Conference proceeding contribution

AN - SCOPUS:71549167320

SN - 3642104320

SN - 9783642104329

VL - 5888 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 87

EP - 102

BT - Cryptology and Network Security - 8th International Conference, CANS 2009, Proceedings

A2 - Garay, Juan A.

A2 - Miyaji, Atsuko

A2 - Otsuka, Akira

PB - Springer, Springer Nature

CY - Berlin, Germany

T2 - 8th International Conference on Cryptology and Network Security, CANS 2009

Y2 - 12 December 2009 through 14 December 2009

ER -

Zhang A, Lim CW, Khoo K, Wei L, Pieprzyk J. Extensions of the cube attack based on low degree annihilators. In Garay JA, Miyaji A, Otsuka A, editors, Cryptology and Network Security - 8th International Conference, CANS 2009, Proceedings. Vol. 5888 LNCS. Berlin, Germany: Springer, Springer Nature. 2009. p. 87-102. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-10433-6_7

Extensions of the cube attack based on low degree annihilators

Abstract

Publication series

Other

Access to Document

Other files and links

Fingerprint

Cite this