ERC Consolidator Grant: Advanced Practical Post-Quantum Cryptography from Lattices

My ERC Consolidator Grant application titled “Advanced Practical Post-Quantum Cryptography from Lattices” has been selected(*) for funding by the European Research Council. Here’s my blurb:

Standardisation efforts for post-quantum public-key encryption and signatures are close to completion. At the same time the most recent decade has seen the deployment, at scale, of more advanced cryptographic algorithms where no efficient post-quantum candidates exist. These algorithms e.g. permit to give strong guarantees even after some parties were compromised, privacy-preserving contact lookups, credentials and e-cash. This project will tackle the challenge of “lifting” such constructions to the post-quantum era by pursuing three guiding questions:

• What is the cost of solving lattice problems with and without hints on a quantum computer? Answers to this question will provide confidence in the entire stack of lattice-based cryptography from “basic” to “advanced”. Studying the presence of hints tackles side-channel attacks and advanced constructions.
• What are the lattice assumptions that establish feature- and (near) performance-parity with pre-quantum cryptography? Standard lattice assumptions do not seem to establish feature parity with pairing-based or even some Diffie-Hellman-based pre-quantum constructions, how can we achieve efficient and secure advanced practical post-quantum solutions?
• How efficient is a careful composition of lattice-base cryptography with other assumptions? If we want to deploy our post-quantum solutions in practice, we will need to design hybrid schemes that are secure if either of their pre- or post-quantum part is secure and to deploy many advanced lattice-based primitives in practice we need to carefully compose them with zero-knowledge proofs to rule out some attacks.

Lattice-based cryptography has established itself as a key technology to realise both efficient basic primitives like post-quantum encryption and advanced solutions such as computation with encrypted data and programs. It is thus well positioned to tackle the middle ground of advanced yet practical primitives for phase 2 of the post-quantum transition.

Concretely, this grant award means that I’ll be recruiting for several postdoc and PhD student (international fees, i.e. not restricted to people from the UK) positions in post-quantum and lattice-based cryptography. I have a bit of flexibility in when to put those on the market, so if you think these positions would fit you well, feel free to get in touch with me to informally discuss it.

In somewhat related news, we’re hiring for a lecturer (≈ assistant professor) position at King’s College London. We’re also hiring for PhD or postdoc residency (≈ intern) positions at SandboxAQ.

(*) Well, there is the tiny issue of Brexit: “As described in Annex 3 of the ERC Work Programme 2022, successful applicants established in a country in the process of associating to Horizon Europe will not be treated as established in an associated country if the association agreement does not apply by the time of the signature of the grant agreement.” See also UKRI’s guidance on the UK’s guarantee scheme.

The k-R-ISIS (of Knowledge) Assumption

Our paper – together with Valerio Cini, Russell W. F. Lai, Giulio Malavolta and Sri Aravinda Krishnan Thyagarajan – titled Lattice-Based SNARKs: Publicly Verifiable, Preprocessing, and Recursively Composable will be presented at CRYPTO’22. A pre-print is available and here’s the abstract:

A succinct non-interactive argument of knowledge (SNARK) allows a prover to produce a short proof that certifies the veracity of a certain NP-statement. In the last decade, a large body of work has studied candidate constructions that are secure against quantum attackers. Unfortunately, no known candidate matches the efficiency and desirable features of (pre-quantum) constructions based on bilinear pairings.

In this work, we make progress on this question. We propose the first lattice-based SNARK that simultaneously satisfies many desirable properties: It (i) is tentatively post-quantum secure, (ii) is publicly-verifiable, (iii) has a logarithmic-time verifier and (iv) has a purely algebraic structure making it amenable to efficient recursive composition. Our construction stems from a general technical toolkit that we develop to translate pairing-based schemes to lattice-based ones. At the heart of our SNARK is a new lattice-based vector commitment (VC) scheme supporting openings to constant-degree multivariate polynomial maps, which is a candidate solution for the open problem of constructing VC schemes with openings to beyond linear functions. However, the security of our constructions is based on a new family of lattice-based computational assumptions which naturally generalises the standard Short Integer Solution (SIS) assumption.

