*15:17* [Pub][ePrint]
Another Nail in the Coffin of White-Box AES Implementations, by Tancrède Lepoint and Matthieu Rivain
The goal of white-box cryptography is to design implementations of common cryptographic algorithm (e.g. AES) that remain secure against an attacker with full control of the implementation and execution environment. This concept was put forward a decade ago by Chow et al. (SAC 2002) who proposed the first white-box implementation of AES. Since then, several works have been dedicated to the design of new implementations and/or the breaking of existing ones. In this paper, we describe a new attack against the original implementation of Chow et al. (SAC 2002), which efficiently recovers the AES secret key as well as the private external encodings in complexity $2^{22}$. Compared to the previous attack due to Billet et al. (SAC 2004) of complexity $2^{30}$, our attack is not only more efficient but also simpler to implement. Then, we show that the \\emph{last} candidate white-box AES implementation due to Karroumi (ICISC 2010) can be broken by a direct application of either Billet et al. attack or ours. Specifically, we show that for any given secret key, the overall implementation has the \\emph{exact same} distribution as the implementation of Chow et al. making them both vulnerable to the same attacks.

By improving the state of the art of white-box cryptanalysis and putting forward new attack techniques, we believe our work brings new insights on the failure of existing white-box implementations, which could be useful for the design of future solutions.

*15:17* [Pub][ePrint]
Implementing Lightweight Block Ciphers on x86 Architectures, by Ryad Benadjila and Jian Guo and Victor Lomné and Thomas Peyrin
Lightweight block ciphers are designed so as to fit into very constrained environments, but usually not really with software performance in mind. For classical lightweight applications where many constrained devices communicate with a server, it is also crucial that the cipher has good software performance on the server side. Recent work has shown that bitslice implementations applied to Piccolo and PRESENT led to very good software speeds, thus making lightweight ciphers interesting for cloud applications. However, we remark that bitslice implementations might not be interesting for some situations, where the amount of data to be enciphered at a time is usually small, and very little work has been done on non-bitslice implementations.In this article, we explore general software implementations of lightweight ciphers on x86 architectures, with a special focus on LED, Piccolo and PRESENT. First, we analyze table-based implementations, and we provide a theoretical model to predict the behavior of various possible trade-offs depending on the processor cache latency profile. We obtain the fastest table-based implementations for our lightweight ciphers, which is of interest for legacy processors. Secondly, we apply to our portfolio of primitives the vperm implementation trick for 4-bit Sboxes, which gives good performance, extra side-channels protection, and is quite fit for many lightweight primitives. Finally, we investigate bitslice implementations, analyzing various costs which are usually neglected (bitsliced form (un)packing, key schedule, etc.), but that must be taken in account for many lightweight applications. We finally discuss which type of implementation seems to be the best suited depending on the applications profile.

*15:17* [Pub][ePrint]
Weakness of $\\mbox{${\\mathbb F}$}_{3^{6 \\cdot 509}}$ for Discrete Logarithm Cryptography, by Gora Adj and Alfred Menezes and Thomaz Oliveira and Francisco Rodr\\\'iguez-Henr\\\'iquez
In 2013, Joux, and then Barbulescu, Gaudry, Joux and Thom\\\'{e}, presented new algorithms for computing discrete logarithms in finite

fields of small and medium characteristic. We show that these new

algorithms render the finite field $\\Fmain = \\FF_{3^{3054}}$ weak for

discrete logarithm cryptography in the sense that discrete logarithms

in this field can be computed significantly faster than with the

previous fastest algorithms. Our concrete analysis shows that the

supersingular elliptic curve over $\\FF_{3^{509}}$ with embedding degree

6 that had been considered for implementing pairing-based cryptosystems

at the 128-bit security level in fact provides only a significantly

lower level of security.

*15:17* [Pub][ePrint]
Dynamic Runtime Methods to Enhance Private Key Blinding, by Karine Gandolfi-Villegas and Nabil Hamzi
In this paper we propose new methods to blind exponentsused in RSA and in elliptic curves based algorithms. Due to classical

differential power analysis (DPA and CPA), a lot of countermeasures to

protect exponents have been proposed since 1999 Kocher [20] and by

Coron [13]. However, these blinding methods present some drawbacks

regarding execution time and memory cost. It also got some weaknesses.

Indeed they could also be targeted by some attacks such as The Carry

Leakage on the Randomized Exponent proposed by P.A. Fouque et al.

in [23] or inefficient against some others analysis such as Single Power

Analysis. In this article, we explain how the most used method could

be exploited when an attacker can access test samples. We target here

new dynamic blinding methods in order to prevent from any learning

phase and also to improve the resistance against the latest side channel

analyses published.

*15:17* [Pub][ePrint]
Candidate Indistinguishability Obfuscation and Functional Encryption for all circuits, by Sanjam Garg and Craig Gentry and Shai Halevi and Mariana Raykova and Amit Sahai and Brent Waters
In this work, we study indistinguishability obfuscation and functional encryption for general circuits:Indistinguishability obfuscation requires that given any two equivalent circuits C_0 and C_1 of similar size, the obfuscations of C_0 and C_1 should be computationally indistinguishable.

In functional encryption, ciphertexts encrypt inputs x and keys are issued for circuits C. Using the key SK_C to decrypt a ciphertext CT_x = Enc(x), yields the value C(x) but does not reveal anything else about x. Furthermore, no collusion of secret key holders should be able to learn anything more than the union of what they can each learn individually.

We give constructions for indistinguishability obfuscation and functional encryption that supports all polynomial-size circuits. We accomplish this goal in three steps:

- We describe a candidate construction for indistinguishability obfuscation for NC1 circuits. The security of this construction is based on a new algebraic hardness assumption. The candidate and assumption use a simplified variant of multilinear maps, which we call Multilinear Jigsaw Puzzles.

- We show how to use indistinguishability obfuscation for NC1 together with Fully Homomorphic Encryption (with decryption in NC1) to achieve indistinguishability obfuscation for all circuits.

- Finally, we show how to use indistinguishability obfuscation for circuits, public-key encryption, and non-interactive zero knowledge to achieve functional encryption for all circuits. The functional encryption scheme we construct also enjoys succinct ciphertexts, which enables several other applications.