newtpqc, a PQCrypto affiliated event

The New Trends in Post-Quantum Cryptography workshop, or newtpqc, is an affiliated event of PQCrypto 2024 on Monday 10 June and Tuesday 11 June 2024, organised at the Mathematical Institute, University of Oxford.

The goal of this workshop is to discuss the most recent and exciting trends of post-quantum cryptography. To this effect, we have asked ten world-class researchers to give keynote talks on cutting-edge topics that will play an important part in post-quantum cryptography in the years to come.

Speakers

Program

Monday 10 June

Time	Speaker - Title
9:30 - 10:00	Breakfast
10:00 - 10:50	Olivier Bronchain - TBD
10:50 - 11:10	Coffee break
11:10 - 12:00	Carsten Baum - VOLE-in-the-head and FAEST Zero-Knowledge (ZK) Proofs are cryptographic protocols that allow a prover to show to a verifier that a certain statement is true, without giving away any additional information in the process. They are a central tool in modern cryptography, with many interesting and surprising applications. Recently, Vector Oblivious Linear Evaluation(VOLE)-based ZK proof systems such as QuickSilver (Yang et al., ACM CCS 2021) and Mac’n’Cheese (Baum et al., IACR CRYPTO 2021) have shown tremendous success in efficiently proving large statements with small constant concrete overhead. In this talk we will discuss the new VOLE-in-the-head approach (Baum et al., IACR CRYPTO 2023) to Zero-Knowledge proofs, and show how it can be used to turn the QuickSilver proof system into a digital signature scheme called FAEST. Moreover, we will discuss other instantiations of the FAEST approach based on Multivariate Quadratic Polynomials and the Rain scheme, as well as recent optimizations to VOLE-in-the-head.
12:00 - 14:00	Lunch
14:00 - 14:50	Ngoc Khanh Nguyen - Polynomial Commitments from Lattices Polynomial commitment scheme allows a prover to commit to a polynomial f over of degree L, and later prove that the committed function was correctly evaluated at a specified point x; in other words f(x)=u for public x,u. Most applications of polynomial commitments, e.g. succinct non-interactive arguments of knowledge (SNARKs), require that (i) both the commitment and evaluation proof are succinct (i.e., polylogarithmic in the degree L) - with the latter being efficiently verifiable, and (ii) no pre-processing step is allowed. Surprisingly, as far as plausibly quantum-safe polynomial commitments are concerned, the currently most efficient constructions only rely on weak cryptographic assumptions, such as security of hash functions. Indeed, despite making use of the underlying algebraic structure, prior lattice-based polynomial commitments still seem to be much behind the hash-based ones. Moreover, security of the aforementioned lattice constructions against quantum adversaries was never formally discussed. In this work, we bridge the gap and propose the first (asymptotically and concretely) efficient lattice-based polynomial commitment with transparent setup and post-quantum security. Our interactive variant relies on the standard (Module-)SIS problem, and can be made non-interactive in the random oracle model using Fiat-Shamir transformation. In addition, we equip the scheme with a knowledge soundness proof against quantum adversaries which can be of independent interest. In terms of concrete efficiency, for L=2^{20} our scheme yields proofs of size 2X smaller than the hash-based FRI commitment (Asiacrypt 2023), and 60X smaller than the very recent lattice-based construction by Albrecht, Fenzi, Lapiha and Nguyen (Eurocrypt 2024).
14:50 - 15:40	Damien Stehlé - Attacks Against the INDCPA-D Security of Exact FHE Schemes A new security model for fully homomorphic encryption (FHE), called INDCPA-D security and introduced by Li and Micciancio [Eurocrypt’21], strengthens INDCPA security by giving the attacker access to a decryption oracle for ciphertexts for which it should know the underlying plaintexts. This includes ciphertexts that it (honestly) encrypted and those obtained from the latter by evaluating circuits that it chose. Li and Micciancio singled out the CKKS FHE scheme for approximate data [Asiacrypt’17] by giving an INDCPA-D attack on it and claiming that INDCPA-D security and INDCPA-D security coincide for FHEs on exact data. In this talk, I will address the widespread belief according to which INDCPA-D attacks are specific to homomorphic computations on approximate data. Indeed, the equivalency formally proved by Li and Micciancio assumes that the schemes are not only exact but have a negligible probability of incorrect decryption. However, almost all competitive implementations of exact FHE schemes give away strong correctness by analyzing correctness heuristically and allowing probabilities of incorrect decryption that are not sufficiently small in an adversarial context. I will show how to exploit this discrepancy to mount practical key-recovery attacks against all major exact FHE schemes. The talk is based on joint work with Jung Hee Cheon, Hyeongmin Choe, Alain Passelègue and Elias Suvanto.
15:40 - 16:00	Break
16:00 - 16:50	Martin Albrecht - Adventures in SIS with Hints I will talk you through a range of “SIS with hints” assumptions – see https://malb.io/sis-with-hints.html – that have (mostly) recently been proposed. These assumptions augment the usual (Inhomogeneous) Short Integer Solutions (ISIS) problem by also handing out short preimages for some specific targets – called “hints” – and claim that solving ISIS remains hard despite these hints. I will spend a bit more time on the most absurd-sounding of them: “SIS remains hard even when given a trapdoor”. The catch is that the required SIS solution may be only marginally longer than the given trapdoor. I will argue that if this problem is easy then single-exponential time sieving can be done in polynomial memory, a long open problem. An application of this result is that signing the same message twice without salting in a GPV-style signature scheme may not enable forgeries.</sub>