In this post, I want to give you a sense of our new family of assumptions, the k-M-ISIS family of assumptions, and its variants. Meanwhile, Russell has written a post focusing on building the SNARK and Aravind has written about the nice things that we can do with our lattice-based SNARKs.

The One-More-ISIS Problem

In “Practical, Round-Optimal Lattice-Based Blind Signatures” by Shweta Agrawal, Elena Kirshanova, Damien Stehle and Anshu Yadav, the authors introduce a new candidate hard lattice problem. They introduce this problem to build blind signatures but in this blog post, I’ll ignore the application and only talk about the cryptanalytic target: One-more-ISIS.

Lattice Estimator, Rebooted

We have “rebooted” the LWE Estimator as the Lattice Estimator. This was born out of frustration with the limitations of the old codebase.

• Here is how we had to express, e.g., NIST Round 1 Kyber-512 for the “Estimate all the {LWE, NTRU} schemes!” project:

  n = 512
  sd = 1.5811388300841898
  q = 7681
  alpha = sqrt(2*pi)*sd/RR(q)
  m = n
  secret_distribution = "normal"
  primal_usvp(n, alpha, q, secret_distribution=secret_distribution, m=m)
  

  In contrast, here’s how we express NIST Round 3 Kyber-512 now:

  from estimator import *
  Kyber512 = LWE.Parameters(
      n=2 * 256,
      q=3329,
      Xs=ND.CenteredBinomial(3),
      Xe=ND.CenteredBinomial(3),
      m=2 * 256,
      tag="Kyber 512",
  )
  

  That is, the user should not have to pretend their input distributions are some sort of Gaussians, the estimator should be able to handle standard distributions used in cryptography. Hopefully this makes using the estimator less error-prone.

• It is well-established by now that making the Geometric Series Assumption for “primal attacks” on the Learning with Errors problem can be somewhat off. It is more precise to use a simulator to predict the shape after lattice reduction but the old estimator did not support this. Now we do:

  lwe.primal_usvp(Kyber512, red_shape_model="GSA")
  

  rop: ≈2^141.2, red: ≈2^141.2, δ: 1.004111, β: 382, d: 973, tag: usvp
  

  lwe.primal_usvp(Kyber512, red_shape_model="CN11")
  

  rop: ≈2^144.0, red: ≈2^144.0, δ: 1.004038, β: 392, d: 976, tag: usvp
  

  The design is (hopefully) modular enough that you can plug in your favourite simulator.

• The algorithms we costed were getting outdated. For example, we had these (really slow) estimates for the “decoding attack” that was essentially equivalent to computing a BKZ-ϐ reduced basis followed by calling an SVP oracle in some dimension η. This is now implemented as primal_bdd.

  lwe.primal_bdd(Kyber512, red_shape_model="CN11")
  

  rop: ≈2^140.5, red: ≈2^139.3, svp: ≈2^139.6, β: 375, η: 409, d: 969, tag: bdd
  

  Similarly, our estimates for dual and hybrid attacks hadn’t kept up with the state of the art. Michael and Ben (both now at Zama) contributed code to fix that and have blogged about it here.

  lwe.dual_hybrid(Kyber512)
  

  rop: ≈2^157.7, mem: ≈2^153.6, m: 512, red: ≈2^157.4, δ: 1.003726, β: 440, d: 1008, ↻: ≈2^116.5, ζ: 16, tag: dual_hybrid
  

  lwe.primal_hybrid(Kyber512)
  

  rop: ≈2^276.4, red: ≈2^276.4, svp: ≈2^155.3, β: 381, η: 2, ζ: 0, |S|: 1, d: 1007, prob: ≈2^-133.2, ↻: ≈2^135.4, tag: hybrid
  

  We’re still not complete (e.g. BKW with sieving is missing), but the more modular design, e.g. the one-big-Python-file-to-rule-them-all is no more, should make it easier to update the code.

• The rename is motivated by our ambition to add estimation modules for attacks on NTRU (not just viewing it as LWE) and SIS, too.

For most users, the usage should be fairly simple, e.g.

params = LWE.Parameters(n=700, q=next_prime(2^13), Xs=ND.UniformMod(3), Xe=ND.CenteredBinomial(8), m=1400, tag="KewLWE")
_ = LWE.estimate.rough(params)

