Past Cryptography Seminar

30 January 2019
Thomas Debris-Alazard

Further Information: 

It is a long-standing open problem to build an efficient and secure digital signature scheme based on the hardness of decoding a linear code which could compete with widespread schemes like DSA or RSA. The latter signature schemes are broken by a quantum computer with Shor’s algorithm. Code-based schemes could provide a valid quantum resistant replacement. We present here Wave the first « hash-and-sign » code-based signature scheme which strictly follows the GPV strategy which ensures universal unforgeability. It uses the family of ternary generalized $(U, U+V)$ codes. Our algorithm produces uniformly distributed signatures through a suitable rejection sampling (one rejection every 3 or 4 signatures). Furthermore, our scheme enjoys efficient signature and verification algorithms. Typically, for 128 bits of classical security, signatures are in the order of 10 thousand bits long and the public key is in the order of one megabyte.​

  • Cryptography Seminar
16 January 2019
Alexandre Wallet

The Ring Learning With Errors problem (RLWE) comes in various forms. Vanilla RLWE is the decision dual-RLWE variant, consisting in distinguishing from uniform a distribution depending on a secret belonging to the dual OK^vee of the ring of integers OK of a specified number field K. In primal-RLWE, the secret instead belongs to OK. Both decision dual-RLWE and primal-RLWE enjoy search counterparts. Also widely used is (search/decision) Polynomial Learning With Errors (PLWE), which is not defined using a ring of integers OK of a number field K but a polynomial ring Z[x]/f for a monic irreducible f in Z[x]. We show that there exist reductions between all of these six problems that incur limited parameter losses. More precisely: we prove that the (decision/search) dual to primal reduction from Lyubashevsky et al. [EUROCRYPT 2010] and Peikert [SCN 2016] can be implemented with a small error rate growth for all rings (the resulting reduction is nonuniform polynomial time); we extend it to polynomial-time reductions between (decision/search) primal RLWE and PLWE that work for a family of polynomials f that is exponentially large as a function of deg f (the resulting reduction is also non-uniform polynomial time); and we exploit the recent technique from Peikert et al. [STOC 2017] to obtain a search to decision reduction for RLWE. The reductions incur error rate increases that depend on intrinsic quantities related to K and f.

Based on joint work with Miruna Roșca and Damien Stehlé.

  • Cryptography Seminar
28 November 2018
Alain Passelègue

Pseudorandom functions (PRFs) are one of the fundamental building blocks in cryptography. Traditionally, there have been two main approaches for PRF design: the ``practitioner's approach'' of building concretely-efficient constructions based on known heuristics and prior experience, and the ``theoretician's approach'' of proposing constructions and reducing their security to a previously-studied hardness assumption. While both approaches have their merits, the resulting PRF candidates vary greatly in terms of concrete efficiency and design complexity. In this work, we depart from these traditional approaches by exploring a new space of plausible PRF candidates. Our guiding principle is to maximize simplicity while optimizing complexity measures that are relevant to cryptographic applications. Our primary focus is on weak PRFs computable by very simple circuits (depth-2 ACC^0 circuits). Concretely, our main weak PRF candidate is a ``piecewise-linear'' function that first applies a secret mod-2 linear mapping to the input, and then a public mod-3 linear mapping to the result. We also put forward a similar depth-3 strong PRF candidate.  
The advantage of our approach is twofold. On the theoretical side, the simplicity of our candidates enables us to draw many natural connections between their hardness and questions in complexity theory or learning theory (e.g., learnability of depth-2 ACC^0 circuits and width-3 branching programs, interpolation and property testing for sparse polynomials, and natural proof barriers for showing super-linear circuit lower bounds). On the applied side, the piecewise-linear structure of our candidates lends itself nicely to applications in secure multiparty computation (MPC). Using our PRF candidates, we construct protocols for distributed PRF evaluation that achieve better round complexity and/or communication complexity (often both) compared to protocols obtained by combining standard MPC protocols with PRFs like AES, LowMC, or Rasta (the latter two are specialized MPC-friendly PRFs).
Finally, we introduce a new primitive we call an encoded-input PRF, which can be viewed as an interpolation between weak PRFs and standard (strong) PRFs. As we demonstrate, an encoded-input PRF can often be used as a drop-in replacement for a strong PRF, combining the efficiency benefits of weak PRFs and the security benefits of strong PRFs. We conclude by showing that our main weak PRF candidate can plausibly be boosted to an encoded-input PRF by leveraging standard error-correcting codes.
Joint work with Dan Boneh, Yuval Ishai, Amit Sahai, and David J. Wu.

  • Cryptography Seminar
7 November 2018

