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 - Side-Channel Attacks on Lattice-Based Cryptography: Attacks and Countermeasures [slides] [no video] The transition to post-quantum cryptography requires to run new algorithms on embedded devices with specific constraints such as work-area and power consumption. Additionally, these devices are subject to adversaries with physical access making power side-channel attacks a concrete threat. In this talk, we will first describe recently published side-channel attacks against lattice-based cryptography. Then, we will focus on the countermeasures and how they can be tailored for specific platform and algorithms.
10:50 - 11:10	Coffee break
11:10 - 12:00	Carsten Baum - VOLE-in-the-head and FAEST [slides] [video] 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 [slides] [video] 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 [slides] [video] 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 [slides] [video] 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 [slides] [video] 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 [slides] [video] The MPC-in-the-Head (MPCitH) paradigm is increasingly popular in building zero-knowledge proofs and post-quantum signatures, leveraging techniques from secure multi-party computation. Notably, this paradigm has been employed in 9 out of the 40 candidates selected for the first round of the recent NIST call for additional post-quantum signatures. In this talk, we will introduce the Threshold-Computation-in-the-Head (TCitH) framework, which utilizes threshold secret sharing—specifically, Shamir’s secret sharing—to enhance MPCitH-based proof systems and signature schemes. We will explore its Merkle tree and GGM tree variants, highlighting how it leverages the multiplication homomorphism and packing capabilities of Shamir’s secret sharing. We will discuss the strong connections between this framework and other proof systems (namely VOLE-in-the-Head and Ligero). Additionally, we will see how this framework improves the MPCitH-based NIST candidates and how it can be used in other applications. In particular, we will present a generic construction of a post-quantum ring signature that achieves a substantial improvement over the state of the art.
12:00 - 14:00	Lunch
14:00 - 14:50	Rolfe Schmidt - Post-Quantum Security in Signal [slides] [video] 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? [slides] [video] 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 [slides] [video] 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 from Industry: Post-Quantum Cryptography beyond Signatures and KEMs [slides] [video] When thinking about deploying post-quantum cryptography, one immediately thinks about upgrading the key agreement and signatures in TLS. As we’ll see in Thom’s talk, there is a clear (but not always easy) path for those. There is a lot of cryptography deployed today beyond signatures and KEMs to attain more niche (privacy) goals, such as to name just two: blind signatures (for unlinkable tokens in Apple Private Relay) and oblivious PAKEs (WhatsApp account backup). For this (as Sophie Schmieg would call it) fancy cryptography, there are often no practical post-quantum alternatives. In this talk we will cover some of the missing primitives, and real-world constraints on them.

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.

Sponsor