usvp                 :: rop: ≈2^153.9, red: ≈2^153.9, δ: 1.003279, β: 527, d: 1295, tag: usvp
dual_hybrid          :: rop: ≈2^178.9, mem: ≈2^175.1, m: 691, red: ≈2^178.7, δ: 1.002943, β: 612, d: 1360, ↻: 1, ζ: 31, tag: dual_hybrid

 _ = LWE.estimate(params)

bkw                  :: rop: ≈2^210.4, m: ≈2^198.0, mem: ≈2^199.0, b: 15, t1: 0, t2: 16, ℓ: 14, #cod: 603, #top: 0, #test: 98, tag: coded-bkw
usvp                 :: rop: ≈2^182.3, red: ≈2^182.3, δ: 1.003279, β: 527, d: 1295, tag: usvp
bdd                  :: rop: ≈2^178.7, red: ≈2^178.1, svp: ≈2^177.2, β: 512, η: 543, d: 1289, tag: bdd
dual                 :: rop: ≈2^207.8, mem: ≈2^167.1, m: 695, red: ≈2^207.6, δ: 1.002926, β: 617, d: 1394, ↻: ≈2^165.5, tag: dual
dual_hybrid          :: rop: ≈2^201.3, mem: ≈2^197.4, m: 676, red: ≈2^201.1, δ: 1.003008, β: 594, d: 1341, ↻: ≈2^141.9, ζ: 35, tag: dual_hybrid

If you are an attack algorithm designer, we would appreciate if you would contribute estimates for your algorithm to the estimator. If we already have support for it implemented, we would appreciate if you could compare our results against what you expect. If you are a scheme designer, we would appreciate if you could check if our results match what you expect. If you find suspicious behaviour or bugs, please open an issue on GitHub.

You can read the documentation here and play with the new estimator in your browser here (beware that Binder has a pretty low time-out, though).

Round-optimal Verifiable Oblivious Pseudorandom Functions from Ideal Lattices

PKC’21 is nearly upon us which – in this day and age – means a new YouTube playlist of talks. Eamonn and Fernando wrote a nice paper on on the success probability of solving unique SVP via BKZ which Fernando is describing here:

Alex is presenting our – with Amit and Nigel – work on round-optimal Verifiable Oblivious PseudoRandom Functions (VOPRF) from ideal lattices here:

Since Alex is doing an amazing job at walking you through our paper I won’t attempt this here. Rather, let me point out a – in my book – cute trick in one of our appendices that may have applications elsewhere.

Postdoc at Royal Holloway on Lattice-based Cryptography

I’m looking for a postdoc to work with me and others – in the ISG and at Imperial College – on lattice-based cryptography and, ideally, its connections to coding theory.

The ISG is a nice place to work; it’s a friendly environment with strong research going on in several areas. We got people working across the field of information security including several people working on cryptography. For example, Carlos Cid, Anamaria Costache, Lydia Garms, Jianwei Li, Sean Murphy, Rachel Player, Eamonn Postlethwaite, Joe Rowell, Fernando Virdia and me all have looked at or are looking at lattice-based cryptography.

A postdoc here is a 100% research position, i.e. you wouldn’t have teaching duties. That said, if you’d like to gain some teaching experience, we can arrange for that as well.

If you have e.g. a two-body problem and would like to discuss flexibility about being in the office (assuming we’ll all be back in the office at some post-covid19 point), feel free to get in touch.

Postdoc at Royal Holloway on Lattice-based Cryptography

Update: 25/09/2020: New deadline: 30 October.

We are looking for a postdoc to join us to work on lattice-based cryptography. This postdoc is funded by the EU H2020 PROMETHEUS project for building privacy preserving systems from advanced lattice primitives. At Royal Holloway, the project is looked after by Rachel Player and me. Feel free to e-mail me with any queries you might have.

The ISG is a nice place to work; it’s a very friendly environment with strong research going on in several areas. We got people working across the field of information security including several people working on cryptography. A postdoc here is a 100% research position, i.e. you wouldn’t have teaching duties. That said, if you’d like to gain some teaching experience, we can arrange for that as well.

Also, if you have e.g. a two-body problem and would like to discuss flexibility about being in the office (assuming we’ll all be back in the office at some post-covid19 point), feel free to get in touch.

