UK Crypto Day (June 2023 Edition)

Together with Nick Spooner and Sarah Meikeljohn, I’m co-organising the next UK Crypto Day.¹

Date	23 June
Venue	King’s College London
Registration	Here
Programme	https://uk-crypto-day.github.io/2023/06/23/

We got some nice speakers/talks lined up:

Jonathan Bootle: The Sumcheck Protocol, Applications, and Formal Verification

The sumcheck protocol plays a central role in many constructions of efficient zero-knowledge arguments. In this talk, I will describe the sumcheck protocol, explain why it is so useful, and discuss recent work on a machine-checkable security proof.

Bio. Jonathan Bootle is a researcher in the Foundational Cryptography Group at IBM Research – Zurich. His research focuses on constructing efficient zero-knowledge proofs, especially those based on lattice assumptions or error-correcting codes.

Bernardo Magri: YOSO – You Only Speak Once

Imagine a setting where whenever a party in a protocol sends a message, its IP address becomes known, and it gets immediately killed by the adversary in a DoS attack. This implies that in any given protocol a party can only send a single message at a random point in time. Can we do secure multiparty computation in this setting? In this talk we introduce the YOSO MPC model that is based around the notion of roles, which are randomly assigned stateless parties that can send a single message for the entire duration of the protocol. We will show how one we can leverage the infrastructure of public blockchains to securely YOSO-compute any function with private inputs.

Bio. Bernardo Magri is a Senior Lecturer at the CS department at University of Machester. His research interests are on the theoretical and practical aspects of cryptography and distributed ledgers.

Sunoo Park: Email Attribution and Election Audits

My talk will focus on two recent works. The first concerns preventing the exploitation of stolen email data. Email is used widely for personal, industry, and government communication; as such, it is a valuable target for attack. Such attacks are compounded by email’s strong attributability: today, any attacker who gains access to your email can easily prove to others that the stolen messages are authentic. We define and construct non-attributable email using a new cryptographic signature primitive.

The second paper concerns a new model of post-election audits, loosely inspired by multi-prover interactive proofs. Post-election audits perform statistical hypothesis testing to confirm election outcomes. However, existing approaches are costly and laborious for close elections—often the most important cases to audit. We instead propose automated consistency checks, augmented by manual checks of only a small number of ballots. Our protocols scan each ballot twice, shuffling the ballots between scans: a “two-scan” approach inspired by two-prover proof systems.

Bio: Sunoo Park is a Postdoctoral Fellow at Columbia University and Visiting Fellow at Columbia Law School. Her research interests range across cryptography, security, and technology law. She received her Ph.D. in computer science at MIT, her J.D. at Harvard Law School, and her B.A. in computer science at the University of Cambridge.

Michele Ciampi: On the round-complexity of secure multi-party computation

In multi-party computation (MPC), multiple entities, each having some inputs want to jointly compute a function of these inputs with the guarantee that nothing aside from the output of the function will be leaked. In this talk, we are going to investigate how many messages the parties of an MPC need to exchange to securely realise any functionality with simulation-based security in the case where there is no setup and the majority of the parties can be corrupted. We will then consider a relaxation of the standard simulation-based paradigm, and discuss whether this lead to more efficient MPC protocols which still realize non-trivial functionalities which meaningful security.

Bio. Michele Ciampi is a Chancellor’s Fellow at the School of Informatics at the University of Edinburgh. His work focuses on theoretical aspects of cryptography, including multi-party computation protocols, zero-knowledge proofs, and blockchain.

François Dupressoir: Revisiting machine-checked AKE security — Reports from a possibly active trench

Machine-checked cryptographic proofs, as supported by tools such as EasyCrypt, CryptHOL or SSProve, aim at increasing trust in cryptographic algorithms by producing machine-checkable evidence that their security follows from relatively (sometimes) standard hardness assumptions. With only a few exceptions, their application has unfortunately been limited to small, typically non-interactive, constructions. A significant exception is a Eurocrypt 2015 paper applying EasyCrypt to a family of Authenticated Key Exchange protocols, whose massive proof has unfortunately been lost to time (and some obnoxious IT practices). This talk will report on an ongoing (or perhaps, hopefully, not) attempt at understanding better the interplay between EasyCrypt, interactive protocols, and a few competing pen-and-paper definition and proof methodologies. By doing so, I hope to provoke discussions around the goal and value of security proof and their machine-checked variants, and about what “traditional” cryptographers might expect or want from proof tools.

Bio. François Dupressoir is a Senior Lecturer at the University of Bristol, where he heads the Cryptography Research Group. His research revolves around bringing formal methods and formal reasoning techniques to cryptographic security of algorithms, protocols and their implementations.

Yixin Shen: Finding Many Collisions via Reusable Quantum Walks — Application to Lattice Sieving

Given a random function with domain and codomain , with , a collision of 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 , and matching algorithms are known for any value of . The situation becomes different when one is looking for multiple collision pairs. Here, for collisions, a query lower bound of was shown by Liu and Zhandry (EUROCRYPT 2019). A matching algorithm is known, but only for relatively small values of , 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 instead of the previous .

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.

Footnotes:

¹

Formerly, known as London-ish Crypto Day, but that produced a name clash with Liz’ London Crypto Day.

SandboxAQ Internships

You may or may not be aware that at SandboxAQ we have an internship residency programme. Residencies would typically be remote but can be on-site, they can take place year round and last between three to twelve months, full-time or part-time. To take part, you’d need to be a PhD student or postdoc somewhere.

In the interest of advertising our programme, here are two example ideas I’d be interested in.

Add SIS and (overstretched-)NTRU to the Lattice Estimator

