Séminaire C2 du vendredi 16 novembre 2018

La prochaine édition du séminaire C2 se tiendra le vendredi 16 novembre 2018 dans la salle 105 couloir 25-26 du LIP6 de Sorbonne Université

  • 10h00 : Alice Pellet-Mary, LIP ENS-Lyon : Quantum attack against some candidate obfuscators based on GGH13
Résumé : Since the first candidate indistinguishability obfuscator (iO) has been proposed in 2013 by Garg, Gentry, Halevi, Raykova, Sahai and Waters, a lot of other candidates have been proposed. All these constructions are only candidate constructions, in the sense that they come with no security proof. Alongside with all these constructions, some attacks have also been proposed, breaking many of the candidates.
In this talk, I will present a quantum attack against some iO that were not broken yet. This attack relies on recovering a short generator of a principal ideal in a cyclotomic field, which can be done in quantum polynomial time thanks to the works of Biasse and Song (SODA 2016) and Cramer, Ducas, Peikert and Regev (Eurocrypt 2016). Once this short generator is recovered, the rest of the attack is a mixed-input attack, which does not require any quantum computer.
  • 11h15 : Baptiste Lambin, IRISA : On Recovering Affine Encodings in White-Box Implementations
Résumé : Ever since the first candidate white-box implementations by Chow et al. in 2002, producing a secure white-box implementation of AES has remained an  enduring challenge. Following the footsteps of the original proposal by Chow et  al., other constructions were later built around the same framework. In this  framework, the round function of the cipher is “encoded” by composing it with non-linear and affine layers known as encodings. However, all such attempts were broken by a  series of increasingly efficient attacks that are able to peel off these  encodings, eventually uncovering the underlying round function, and with it the secret key. These attacks, however, were generally ad-hoc and did not enjoy a wide  applicability. As our main contribution, we propose a generic and efficient algorithm  to recover affine encodings, for any Substitution-Permutation-Network (SPN) cipher, such  as AES, and any form of affine encoding. For AES parameters, namely 128-bit  blocks split into 16 parallel 8-bit S-boxes, affine encodings are recovered with a  time complexity estimated at 2^32 basic operations, independently of how the encodings are built. This algorithm is directly applicable to a large class of schemes. We  illustrate this on a recent proposal due to Baek, Cheon and Hong, which was not previously  analyzed. While Baek et al. evaluate the security of their scheme to 110 bits, a  direct application of our generic algorithm is able to break the scheme with an estimated time complexity of only 2^35 basic operations. As a second contribution, we show a different approach to cryptanalyzing the Baek et al. scheme, which reduces the analysis to a standalone combinatorial problem, ultimately achieving key recovery in time complexity 2^31 . We also provide an implementation of the attack, which is able to recover the secret key in about 12 seconds on a standard desktop computer.
  • 13h45 : Jean-Marc Robert, Université de Toulon : Enhanced Digital Signature using Splitted Digit Exponent Representation
Résumé : Digital Signature Algorithm (DSA) involves modular exponentiation, of a public and known base by a random one-time exponent. In order to speed-up this operation, well-known methods take advantage of the memorization of base powers. However, due to the cost of the memory, to its small size and to the latency of access, previous research sought for minimization of the storage. In this paper, taking into account the modern processor features and the growing size of the cache memory, we improve the storage/efficiency trade-off, by using a RNS Digit exponent representation. We then propose algorithms for modular exponentiation. The storage is lower for equivalent complexities for modular exponentiation computation. The implementation performances show significant memory saving, up to 3 times for the largest NIST standardized key sizes compared to state of the art approaches. This work has been presented at WAIFI 2016 conference. We extend this approach to the Elliptic Curve Scalar Multiplication with another multiplicative digit approach we call R-splitting, providing side-channel resistance.
  • 15h00: Anand Kumar Narayanan, LIP6 , Sorbonne université : Nearly linear time encodable codes beating the Gilbert-Varshamov bound.
Résumé : Error-correcting codes enable reliable transmission of information over an erroneous channel. One typically desires codes to transmit information at a high rate while still being able to correct a large fraction of errors. However, rate and relative distance (which quantifies the fraction of errors corrected) are competing quantities with a trade off. The Gilbert-Varshamov bound assures for every rate R, relative distance D and alphabet size Q, there exists an infinite family of codes with R + H_Q(D) > = 1-\epsilon.  Constructing codes meeting or beating theGilbert-Varshamov bound remained a long-standing open problem, until the advent of algebraic geometry codes by Goppa. In a seminal paper, for prime power squares Q ≥ 7^2, Tsfasman-Vladut-Zink constructed algebraic geometry codes beating the Gilbert-Varshamov bound. A rare occasion where an explicit construction yields better parameters than guaranteed by randomized arguments! For codes to find use in practice, one often requires fast encoding and decoding algorithms in addition to satisfying a good trade off between rate and minimum distance. A natural question, which remains unresolved, is if there exist linear time encodable and decodable codes meeting or beating the Gilbert-Varshamov bound. In this talk, I shall present the first nearly linear time encodable codes beating the Gilbert-Varshamov bound, along with a nearly quadratic decoding algorithm. Time permitting, applications to secret sharing, explicit construction of pseudorandom objects, Probabilistically Checkable Interactive Proofs and the like will also be discussed.
The talk will be based on joint work with Matthew Weidner
(Caltech/Cambridge). A preprint is available here