Faster Enumeration-based Lattice Reduction

Our paper “Faster Enumeration-based Lattice Reduction: Root Hermite Factor in Time ” – together with Shi Bai, Pierre-Alain Fouque, Paul Kirchner, Damien Stehlé and Weiqiang Wen – is now available on ePrint (the work has been accepted to CRYPTO 2020). Here’s the abstract:

We give a lattice reduction algorithm that achieves root Hermite factor in time and polynomial memory. This improves on the previously best known enumeration-based algorithms which achieve the same quality, but in time . A cost of was previously mentioned as potentially achievable (Hanrot-Stehlé’10) or as a heuristic lower bound (Nguyen’10) for enumeration algorithms. We prove the complexity and quality of our algorithm under a heuristic assumption and provide empirical evidence from simulation and implementation experiments attesting to its performance for practical and cryptographic parameter sizes. Our work also suggests potential avenues for achieving costs below for the same root Hermite factor, based on the geometry of SDBKZ-reduced bases.

The Approximate GCD Problem

Steven Galbraith once told me that he expects mathematicians to teach RSA long after the world has migrated to post-quantum algorithms; because it is so easy to explain. Arguably, LWE is easier to explain than RSA but the Approximate Greatest Common Divisors problem (AGCD) is even easier than that and requires only scalars. Thus, it is a nice post-quantum alternative for an undergraduate mathematics module. Someone should perhaps write an undergraduate mathematics textbook introducing cryptography using Approximate Common Divisors.

Postdoc at Royal Holloway on Lattice-based Cryptography

We are looking for a postdoc to join us to work on lattice-based cryptography. This postdoc is funded by the EU H2020 PROMETHEUS project for building privacy preserving systems from advanced lattice primitives. At Royal Holloway, the project is looked after by Rachel Player and me. Feel free to e-mail me with any queries you might have.

The ISG is a nice place to work; it’s a very friendly environment with strong research going on in several areas. We got people working across the field of information security including several people working on cryptography. A postdoc here is a 100% research position, i.e. you wouldn’t have teaching duties. That said, if you’d like to gain some teaching experience, we can arrange for that as well.

Also, if you have e.g. a two-body problem and would like to discuss flexibility about being in the office, feel free to get in touch.

Location:	Egham
Salary:	£41,743 per annum – including London Allowance
Closing Date:	Thursday 12 September 2019
Interview Date:	To be confirmed
Reference:	0819-315

Full-Time, Fixed Term (until December 2021)

The ISG is seeking to recruit a post-doctoral research assistant to work in the area of cryptography. The position is available now until 31 December 2021.

The PDRA will work alongside Dr. Martin Albrecht, Dr. Rachel Player and other cryptographic researchers at Royal Holloway on topics in lattice-based cryptography. This post is part of the EU H2020 PROMETHEUS project (http://prometheuscrypt.gforge.inria.fr) for building privacy preserving systems from advanced lattice primitives. Our research focus within this project is on cryptanalysis and implementations, but applicants with a strong background in other areas such as protocol/primitive design are also encouraged to apply.

Applicants should have already completed, or be close to completing, a PhD in a relevant discipline. Applicants should have an outstanding research track record in cryptography. Applicants should be able to demonstrate scientific creativity, research independence, and the ability to communicate their ideas effectively in written and verbal form.

In return we offer a highly competitive rewards and benefits package including:

• Generous annual leave entitlement
• Training and Development opportunities
• Pension Scheme with generous employer contribution
• Various schemes including Cycle to Work, Season Ticket Loans and help with the cost of Eyesight testing.
• Free parking

The post is based in Egham, Surrey where the College is situated in a beautiful, leafy campus near to Windsor Great Park and within commuting distance from London.

Informal enquiries can be made to Martin Albrecht at martin.albrecht@royalholloway.ac.uk

We particularly welcome applicants from backgrounds which are typically under-represented in cryptography. We are committed to enabling a healthy work-life balance.

Please quote the reference: 0819-315

Closing Date: Midnight, 12 September 2019

Interview Date: To be confirmed

PS: I have no idea why our HR department thinks “free parking” is a perk worth mentioning.