Comparison of cube attacks over different vector spaces

Richard Winter, Ana Salagean, Raphael C.W. Phan

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

5 Citations (Scopus)

Abstract

We generalise the cube attack of Dinur and Shamir (and the similar AIDA attack of Vielhaber) to a more general higher order differentiation attack, by summing over an arbitrary subspace of the space of initialisation vectors. The Moebius transform can be used for efficiently examining all the subspaces of a big space, similar to the method used by Fouque and Vannet for the usual cube attack. Secondly we propose replacing the Generalised Linearity Test proposed by Dinur and Shamir with a test based on higher order differentiation/Moebius transform. We show that the proposed test provides all the information provided by the Generalised Linearity Test, at the same computational cost. In addition, for functions that do not pass the linearity test it also provides, at no extra cost, an estimate of the degree of the function. This is useful for guiding the heuristics for the cube/AIDA attacks. Finally we implement our ideas and test them on the stream cipher Trivium.

Original languageEnglish
Title of host publicationCryptography and Coding - 15th IMA International Conference, IMACC 2015, Proceedings
EditorsJens Groth
PublisherSpringer
Pages225-238
Number of pages14
ISBN (Print)9783319272382
DOIs
Publication statusPublished - 2015
Externally publishedYes
EventIMA International Conference on Cryptography and Coding 2015 - Oxford, United Kingdom
Duration: 15 Dec 201517 Dec 2015
Conference number: 15th
https://link.springer.com/book/10.1007/978-3-319-27239-9 (Proceedings)

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9496
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceIMA International Conference on Cryptography and Coding 2015
Abbreviated titleIMACC 2015
Country/TerritoryUnited Kingdom
CityOxford
Period15/12/1517/12/15
Internet address

Keywords

  • Cube/AIDA attack
  • Higher order differentiation
  • Linearity testing
  • Moebius transform
  • Trivium

Cite this