Paris Crypto Day

Oct 25 @ ENS

The next Paris Area Crypto Day will be held on 25.10.2018 (Thu) at ENS.

• Amphi Jaurès, ENS (29 rue d’Ulm, level B1)
• Please register (free). Deadline 23.10.2018

Tentative Program

Organizers. Michel Abdalla, Georg Fuchsbauer, and Hoeteck Wee (ENS)

Acknowledgements. ERC CryptoCloud and aSCEND

Abstracts

Anonymity in Cryptocurrencies Sarah Meiklejohn (UCL)

A long line of recent research has demonstrated that existing cryptocurrencies often do not achieve the level of anonymity that users might expect they do, while at the same time another line of research has worked to increase the level of anonymity by adding new features to existing cryptocurrencies or creating entirely new cryptocurrencies. This talk will explore both of these lines of research, briefly demonstrating de-anonymization attacks but focusing primarily on techniques for anonymity that achieve provably secure guarantees.

Updatable and Universal Common Reference Strings with Applications to zk-SNARKs Mary Maller (UCL)

By design, existing (pre-processing) zk-SNARKs embed a secret trapdoor in a relation-dependent common reference strings (CRS). The trapdoor is exploited by a (hypothetical) simulator to prove the scheme is zero knowledge, and the secret-dependent structure facilitates a linear-size CRS and linear-time prover computation. If known by a real party, however, the trapdoor can be used to subvert the security of the system. The structured CRS that makes zk-SNARKs practical also makes deploying zk-SNARKS problematic, as it is difficult to argue why the trapdoor would not be available to the entity responsible for generating the CRS. Moreover, for pre-processing zk-SNARKs a new trusted CRS needs to be computed every time the relation is changed.

In this paper, we address both issues by proposing a model where a number of users can update a universal CRS. The updatable CRS model guarantees security if at least one of the users updating the CRS is honest. We provide both a negative result, by showing that zk-SNARKs with private secret-dependent polynomials in the CRS cannot be updatable, and a positive result by constructing a zk-SNARK based on a CRS consisting only of secret-dependent monomials. The CRS is of quadratic size, is updatable, and is universal in the sense that it can be specialized into one or more relation-dependent CRS of linear size with linear-time prover computation.

(Joint work with Jens Groth, Markulf Kohlweiss, Sarah Meiklejohn and Ian Miers)

The Algebraic Group Model and its Applications Julian Loss (RUB)

One of the most important and successful tools for assessing hardness assumptions in cryptography is the Generic Group Model (GGM). Over the past two decades, numerous assumptions and protocols have been analyzed within this model. While a proof in the GGM can certainly provide some measure of confidence in an assumption, its scope is rather limited since it does not capture group-specific algorithms that make use of the representation of the group.

To overcome this limitation, we propose the Algebraic Group Model (AGM), a model that lies in between the Standard Model and the GGM. It is the first restricted model of computation covering group-specific algorithms yet allowing to derive simple and meaningful security statements.
To prove its usefulness, we show that several important assumptions, among them the Computational Diffie-Hellman, the Strong Diffie-Hellman, and the interactive LRSW assumptions, are equivalent to the Discrete Logarithm (DLog) assumption in the AGM. On the more practical side, we prove tight security reductions for two important schemes in the AGM to DLog or a variant thereof: the BLS signature scheme and Groth’s zero-knowledge SNARK (EUROCRYPT 2016), which is the most efficient SNARK for which only a proof in the GGM was known. Our proofs are quite simple and therefore less prone to subtle errors than those in the GGM.

Moreover, in combination with known lower bounds on the Discrete Logarithm assumption in the GGM, our results can be used to derive lower bounds for all the above-mentioned results in the GGM.

(Joint work with Georg Fuchsbauer and Eike Kiltz)

Post-quantum Diffie–Hellman: Caveat Emptor Benjamin Smith (INRIA/LIX)

In the mad dash towards post-quantum crypto, it is often overlooked that it has been surprisingly hard to find a practical drop-in replacement for Diffie–Hellman key exchange (as opposed to post-quantum KEMs for key establishment). Recent work revisiting an old isogeny-based primitive due to Couveignes, Rostovtsev, and Stolbunov has given some very useful results in this direction: practical post-quantum Diffie–Hellman is now in reach, especially with the new CSIDH proposal. These key exchanges, based on isogenies of elliptic curves with commutative endomorphism rings, have a clear superficial resemblance to classical Diffie–Hellman; but the deeper we look, the further their properties diverge from the common intuitions for Diffie–Hellman-based cryptosystems that we have developed over the last four decades. In this talk we will compare and contrast pre- and post-quantum Diffie–Hellman algorithms and their applications, highlighting some important subtleties and distinctions.

Fast Homomorphic Evaluation of Deep Discretized Neural Networks Michele Minelli (ENS)

The rise of machine learning as a service multiplies scenarios where one faces a privacy dilemma: either sensitive user data must be revealed to the entity that evaluates the cognitive model (e.g., in the Cloud), or the model itself must be revealed to the user so that the evaluation can take place locally. Fully Homomorphic Encryption (FHE) offers an elegant way to reconcile these conflicting interests in the Cloud-based scenario and also preserve non-interactivity. However, due to the inefficiency of existing FHE schemes, most applications prefer to use Somewhat Homomorphic Encryption (SHE), where the complexity of the computation to be performed has to be known in advance, and the efficiency of the scheme depends on this global complexity.

In this paper, we present a new framework for homomorphic evaluation of neural networks, that we call FHE-DiNN, whose complexity is strictly linear in the depth of the network and whose parameters can be set beforehand. To obtain this scale-invariance property, we rely heavily on the bootstrapping procedure. We refine the recent FHE construction by Chillotti et al. (ASIACRYPT 2016) in order to increase the message space and apply the sign function (that we use to activate the neurons in the network) during the bootstrapping. We derive some empirical results, using TFHE library as a starting point, and classify encrypted images from the MNIST dataset with more than 96% accuracy in less than 1.7 seconds.

Finally, as a side contribution, we analyze and introduce some variations to the bootstrapping technique of Chillotti et al. that offer an improvement in efficiency at the cost of increasing the storage requirements.

(Joint work with Florian Bourse, Matthias Minihold and Pascal Paillier)

Towards RSA-OAEP without Random Oracles Adam O’Neill (Georgetown)

We give the first positive results about instantiability of the widely implemented and standarized RSA-OAEP encryption scheme of Bellare and Rogaway (EUROCRYPT 1994) and variants under chosen-ciphertext attack. Recall that RSA-OAEP adds redundancy and randomness to a message before composing two rounds of an underlying Feistel transform, whose round functions are modeled as random oracles (ROs), with RSA. First, we show that either of the two oracles (while still modeling the other as a RO) can be instantiated in RSA-OAEP under IND-CCA2 using mild standard model assumptions. Surprisingly, ours are the first “partial instantiation” results for RSA-OAEP. We obtain them by exploiting (generalizations of) algebraic properties of RSA proven by Barthe, Pointcheval, and Báguelin (CCS 2012). Second, we show that both oracles can be instantiated simultaneously for two variants of RSA-OAEP, called “t-clear” and “s-clear” RSA-OAEP. In particular, we are the first to consider s-clear RSA-OAEP, and our result for it yields the most efficient RSA-based IND-CCA2 secure scheme (under plausible assumptions) in the standard model to date. We obtain it by leveraging a new hierarchy of extractability-style assumptions in the sense of Canetti and Dakdouk (TCC 2010) on the round functions, as well as novel yet plausible assumptions on RSA.

(Joint work with Nairen Cao and Mohammad Zaheri)