We provide lattice-based protocols allowing to prove relations among committed integers. While the most general zero-knowledge proof techniques can handle arithmetic circuits in the lattice setting, adapting them to prove statements over the integers is non-trivial, at least if we want to handle exponentially large integers while working with a polynomial-size modulus qq. For a polynomial L, we provide zero-knowledge arguments allowing a prover to convince a verifier that committed L-bit bitstrings x, y and z are the binary representations of integers X, Y and Z satisfying Z=X+Y over the integers. The complexity of our arguments is only linear in L. Using them, we construct arguments allowing to prove inequalities X <Z among committed integers, as well as arguments showing that a committed X belongs to a public interval [α,β], where α and β can be arbitrarily large. Our range arguments have logarithmic cost (i.e., linear in L) in the maximal range magnitude. Using these tools, we obtain zero-knowledge arguments showing that a committed element X does not belong to a public set S using soft-O(n⋅log|S|) bits of communication, where n is the security parameter. We finally give a protocol allowing to argue that committed L-bit integers X, Y and Z satisfy multiplicative relations Z=XY over the integers, with communication cost subquadratic in L. To this end, we use our protocol for integer addition to prove the correct recursive execution of Karatsuba's multiplication algorithm. The security of our protocols relies on standard lattice assumptions with polynomial modulus and polynomial approximation factor.


  • Cryptography Seminar
30 May 2018

Post-quantum cryptography has been one of the most active subfields of
cryptography in the last few years. This is especially true today as
standardization efforts are currently underway, with no less than 69
candidate cryptographic schemes proposed.

In this talk, I will present one of these schemes: Falcon, a signature
scheme based on the NTRU class of structured lattices. I will focus on
mathematical aspects of Falcon: for example how we take advantage of the
algebraic structure to speed up some operations, or how relying on the
most adequate probability divergence can go a long way in getting more
efficient parameters "for free". The talk will be concluded with a few
open problems.

  • Cryptography Seminar
16 May 2018
Jon Millican

In 2016, Facebook added an optional end-to-end (E2E) encryption feature called Secret Conversations to Messenger. This was challenging to design, as many of Messenger's key properties and features don't fit the typical model of E2E apps. Additionally, Messenger is already one of the world's most popular messaging apps, supporting nearly a billion people across a variety of technical and cultural environments. Because of this, Messenger's deployment of E2E encryption provides attendees with a valuable case study on how to build usable, secure products. 

We will discuss the core properties of a typical E2E app, the core features of Messenger, the distance between the two, and the approach we took to close the gap. We'll examine how minimizing the distance shaped the current E2E experience within Messenger. Through discussion of the key decisions in this process, we'll address the implications for alternative designs with real world comparisons where they exist. 

Although Secret Conversations in Messenger use off-the-shelf Signal Protocol for message encryption, Facebook also wanted to ensure a safe communication channel for community members who may be victims of online abuse. To this end, we created a way for people to report secret conversations that violate our Community Standards, without breaking any E2E guarantees for other messages.

Developing a reporting protocol created an interesting challenge: the potential of fake reports with no intermediary to invalidate them. To pre-empt the possibility of Bob forging a report to incriminate Alice, we added a method that uses two HMACs - one added by the sender and one by Facebook - to “cryptographically frank” messages as we forward them from one party to the other (physical mail uses a similar franking). This technique ensures similar confidence that a report is genuine as we have for messages stored in plaintext on our servers. Additionally, the frank is only verifiable by Facebook after receiving a report from the recipient, thus preventing a third party from using it as evidence against the sender.

We hope that this talk will provide an insight into the intricacies of deploying security features at scale, and the additional considerations necessary when developing an existing product.

  • Cryptography Seminar
9 May 2018
Tibor Jager

Tight security is increasingly gaining importance in real-world
cryptography, as it allows to choose cryptographic parameters in a way
that is supported by a security proof, without the need to sacrifice
efficiency by compensating the security loss of a reduction with larger
parameters. However, for many important cryptographic primitives,
including digital signatures and authenticated key exchange (AKE), we
are still lacking constructions that are suitable for real-world deployment.

This talk will present the first first practical AKE protocol with tight
security. It allows the establishment of a key within 1 RTT in a
practical client-server setting, provides forward security, is simple
and easy to implement, and thus very suitable for practical deployment.
It is essentially the "signed Diffie-Hellman" protocol, but with an
additional message, which is crucial to achieve tight security. This
message is used to overcome a technical difficulty in constructing
tightly-secure AKE protocols.

The second important building block is a practical signature scheme with
tight security in a real-world multi-user setting with adaptive
corruptions. The scheme is based on a new way of applying the
Fiat-Shamir approach to construct tightly-secure signatures from certain
identification schemes.

For a theoretically-sound choice of parameters and a moderate number of
users and sessions, our protocol has comparable computational efficiency
to the simple signed Diffie-Hellman protocol with EC-DSA, while for
large-scale settings our protocol has even better computational per-
formance, at moderately increased communication complexity.

  • Cryptography Seminar