*22:17* [Pub][ePrint]
Dynamic Countermeasure Against the Zero Power Analysis, by Jean-Luc Danger and Sylvain Guilley and Philippe Hoogvorst and Cédric Murdica and David Naccache
Elliptic Curve Cryptography can be vulnerable to Side-Channel Attacks, such as the Zero Power Analysis (ZPA).This attack takes advantage of the occurrence of special points that bring a zero-value when computing a doubling or an addition of points.

This paper consists in analysing this attack.

Some properties of the said special points are explicited.

A novel dynamic countermeasure is described.

The elliptic curve formul\\ae{} are updated depending on the elliptic curve and the provided base point.

*19:17* [Pub][ePrint]
Multi-user collisions: Applications to Discrete Logs, Even-Mansour and Prince, by Pierre-Alain Fouque and Antoine Joux and Chrysanthi Mavromati
In this paper, we investigate the multi-user setting both in public-key and in secret-key cryptanalytic applications. In this setting, the adversary tries to recover keys of many users in parallel more efficiently than with classical attacks, \\textit{i.e.}, the number of recovered keys multiplied by the time complexity to find a single key, by amortizing the cost among several users. One possible scenario is to recover a single key in a large set of users more efficiently than to recover a key in the classical model. Another possibility is, after some shared precomputation, to be able to learn individual keys very efficiently. This latter model is close to traditional time/memory tradeoff attacks with precomputation. With these goals in mind, we introduce two new algorithmic ideas to improve collision-based attacks in the multi-user setting. Both ideas are derived from the parallelizable collision search as proposed by van~Oorschot and Wiener. We recall that this collision search uses precomputed chains obtained by iterating some basic function. In our cryptanalytic application, each pair of merging chains can be used to correlate the key of two distinct users. The first idea is to construct a graph, whose vertices are keys and whose edges are these correlations. When the graph becomes connected, we simultaneously recover all the keys. Thanks to random graph analysis techniques, we can show that the number of edges that are needed to make this event occurs is small enough to obtain some improved attacks.

The second idea modifies the basic technique of van~Oorschot and Wiener: instead of waiting for two chains to merge, we now require that they become {\\it parallel}.

We first show that, using the first idea alone, we can recover the discrete logs of $L$ users in a group of size $N$ in time $\\widetilde{O}(\\sqrt{NL})$, without any special restriction on the value of $L$. As a first application of these two ideas put together, we show that in the multi-user Even-Mansour scheme, \\textit{all} the keys of $L=N^{1/3}$ users can be found with $N^{1/3+\\epsilon}$ queries for each user (where $N$ is the domain size). Finally, we consider the PRINCE block cipher (with 128-bit keys and 64-bit blocks) and find the keys of $2$ users among a set of $2^{32}$ users in time $2^{65}$. We also describe a new generic attack in the classical model for PRINCE that is better than all published attacks.

*19:17* [Pub][ePrint]
Self-Updatable Encryption: Time Constrained Access Control with Hidden Attributes and Better Efficiency, by Kwangsu Lee and Seung Geol Choi and Dong Hoon Lee and Jong Hwan Park and Moti Yung
Revocation and key evolving paradigms are central issues in cryptography, and in PKI in particular. A novel concern related to these areas was raised in the recent work of Sahai, Seyalioglu, and Waters (Crypto 2012) who noticed that revoking past keys should at times (e.g., the scenario of cloud storage) be accompanied by revocation of past ciphertexts (to prevent unread ciphertexts from being read by revoked users). They introduced revocable-storage attribute-based encryption (RS-ABE) as a good access control mechanism for cloud storage. RS-ABE protects against the revoked users not only the future data by supporting key-revocation but also the past data by supporting ciphertext-update, through which a ciphertext at time $T$ can be updated to a new ciphertext at time $T+1$ using only the public key.Motivated by this pioneering work, we ask whether it is possible to have a modular approach, which includes a primitive for time managed ciphertext update as a primitive. We call encryption which supports this primitive a ``self-updatable encryption\'\' (SUE). We then suggest a modular cryptosystems design methodology based on three sub-components: a primary encryption scheme, a key-revocation mechanism, and a time-evolution mechanism which controls the ciphertext self-updating via an SUE method, coordinated with the revocation (when needed). Our goal in this is to allow the self-updating ciphertext component to take part in the design of new and improved cryptosystems and protocols in a flexible fashion. Specifically, we achieve the following results:

- We first introduce a new cryptographic primitive called self-updatable encryption (SUE), realizing a time-evolution mechanism. In SUE, a ciphertext and a private key are associated with time. A user can decrypt a ciphertext if its time is earlier than that of his private key. Additionally, anyone (e.g., a cloud server) can update the ciphertext to a ciphertext with a newer time. We also construct an SUE scheme and prove its full security under static assumptions.

- Following our modular approach, we present a new RS-ABE scheme with shorter ciphertexts than that of Sahai et al. and prove its security. The length efficiency is mainly due to our SUE scheme and the underlying modularity.

- We apply our approach to predicate encryption (PE) supporting attribute-hiding property, and obtain a revocable-storage PE (RS-PE) scheme that is selectively-secure.

- We further demonstrate that SUE is of independent interest, by showing it can be used for timed-release encryption (and its applications), and for augmenting key-insulated encryption with forward-secure storage.

*19:17* [Pub][ePrint]
Predicate- and Attribute-Hiding Inner Product Encryption in a Public Key Setting, by Yutaka Kawai and Katsuyuki Takashima
In this paper, we propose a reasonable definition of predicate-hiding inner product encryption (IPE) in a public key setting, which we call inner product encryption with ciphertext conversion (IPE-CC), where original ciphertexts are converted to predicate-searchable ones by an helper in possession of a conversion key. We then define a notion of full security for IPE-CC, which comprises three security properties of being adaptively predicate- and attribute-hiding in the public key setting, adaptively (fully-)attribute-hiding against the helper, and usefully secure even against the private-key generator (PKG). We then present the first fully secure IPE-CC scheme, and convert it into the first fully secure symmetric-key IPE (SIPE) scheme, where the security is defined in the sense of Shen, Shi, Waters. All the security properties are proven under the decisional linear assumption in the standard model. The IPE-CC scheme is comparably as efficient as existing attribute-hiding (not predicate-hiding) IPE schemes. We also present a variant of the proposed IPE-CC scheme with the same security that achieves shorter public and secret keys. We employ two key techniques, trapdoor basis setup, in which a new trapdoor is embedded in a public key, and multi-system proof technique, which further generalizes an extended dual system approach given by Okamoto and Takashima recently.

*04:17* [Pub][ePrint]
Fast Software Implementation of Binary Elliptic Curve Cryptography, by Manuel Bluhm and Shay Gueron
This paper presents an efficient and side channel protected software implementation of point multiplication for the standard NIST and SECG binary elliptic curves. The enhanced performance is achieved by improving the L\\`{o}pez-Dahab/Montgomery method at the algorithmic level, and by leveraging Intel\'s AVX architecture and the pclmulqdq processor instruction at the coding level. The fast carry-less multiplication is further used to speed up the reduction on the newest Haswell platforms.

For the five NIST curves over $GF(2^m)$ with $m$ $\\in$ $\\{163,233,283,409,571\\}$, the resulting point multiplication implementation is about 6 to 12 times faster than that of OpenSSL-1.0.1e, enhancing the ECDHE and ECDSA algorithms significantly.