Tuesday 11 June

Time	Speaker - Title
9:30 - 10:00	Breakfast
10:00 - 10:50	Sofía Celi - Private Information Retrieval and Lattices: Advancements and Future Directions This talk explores recent advancements in Private Information Retrieval (PIR), particularly single-server constructions. Emphasizing real-world deployment needs, we delve into new schemes and outline the trajectory of future research in this field. Additionally, we investigate the role of lattices in PIR solutions and the underlying assumptions.
10:50 - 11:10	Coffee break
11:10 - 12:00	Matthieu Rivain - Threshold Computation-in-the-head
12:00 - 14:00	Lunch
14:00 - 14:50	Rolfe Schmidt - Post-Quantum Security in Signal This talk will provide a detailed look at how Signal is approaching post-quantum security. After quickly discussing Signal’s threat model, we will survey Signal’s features, supporting systems, and performance constraints to get a high level view of their post-quantum security needs. To make Signal’s approach concrete, we will look in detail at how Signal developed the PQXDH handshake protocol and used formal verification tools to ensure that they provably met their security goals and how these findings relate to recent developments in KEM security properties.
14:50 - 15:40	Thom Wiggers - TLS: Are we PQ yet? The TLS protocol (famous for https://) is perhaps the most-used cryptographic protocol. As such, it is extremely important that it gets migrated to post-quantum cryptography. Fortunately, the TLS working group, browsers like Chrome and Firefox, and service providers like Cloudflare are making headway to solve the problem. Chrome on desktop computer already prefers Kyber768+X25519 key exchange by default! So, just migrate the certificates, and we’re done, right?
15:40 - 16:00	Break
16:00 - 16:50	Katharina Boudgoust - Aggregating Lattice-Based Signatures - Challenges and New Results As all participants of this workshop know, constructing cryptographic primitives which seem to resist quantum attacks is a very active research area. Whereas the design of relatively basic primitives, such as encryption and signature schemes, has reached in recent years a decent state of maturity, the situation is much less settled for more advanced primitives. Lattice-based cryptography has shown to be a promising direction to build presumably post-quantum cryptography. This is reflected by NIST’s choice in 2022 to select one encryption scheme (Kyber) and two signature schemes (Dilithium and Falcon) based on lattices in their post-quantum project. In this talk, we focus on the design of lattice-based signatures which allow for the additional functionality of aggregation. After having introduced this notion and its various flavors, we review the challenges met when trying to adapt existing approaches from the pre-quantum world to the lattice world. We then discuss recent results which have made some progress in this area.
16:50 - 17:40	Bas Westerbaan - Open problems in the industry

Venue

newtpqc is organised at the Mathematical Institute of the University of Oxford:

Mathematical Institute
University of Oxford
Andrew Wiles Building
Woodstock Road
Oxford
OX2 6GG

Detailed instructions to travel to Oxford and to the conference venue can be found here.