The name “lattice estimator” at present is more aspirational than factual. In particular, we cover algorithms for solving LWE but not algorithms for solving SIS or (overstretched) NTRU. Well, we implicitly cover SIS because solving SIS implies solving LWE (and we cost that: the “dual attack”), we don’t have a nice interface to ask “how hard would this SIS instance be”. Adding this would be a nice contribution to the community, given how widely that estimator is used.

OPRFs from Lattices

Our first work on building OPRFs from lattices costs about 2MB of bandwidth if you ignore the zero-knowledge proofs and something like 128GB (yes, GB) if you count them. Since then, proving lattice statements has become a lot cheaper, so a natural project is to reconsider our construction: use newer/smaller proofs, tune the parameters, prove it in a nicer game-based model or in UC. To give you a taste of what is possible: This work building a non-interactive key-exchange (NIKE) has to solve essentially the same problem (noise drowning + ZK proofs) and achieves smaller parameters.

If you are interested, or have some other ideas, ping me and apply for a PQC resident position.

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.

Lecturer (≅ Assistant Professor/Juniorprofessor/Maître de conférences) in Cryptography at King’s College London

As you may or may not have heard, I will join the Department of Informatics at King’s College London from 2023. Specifically, I will join the Cybersecurity Group there with the aim to build a cryptography lab. As part of that plan, we are going to hire for four staff positions (three at the lecturer level, one at the senior lecturer level). The first of these is now on the market:

https://jobs.kcl.ac.uk/gb/en/job/054515/Lecturer-in-Cryptography

Note that the plan here is not to build an exclusive lattice-based cryptography, mathematical cryptography, post-quantum cryptography or a cryptanalysis lab, but our ambition is to build a lab with expertise across cryptography. I think this creates a fun and interesting research environment. So consider applying if you consider FSE, CHES, PKC, TCC or RWC your home venue or any other area of cryptography.

Normally, in this genre of blog posts I’d now go on talking about how amazing the department and everybody in it is but I’ve yet to start at KCL myself. However, everything I’ve seen so far makes me really quite optimistic, the department is strong and the people are nice.

The application deadline is somewhat far into the future (1 March 2023). So, if you like, there’s plenty of time to reach out to discuss or even to come visit us to check us out.

We’d appreciate any help in spreading the word. Happy to answer any questions I can answer or to direct to you to someone who can.

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.

A Fun Bug? Help Wanted!

Over at Low BDD Estimate · Issue #33 Ben reports a bug that, on first sight and unfortunately, does not stand out much. For some unusual parameters the Lattice Estimator reports wrong results. Given that we rely on a variety of heuristics to keep the running time down and given that the whole thing is mostly developed on the side, this is – again, unfortunately – not surprising.

Debugging “corner cases” can often do wonders to improve the robustness of a given piece of software. For example, back in the days when I worked a lot on M4RI, as much as I dreaded fixing bugs that only showed up on Solaris boxes, those bugs always revealed some shady assumptions in my code that were bound to produce problems elsewhere down the line.

Indeed, I think this bug puts the finger on the heuristics we rely upon and where they can go wrong. The parameter sets that Ben has in mind are quite unusual in that we have to pick quite a large dimension (or, equivalently, a large number of LWE samples) to make the target uniquely short. That is, I suspect fixing this bug would take a bit more than increasing the precision of some numerical computation here or there or to fix/add some if statement to account for a corner case. This makes bugs like these a high-ish priority.

On the other hand, truth be told, between this, the estimator being “mostly developed on the side” and all the other stuff I have to do, I doubt I’ll sink significant time into fixing this bug anytime soon.

But, and this is point of this post, perhaps someone would like to take this bug as an invitation to help to improve the Lattice Estimator? While, the estimator is quite widely relied upon to, well, estimate the difficulty of solving LWE and related problems, its bus factor is uncomfortably low. I’d say attempting to fix this bug would take whoever attempts to fix it on a whirlwind tour through the code base; a good way to learn it and to improve it.

Interested? Get in touch.

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).

Lecturer (≅ Assistant Professor/Juniorprofessor/Maître de conférences) in Computer Science (Quantum Computing)

Our colleagues in Computer Science (I am a computer scientist by training but I sit in the Department of Information Security aka the “Information Security Group”) are looking to hire a lecturer (roughly equivalent to assistant professor, Juniorprofessor or maître de conférences) with a focus on quantum algorithms. I’m reproducing the full ad below, but here’s why I think that’s rather exciting and you should apply if that’s your jam.

As you may know, several of us in the ISG work in the area of post-quantum cryptography, an area adjacent to quantum computing. To give some examples, Simon and co-authors showed that there are regimes where subexponential quantum attacks on SIDH exist; Eamonn, me and co-authors gave resource estimates for running quantum sieving attacks on lattice-based schemes; Carlos and co-authors gave polynomial-time quantum attacks (i.e. with superposition queries) against the CPA security of contracting Feistel structures; Chris discussed the impact of quantum computing on 5G; Fernando and co-authors gave resource estimates (and Q# code!) for breaking AES on a quantum computer; Eamonn and co-authors improved “low-memory” sieving in a quantum setting. We have a lively research community of PhD students, postdocs and staff. Speaking of PhD students, due to our CDT in Cyber Security of the Everyday, we are currently recruiting 10 students per year across the field of information security, including the “quantum threat”. Moreover, as mentioned in the ad, the College considers quantum a key priority. Some of our physicists work in various areas of quantum, some of our mathematicians work on quantum dynamics.

Feel free to reach out to me if you want to discuss what it is like working at Royal Holloway. For specifics about this post, reach out to Magnus (HoD of CS). Also feel encouraged to disseminate this ad through your networks.

32nd HP/HPE (Virtual) Colloquium On Information Security

We got some great speakers lined up for the 32nd HP/HPE (Virtual) Colloquium On Information Security on 16/17 December 2021. Details below.