The next London-ish Lattice Coding and Crypto Meeting: Friday 19 May
23 views
Skip to first unread message
cli...@googlemail.com
Apr 24, 2023, 6:11:51 AM4/24/23
to London-ish Lattice Coding and Crypto Meetings
Dear All,
The next London-ish Lattice Coding and Crypto Meeting will take place Friday 19 May, 2023 at Room 611, Dept. EEE, Imperial College London. The schedule is as follows:
12 - 1 Yixin Shen
Title: Finding Many Collisions via Reusable Quantum Walks- Application to Lattice Sieving
Abstract: Given a random function $f$ with domain $[2^n]$ and codomain $[2^m]$, with $m \geq 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 $\Theta(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 $\Theta(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)}$.
Bio: 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.
1 - 2 Lunch
2 - 3 Jingbo Liu
Title: A New Waring's Problem and Balanced HKZ-Reduction
Abstract: For each positive integer $n$, let $g_\mathbb{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_\mathbb{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_\mathbb{Z}(n)$ is at most an exponential of $\sqrt{n}$. Let $E$ be an imaginary quadratic field and $\mathcal{O}$ be its ring of integers. We also define an analogous number $g_\mathcal{O}(n)$ for writing Hermitian forms over $\mathcal{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_\mathcal{O}(n)$ is at most an exponential of $\sqrt{n}$.
Bio: 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.
3 - 4 Amit Deo
Title: Crypto Dark Matter on the Torus
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.
Bio: 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.
4 - 4.30 Coffee
4.30 - 6 Fuchun Lin
Title: More Efficient Zero-Knowledge Protocols over Z2k via Galois Rings
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 Z2k are significantly lagging behind, with only a proof-of-concept pioneering work called Appenzeller to Brie and a first proposal called MozZ2karella. The ring Z232 or Z264, 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 F2k , the fraction of units in rings Z2k is 1/2. In this work, we first construct protocols over a large Galois ring extension of Z2k (fraction of units close to 1) and then convert to Z2k efficiently using amortization techniques. Our results greatly change the landscape of ZK protocols over Z2k .
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.
Bio: 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.
6 - whenever Dinner
The next London-ish Lattice Coding and Crypto Meeting will take place Friday 19 May, 2023 at Room 611, Dept. EEE, Imperial College London. The schedule is as follows:
12 - 1 Yixin Shen
Title: Finding Many Collisions via Reusable Quantum Walks- Application to Lattice Sieving
Abstract: Given a random function $f$ with domain $[2^n]$ and codomain $[2^m]$, with $m \geq 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 $\Theta(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 $\Theta(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)}$.
Bio: 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.
1 - 2 Lunch
2 - 3 Jingbo Liu
Title: A New Waring's Problem and Balanced HKZ-Reduction
Abstract: For each positive integer $n$, let $g_\mathbb{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_\mathbb{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_\mathbb{Z}(n)$ is at most an exponential of $\sqrt{n}$. Let $E$ be an imaginary quadratic field and $\mathcal{O}$ be its ring of integers. We also define an analogous number $g_\mathcal{O}(n)$ for writing Hermitian forms over $\mathcal{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_\mathcal{O}(n)$ is at most an exponential of $\sqrt{n}$.
Bio: 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.
3 - 4 Amit Deo
Title: Crypto Dark Matter on the Torus
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.
Bio: 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.
4 - 4.30 Coffee
4.30 - 6 Fuchun Lin
Title: More Efficient Zero-Knowledge Protocols over Z2k via Galois Rings
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 Z2k are significantly lagging behind, with only a proof-of-concept pioneering work called Appenzeller to Brie and a first proposal called MozZ2karella. The ring Z232 or Z264, 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 F2k , the fraction of units in rings Z2k is 1/2. In this work, we first construct protocols over a large Galois ring extension of Z2k (fraction of units close to 1) and then convert to Z2k efficiently using amortization techniques. Our results greatly change the landscape of ZK protocols over Z2k .
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.
Bio: 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.
6 - whenever Dinner
We
will have a webpage soon to host the event details.
Cheers,
Rachel and Cong
Cheers,
Rachel and Cong
cli...@googlemail.com
May 18, 2023, 4:44:00 AM5/18/23
to London-ish Lattice Coding and Crypto Meetings
Reply all
Reply to author
Forward
0 new messages