Section: Highlights of the Year

Highlights of the Year

Resistance of equivalent Sboxes to differential and linear attacks

The so-called Sboxes highly influence the security of a block cipher since they are the only nonlinear component in the cipher. It was widely believed that Sboxes which are affine equivalent (i.e., which are the same up to the composition with affine functions) provide the same security level regarding differential and linear cryptanalyses. However, some simulation results on the maximum expected differential probability over two rounds of the AES show that this is not always the case. A. Canteaut and J. Roué [45] have then investigated the effect of affine transformations of the Sbox on the maximal expected differential probability and linear potential over two rounds of a substitution-permutation network, when the diffusion layer is linear over the finite field defined by the Sbox alphabet. They have been able to exhibit different behaviors depending on the choice of the Sbox within a given equivalence class. This includes some unexpected differences: for a given $m$-bit Sbox, the choice of the basis used for defining the finite field in the description of the linear layer may also affect the value of the two-round MEDP or MELP. They have also shown that the inversion is the mapping within its equivalence class which has the highest two-round MEDP and MELP, independently of the choice of the MDS linear layer. This situation mainly originates from the fact that this Sbox is an involution. This result has been awarded as one of the 3 best papers at Eurocrypt 2015.

Relativistic cryptography

Two-party cryptographic tasks are well-known to be impossible without complexity assumptions, either in the classical or the quantum world. Remarkably, such no-go theorems might become invalid when adding the physical assumption that no information can travel faster than the speed of light. This additional assumption gives rise to the emerging field of relativistic cryptography. We started investigating such questions through the task of bit commitment. In particular, an interesting bit commitment protocol was introduced in 2014 by Lunghi et al. and proven secure against arbitrary classical attacks. The drawback however was that the commitment time was quite constrained, as most a few milliseconds. In [16] , K. Chakraborty, A. Chailloux and A. Leverrier showed that the same protocol could in fact achieve commitment times that were arbitrarily long, thereby establishing that relativistic cryptography is a very practical solution.

Quantum Expander Codes

In a paper presented at FOCS 2015 [55] , A. Leverrier and JP. Tillich, together with G. Zémor, give an efficient decoding algorithm for a certain kind of quantum LDPC codes which provably corrects any pattern of errors of weight proportional to the square-root of the length of the code. The algorithm runs in time linear in the number of qubits, which makes its performance the strongest to date for linear-time decoding of quantum codes. This work can be considered as a further step towards proving that fault tolerant quantum computing is possible by using only a constant multiplicative overhead of additional qubits.

Organization of WCC 2015

The whole project-team has been involved in the organization of the international conference WCC 2015, which was held in Paris (at Institut Henri Poincaré) in April 2015. This was the ninth in the series of biannual workshops on Coding and Cryptography. This edition has gathered around 150 participants from many different countries. We received 90 submissions out of which 53 have been selected for presentation at the conference.

Awards

• 1st prize of the Streebog competition  [90]

• 2nd prize of the underhanded crypto contest https://underhandedcrypto.com/archive/

• One of the best 3 papers at Eurocrypt 2015 [45]

• Best paper at PQCrypto 2016 [57] .

Best Papers Awards:

[45]