Cryptology ePrint Archive: Report 2015/894

Comparison of cube attacks over different vector spaces

Richard Winter and Ana Salagean and Raphael C.-W. Phan

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.

Category / Keywords: foundations / Cube/AIDA attack, Trivium, Linearity testing, Moebius transform, higher order differentiation

Original Publication (in the same form): LNCS IMACC 2015 Conference Proceedings

Date: received 14 Sep 2015

Contact author: R Winter at lboro ac uk

Available format(s): PDF | BibTeX Citation

Version: 20150915:070137 (All versions of this report)

Short URL: ia.cr/2015/894

Discussion forum: Show discussion | Start new discussion