Low-Data Complexity Biclique Cryptanalysis of Block Ciphers With Application to Piccolo and HIGHT

In this paper, we present a framework for biclique cryptanalysis of block ciphers which extremely requires a low amount of data. To that end, we enjoy a new representation of biclique attack based on a new concept of cutset that describes our attack more clearly. Then, an algorithm for choosing two differential characteristics is presented to simultaneously minimize the data complexity and control the computational complexity. Then, we characterize those block ciphers that are vulnerable to this technique and among them, we apply this attack on lightweight block ciphers Piccolo-80, Piccolo-128, and HIGHT. The data complexity of these attacks is only 16-plaintext-ciphertext pairs, which is considerably less than the existing cryptanalytic results. In all the attacks, the computational complexity remains the same as the previous ones or even it is slightly improved.