Lattice-based approaches are emerging as a common theme in modern cryptography and coding theory. In communications, they are useful mathematical tools to construct powerful error-correction codes achieving the capacity of wireless channels. In cryptography, they are used to building lattice-based schemes with provable security, better asymptotic efficiency, resilience against quantum attacks and new functionalities such as fully homomorphic encryption.
This meeting — on Friday, 1 December 2023 — is aimed at connecting the two communities with a common interest in lattices. It will consist of several talks on related topics, with a format aimed at encouraging interaction.
Speakers are told the audience is somewhat familiar with lattices.
Quantum Lattice Enumeration in Limited Depth 12:00–13:00 | Fernando Virdia:
Dr Fernando Virdia is a post-doctoral researcher working on cryptographic applications at Associação para a Inovação e Desenvolvimento da FCT NOVA.ID.FCT. He is interested in investigating and developing secure and practical cryptographic primitives. During 2022 and 2023 he was a Research Scientist at Intel Labs, working on post-quantum cryptography. Prior to joining Intel, he was a post-doctoral researcher at the Applied Cryptography Group at ETH Zürich, working with Kenny Paterson, and a fellow of the Zürich Information Security & Privacy Center, ZISC. In 2021, he graduated with a PhD from the Information Security Group at Royal Holloway, University of London, under the supervision of Martin R. Albrecht.
Abstract: In 2018, Aono, Nguyen, and Shen (ASIACRYPT 2018) proposed to use quantum backtracking algorithms (Montanaro, TOC 2018; Ambainis and Kokainis, STOC 2017) to speedup lattice point enumeration. Aono et al.’s work argued that quantum walk speedups can be applied to lattice enumeration, achieving at least a quadratic asymptotic speedup à la Grover search while not requiring exponential amounts of quantum accessible classical memory, as it is the case for quantum lattice point sieving. In this talk, we will explore how to lower bound the cost of using Aono et al.’s techniques on lattice enumeration with extreme cylinder pruning assuming a limit to the maximum depth that a quantum computation can achieve without decohering, with the objective of better understanding the practical applicability of quantum backtracking in lattice cryptanalysis.
Link to paper here.
Lunch Break 13:00–14:00
Concrete NTRU Security and Advances in Practical Electronic Voting 14:00–15:00 | Patrick Hough:
Patrick is a PhD candidate at the University of Oxford whose research focuses on privacy-preserving cryptographic protocols built from lattice assumptions. In particular, he is interested in the design and applications of lattice-based zero-knowledge proofs. Examples of protocols he studies include digital signatures, electronic voting, distributed key generation, and threshold schemes.
Abstract: Until quite recently, lattice reduction attacks on NTRU lattices were believed to behave similarly as on (R)LWE lattices for comparable parameters. A sequence of works over the last few years reveals the problem to be significantly easier on so-called ‘overstretched’ parameter sets; those with large modulus q. In 2021, Ducas and van Woerden gave a concrete ‘fatigue point’ above which values of q give rise to an overstretched parameter set. We begin by extending their analysis to reveal a concrete expression describing the fatigue point for general NTRU secrets. Next, we show how the nature of this expression allows for a more fine-tuned parameter selection when calculating the efficiency/security tradeoff for protocols built upon NTRU. Finally, we will present a new electronic voting scheme, relying on NTRU, which reduces the communication cost when compared to the state-of-the-art lattice voting schemes by 2.5 times overall, with a 5 times reduction in ballot size.
An Overview of WAVE and its Implementation 15:00–16:00 | Gustavo Banegas:
Dr. Gustavo Banegas is a senior cryptographer working at Qualcomm France in Sophia Antipolis, France. Previously, he was a Post-Doc working with Benjamin Smith at the GRACE Team at INRIA in France. From November of 2019 until November of 2020, he was a Post-Doc Researcher at the Department of Computer Science and Engineering at Chalmers University of Technology in Sweden. In the middle of November of 2019, he finished his PhD at the Eindhoven University of Technology under the supervision of Tanja Lange and Daniel J. Bernstein.
Abstract: In this presentation, we will introduce WAVE, a code-based hash-and-sign signature scheme. WAVE is designed to instantiate the theoretical framework developed by Gentry, Peikert, and Vaikuntanathan (GPV) and incorporates a novel code-based trapdoor mechanism. Its security is formally established and inherits from the computational hardness of two well-identified problems, for which the best-known attacks rely on generic decoding algorithms. When implemented with appropriate parameters, WAVE can provide robust security against both classical and quantum adversaries. Throughout this talk, we will delve into the specifics of the WAVE scheme and the challenges associated with achieving a constant-time implementation.
Coffee Break 16:00-16:30
Smoothing Codes and Lattices: Systematic Study and New Bounds 16:30-18:00 | Nicolas Resch:
Dr Nicolas Resch is an assistant professor with the Theoretical Computer Science Group from the Informatics Institute of the University of Amsterdam (UvA). While he has broad interests in much of theoretical computer science, most of his work focuses on coding theory, cryptography, and their intersection. Prior to joining the UvA, he was a postdoctoral researcher in the Cryptology Group at the Centrum Wiskunde & Informatica (CWI), hosted by Ronald Cramer. He obtained his PhD from Carnegie Mellon University (CMU), where he was fortunate to be advised by Venkatesan Guruswami and Bernhard Haeupler.
Abstract:
In this presentation, we will discuss a unified framework for proving smoothing bounds for both lattices and codes, for all choices of spherically-symmetric noise distribution. Initially introduced by Micciancio and Regev, smoothing bounds are traditionally instantiated with Gaussian distributions and are crucial for arguing the security of many lattice-based cryptosystems. Further, they are a key tool in deriving worst-case to average-case reductions.
Our conclusion is that the best strategy for a worst-case bound combines Parseval’s Identity, the Cauchy-Schwarz inequality, and the second linear programming bound, and this holds for both codes and lattices and all noise distributions we considered. For an average-case analysis, the linear programming bound can be replaced by a tight average count.
This alone gives optimal results for spherically uniform noise over random codes and random lattices. This also improves the previous Gaussian smoothing bound for worst-case lattices, but surprisingly our argument provides better results with uniform ball noise than for Gaussian noise. Analogously for codes, the uniform distribution over a sphere gives better bounds than Bernoulli noise. This counter-intuitive situation can be resolved by an appropriate decomposition and truncation of Gaussian/Bernouilli distributions into a convex combination of uniform noise; this puts them on par with the uniform cases.
Time permitting, we will also discuss some follow-up work on applying smoothing bounds to derive worst-case to average-case reductions for codes, and some of the challenges that arise.
Dinner 18:00
Venue
Room 909B
Department of Electrical and Electronic Engineering
Imperial College London
South Kensington
London SW7 2AZ
rEGISTRATION
Email: c.ling@imperial.ac.uk
London-ish Lattice Coding & Crypto Meeting 