Automated Dynamic Cube Attack on Block Ciphers: Cryptanalysis of SIMON and KATAN, by Zahra Ahmadian and Sahram Rasoolzadeh and Mahmoud Salmasizadeh and Mohammad Reza Aref
A few work has ever been performed in cryptanalysis of block ciphers using cube attacks. This paper presents a new framework for an efficient key recovery attack on block ciphers based on cube technique. In this method, a cube tester is positioned at the middle of the cipher which is extended in two directions over the maximum possible upper and lower rounds, given that some subkey bits are guessed. It is shown that an automated algorithm for this dynamic cube attack on block ciphers can be realized. Furthermore, we show its effectiveness on two lightweight block ciphers KATAN and SIMON. Our results shows that this method can break 117 and 152 out of 254 rounds of KATAN-32 in non-full-codebook and full-codebook attack scenarios, respectively. In the case of SIMON32/64, we succeed to cryptanalyse 16 and 18 out of 32 rounds, by the same scenarios. Both results show that although this method does not outperform all the existing attacks on these two ciphers, it can absolutely compete with the well-established and mature methods of cryptanalysis of block ciphers, such as linear, differential and meet in
the middle attack families.
Aggregate Pseudorandom Functions and Connections to Learning, by Aloni Cohen and Shafi Goldwasser and Vinod Vaikuntanathan
In the first part of this work, we introduce a new type of pseudo-random function for which ``aggregate queries\'\' over exponential-sized sets can be efficiently answered. An example of an aggregate query may be the product of all function values
belonging to an exponential-sized interval, or the sum of all function values on points for which a polynomial time predicate holds. We show how to use algebraic properties of underlying
classical pseudo random functions, to construct aggregatable pseudo random functions for a number of classes of aggregation queries under cryptographic hardness assumptions. On the flip side, we show that certain aggregate queries are impossible to support.
In the second part of this work, we show how various extensions of pseudo-random functions considered recently in the cryptographic literature, yield impossibility results for various extensions of machine learning models, continuing a line of investigation originated by Valiant and Kearns in the 1980s and 1990s. The extended pseudo-random functions we address include constrained pseudo random functions, aggregatable pseudo random functions, and pseudo random functions secure under related-key attacks.