Quantum & AI

QUAIL: Quantum Artificial Intelligence Lab

The impact of quantum information can be both constructive and destructive: one the one hand quantum parallelism offers unprecedented computational power; on the other hand it can be used to break cryptosystems. QUAIL is uniquely positioned to address both sides of quantum information science in a holistic approach, namely, not only harnessing the power of quantum computers for artificial intelligence, but also securing communications and computation for machine learning under the threat of quantum computing attacks in the post-quantum era.

Lattice-based cryptography is a highly active area of post-quantum cryptography research. Regular meetings to learn about current research in the field are held to keep up to date with developments in the field and encourage discourse with other researchers. Information for the next Lattice Coding & Crypto meeting is included on this page. 

Led by Dr Roberto Bondesan and Dr Cong Ling

Lattice Coding & Crypto Meeting

May 19, Room 611 Dept. EEE Imperial College London

Finding Many Collisions via Reusable Quantum Walks – Application to Lattice Sieving 12:00-13:00

Yixin Shen 

Yixin Shen is a research fellow at Royal Holloway, University of London. Her work focuses on quantum algorithms and their application in lattice-based cryptanalysis. She completed her PhD at Université Paris Cité in 2021. After that, she worked as a postdoctoral researcher at Royal Holloway. In 2022, she obtained a five-year EPSRC Quantum Technology Career Development Fellowship.

Abstract: Given a random function f with domain 2ⁿ and codomain 2^m, with m >= n, a collision of f is a pair of distinct inputs with the same image. Collision finding is a ubiquitous problem in cryptanalysis, and it has been well-studied using both classical and quantum algorithms. Indeed, the quantum query complexity of the problem is well known to be θ(2^m/3), and matching algorithms are known for any value of m. The situation becomes different when one is looking for multiple collision pairs. Here, for 2^k collisions, a query lower bound of θ(2^(2k+m)/3) was shown by Liu and Zhandry (EUROCRYPT~2019). A matching algorithm is known, but only for relatively small values of m, when many collisions exist.

In this paper, we improve the algorithms for this problem and, in particular, extend the range of admissible parameters where the lower bound is met. Our new method relies on a chained quantum walk algorithm, which might be of independent interest. It allows to extract multiple solutions of an MNRS-style quantum walk, without having to recompute it entirely: after finding and outputting a solution, the current state is reused as the initial state of another walk. As an application, we improve the quantum sieving algorithms for the Shortest Vector Problem (SVP), with a complexity of 2^{0.2563d + o(d)} instead of the previous 2^{0.2570d + o(d)}.

13:00-14:00 Lunch

A New Waring’s Problem and Balanced HKZ-Reduction 14:00-15:00

Jingbo Liu

Dr. Jingbo Liu received her Ph.D. in Mathematics from Wesleyan University, Middletown, CT in 2016 and held a two-year post-doctoral scholar position at the University of Hong Kong. She joined Texas A&M University-San Antonio in 2018 and currently an assistant professor in Mathematics. Her research interests mainly focus on the representation theory of quadratic and Hermitian lattices, and she is also interested in the applications of reduction theory to Engineering and Cryptography. Her recent research publications appeared in Bulletin des Sciences Mathématiques, International Mathematics Research Notices, Journal of Algebra, Journal of Number Theory, and Transactions of the American Mathematical Society.

Abstract: For each positive integer n, let g_Z(n) be the smallest integer such that if an integral quadratic form in n variables can be written as a sum of squares of integral linear forms, then it can be written as a sum of g_Z(n) squares of integral linear forms. We show that every positive definite integral quadratic form is equivalent to what we call a balanced Hermite-Korkin-Zolotarev reduced form and use it to show that the growth of g_Z(n) is at most an exponential of n^1/2. Let E be an imaginary quadratic field and O be its ring of integers. We also define an analogous number g_O(n) for writing Hermitian forms over O as sums of norms of integral linear forms, and when the class number of E is one, we show that the growth of g_O(n) is at most an exponential of n^1/2.

Crypto Dark Matter on the Torus 15:00-16:00

Amit Deo

In, 2019, I completed my PhD in lattice-based cryptography under the supervision of Prof. Martin R. Albrecht at Royal Holloway, University of London. Following this, I was a post-doctoral researcher at ENS de Lyon and a cryptographic researcher at the IoT security company Crypto Quantique. Starting May 2023, I will be joining the research team at the FHE company Zama.

Abstract: In this talk we will briefly overview the notion of a (Partially) Oblivious Pseudorandom Function ((P)OPRF) and give a short overview of existing constructions. We will then present our novel POPRF construction based on the “Crypto Dark Matter” PRF from TCC’18. Finally we will discuss how to heuristically add verifiability to our POPRF construction using low-depth circuit assumptions.

16:00-16:30 Coffee Break

More Efficient Zero-Knowledge Protocols over Z_2^k via Galois Rings 16:30-18:00

Fuchun Lin

Dr. Lin obtained his PhD from Nanyang Technological University, Singapore. His research interest ranges from lattices to secret sharing and MPC. He is now with Shanghai Jiaotong University, China.

Abstract: A recent line of works on zero knowledge (ZK) protocols with a vector oblivious linear function evaluation (VOLE)-based offline phase provides a new paradigm for scalable ZK protocols with prover memory footprint almost the same as verifying the circuit in the clear. Most of these protocols can be made to have a non-interactive online phase, yielding a preprocessing NIZK. In particular, when the preprocessing is realized by a two-round protocol, one obtains a malicious designated verifier-NIZK (MDV-NIZK). Though many practically efficient protocols for proving circuit satisfiability over any field are implemented, protocols over the ring Z_2^k are significantly lagging behind, with only a proof-of-concept pioneering work called Appenzeller to Brie and a first proposal called MozZ2karella. The ring Z_2³² or Z_2⁶⁴, though highly important (it captures computation in real-life programming and the computer architectures such as CPU words), presents non-trivial difficulties because, unlike Galois fields F_2^k , the fraction of units in rings Z_2^k is 1/2. In this work, we first construct protocols over a large Galois ring extension of Z_2^k (fraction of units close to 1) and then convert to Z_2^k efficiently using amortization techniques. Our results greatly change the landscape of ZK protocols over Z_2^k .

This line of works features a pseudorandom correlation generator (PCG) approach to extending VOLE correlation, which is based on variants of LPN over large rings.