Paris Crypto Day

Jan 12 @ ENS

The fourth Paris Area Crypto Day will be held on 12.01.2017 (Thu) at ENS.

• Amphi Dussane, ENS (map)
• Please register (free, lunch included). Deadline 09.01.2016

Program

Abstracts

Low-Complexity Cryptographic Hash Functions
Vinod Vaikuntanathan (MIT)

Cryptographic hash functions are efficiently computable functions that shrink a long input into a shorter output while achieving some of the useful security properties of a random function. The most common type of such hash functions is collision resistant hash functions (CRH), which prevent an efficient attacker from finding a pair of inputs on which the function has the same output.

Despite the ubiquitous role of hash functions in cryptography, several of the most basic questions regarding their computational and algebraic complexity remained open. In this work we settle most of these questions under new, but arguably quite conservative, cryptographic assumptions, whose study may be of independent interest.

Concretely, we obtain the following results:

• Low-complexity CRH. Assuming the intractability of finding short codewords in natural families of linear error-correcting codes, there are CRH that shrink the input by a constant factor and have a constant algebraic degree over Z_2 (as low as 3), or even constant output locality and input locality and thus computable by linear-size circuits. Such CRH are potentially MPC- and FHE-friendly.

• Win-win results. If low-degree CRH with good shrinkage do not exist, this has useful consequences for learning algorithms and data structures.

• Degree-2 hash functions. Assuming the conjectured intractability of solving a random system of quadratic equations over Z_2, a uniformly random degree-2 mapping is a universal one-way hash function (UOWHF). UOWHF relaxes CRH by forcing the attacker to find a collision with a random input picked by a challenger. On the other hand, a uniformly random degree-2 mapping is not a CRH. We leave the existence of degree-2 CRH open, and relate it to open questions on the existence of degree-2 randomized encodings of functions.

An important research direction is to understand the security of our assumptions from the cryptanalysis standpoint.

Joint Work with Benny Applebaum, Naama Haramaty, Yuval Ishai and Eyal Kushilevitz, to appear in ITCS 2017.

Basing Privacy-Preserving Credentials on Standard Signatures
Melissa Chase (Microsoft Research)

Practical anonymous credential systems are generally built around sigma-protocol ZK proofs. This requires that credentials be based on specially formed signatures. Here we ask whether we can instead use a standard (say, RSA, or (EC)DSA) signature that includes formatting and hashing messages, as a credential, and still provide privacy. Existing techniques do not provide efficient solutions for proving knowledge of such a signature: On the one hand, ZK proofs based on garbled circuits (Jawurek et al. 2013) give efficient proofs for checking formatting of messages and evaluating hash functions. On the other hand they are expensive for checking algebraic relations such as RSA or discrete-log, which can be done efficiently with sigma protocols.

We design new constructions obtaining the best of both worlds: combining the efficiency of the garbled circuit approach for non-algebraic statements and that of sigma protocols for algebraic ones. We then discuss how to use these as building-blocks to construct privacy-preserving credential systems based on standard RSA and (EC)DSA signatures.

Other applications of our techniques include anonymous credentials with more complex policies, the ability to efficiently switch between commitments (and signatures) in different groups, and secure two-party computation on committed/signed inputs.

De la crypto à la « cyberguerre » ?
Guillaume Poupard (ANSSI)

Discipline pourtant exclusivement défensive, la cryptographie a historiquement été associée à nombre de conflits et d’histoires d’espionnage en tout genre. On aurait pu croire, avec la libéralisation mais également la banalisation de son usage dans notre vie de tous les jours que la crypto allait réintégrer le simple champ des technologies indispensables aux développements numériques mais il n’en est rien. Dans un contexte de fortes incertitudes géopolitiques où le « cyber » tend à jouer un rôle déstabilisateur de plus important mais également face à la menace de terroristes présumés adeptes de « messageries cryptées », la cryptologie continue à jouer un rôle complexe mais déterminant. Petit tour d’horizon de la question et des enjeux vu de l’ANSSI…

Content Delivery over TLS: A Cryptographic Analysis of Keyless SSL
Pierre-Alain Fouque (Rennes)

The Transport Layer Security (TLS) protocol is designed to allow two parties, a client and a server, to communicate securely over an insecure network. However, when TLS connections are proxied through an intermediate middlebox, like a Content Delivery Network (CDN), the standard end-to-end security guarantees of the protocol no longer apply. In this talk, we will investigate the security guarantees provided by Keyless SSL, a CDN architecture currently deployed by CloudFlare that composes two TLS 1.2 handshakes to obtain a proxied TLS connection. We demonstrate new attacks that show that Keyless SSL does not meet its intended security goals. These attacks have been reported to CloudFlare and we are in the process of discussing fixes.

We argue that proxied TLS handshakes require a new, stronger, 3-party security definition. We modify Keyless SSL and prove that our modifications guarantee the new 3-party security, assuming ACCE-security for the individual TLS 1.2 connections. We also propose a new design for Keyless TLS 1.3 and prove its security, assuming that the TLS 1.3 handshake implements an authenticated 2-party key exchange. Notably, we show that secure proxying in Keyless TLS 1.3 is computationally lighter and requires simpler assumptions on the certificate infrastructure than our proposed fix for Keyless SSL. Our results indicate that proxied TLS architectures, as currently used by a number of CDNs, may be vulnerable to subtle attacks and deserve close attention.

joint work with K. Bhargavan, I. Carlson, C. Onete, and B. Richard Will appear at EURO S&P 2017.