Multicore BKZ in FPLLL

There have been a few works recently that give FPLLL a hard time when considering parallelism on multicore systems. That is, they compare FPLLL’s single-core implementation against their multi-core implementations, which is fair enough. However, support for parallel enumeration has existed for a while in the form of fplll-extenum. Motivated by these works we merged that library into FPLLL itself a year ago. However, we didn’t document the multicore performance that this gives us. So here we go.

I ran

for t in 1 2 4 8; do
  ./compare.py -j  $(expr 28 / $t)  -t $t -s 512 -u 80 ./fplll/strategies/default.json
done

where compare.py is from the strategizer and default.json is from a PR against FPLLL. Note that these strategies were not optimised for multicore performance. I ran this on a system with two Intel(R) Xeon(R) CPU E5-2690 v4 @ 2.60GHz i.e. 28 cores. The resulting speed-ups are: multicore-bkz-in-fplll-default.png

As you can see, the speed-up is okay for two cores but diminishes as we throw more cores at the problem. I assume that this is partly due to block sizes being relatively small (for larger block sizes G6K – which scales rather well on multiple cores – will be faster). I also suspect that this is partly an artefact of not optimising for multiple cores, i.e. picking the trade-off between enumeration (multicore) and preprocessing (partly single-core due to LLL calls) right. If someone wants to step up and compute some strategies for multiple cores, that’d be neat.

Virtual FPLLL Days 6 aka Bounded Distance Development

The sixth FPLLL Days will be held on 19 and 20 November 2020. For obvious reasons they will be held online. (Who knows, we might end up liking the format enough to do more of these online in a post-COVID world, too).

As with previous incarnations of FPLLL Days, everyone who wishes to contribute to open-source lattice-reduction software is welcome to attend. In particular, you do not have to work on FPLLL or any of its sibling projects like FPyLLL or G6K. Work on whatever advances the state of the art or seems useful to you personally. That said, we do have the ambition to suggest projects from the universe of FPLLL and I personally hope that some people will dig in with me to do the sort of plumbing that keeps projects like these running. To give you an idea of what people worked on in the past, you can find the list of project of the previous FPLLL Days on the wiki and a report on the PROMETHEUS blog.

Format is yet to be determined. We are going to coordinate using Zulip. I think it would also be useful to have a brief conference call, roll call style, on the first day to break the ice and to make it easier for people to reach out to each other for help during the event. This is why we’re asking people to indicate their timezone on the Wiki. If you have ideas for making this event a success, please let us know.

PS: For the record: Joe threatened a riot if I didn’t call it “Bounded Distance Development”, so credit goes to him for the name.

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.

Continue reading “Postdoc at Royal Holloway on Lattice-based Cryptography”

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.

Continue reading “Postdoc at Royal Holloway on Lattice-based Cryptography”

Faster Enumeration-based Lattice Reduction

Our paper “Faster Enumeration-based Lattice Reduction: Root Hermite Factor k^{1/(2k)} in Time k^{k/8\, +\, o(k)}” – 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 k^{1/(2k)} in time k^{k/8 + o(k)} and polynomial memory. This improves on the previously best known enumeration-based algorithms which achieve the same quality, but in time k^{k/(2e) + o(k)}. A cost of k^{k/8 + o(k)} 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 k^{k/8 + o(k)} for the same root Hermite factor, based on the geometry of SDBKZ-reduced bases.

Continue reading “Faster Enumeration-based Lattice Reduction”

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.

Two Postdocs on Lattice-based Cryptography

I have two postdoc positions available to work on lattice-based or post-quantum cryptography with me and other people here in the ISG. Currently, five PhD students work on post-quantum or lattice-based cryptography in the ISG, as well as two postdocs. Furthermore, several more students, staff and postdocs work across the field of cryptography in general. We have regular reading groups, research seminars, visitors and decent travel funding. Beyond cryptography, the ISG works across the field of information security, e.g. smart card/embedded security, malware analysis and social or cultural aspects of security. I guess what I’m saying is: yes, Royal Holloway is in Brexit-land, but the ISG is a good place to work. If you have any informal queries, feel free to get in touch.

Location Egham
Salary £37,345 per annum – including London Allowance
Closing Date Friday 05 April 2019
Interview Date To be confirmed
Reference 0219-081

The postdoc will work alongside Dr. Martin Albrecht and other cryptographic researchers in the ISG on topics in lattice-based cryptography and related fields. One post is funded by a joint grant between Royal Holloway and Imperial College (Dr. Cong Ling) for bridging the gap between lattice-based cryptography and coding theory (starting date: 15 April or later). The second post is funded by an EPSRC grant on investigating the security of lattice-based and post-quantum cryptographic constructions (starting date: 1 June or later). Applicants with a strong background in all areas of cryptography are 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.

The ISG is one of the largest departments dedicated to information security in the world with 21 core academic staff in the department, as well as research and support staff. We work with many research partners in other departments and have circa 90 PhD students working on a wide range of security research, many of whom are fully funded through our Centre for Doctoral Training in Cyber Security. We have a strong, vibrant, embedded and successful multi-disciplinary research profile spanning from cryptography to systems security and social aspects of security. This vibrant environment incorporates visiting researchers, weekly research seminars, weekly reading groups, PhD seminars and mini conferences, the WISDOM group (Women in the Security Domain Or Mathematics) and we are proud of our collegial atmosphere and approach.

If you require any further information please email: recruitment@rhul.ac.uk. Informal enquiries can be made to Martin Albrecht at martin.albrecht@rhul.ac.uk.

  • Please quote the reference: 0219-081
  • Closing Date: Midnight, 5 April 2019
  • Interview Date: To be confirmed

Postdoc at Royal Holloway on Lattice-based Cryptography

I am 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 Kenny Paterson 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 £36,654 per annum – including London Allowance
Closing Date Monday 17 September 2018
Interview Date To be confirmed
Reference 0818-334

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

The PDRA will work alongside Dr. Martin Albrecht 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 and training and development opportunities. This is a full time fixed term 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.

To view further details of this post and to apply please visit https://jobs.royalholloway.ac.uk/vacancy.aspx?ref=0818-334. For queries on the application process the Human Resources Department can be contacted by email at: recruitment@rhul.ac.uk.

Please quote the reference: 0818-334

Closing Date: Midnight, 17th September 2018

Interview Date: To be confirmed

NTT Considered Harmful?

In a typical Ring-LWE-based public-key encryption scheme, Alice publishes

(a, b) = (a, a \cdot s + e) \in \mathbb{Z}_q[x]/(x^n+1)

(with n a power of two1) as the public key, where s, e are both “small” and secret. To encrypt, Bob computes

(c_{0}, c_{1}) = (v \cdot a + e', v \cdot b + e'' + \textnormal{Encode}(m))

where v, e', e'' are small, m is the message \in \{0,1\}^n and \textnormal{Encode}(\cdot) some encoding function, e.g. \sum_{i=0}^{n-1} \lfloor \frac{q}{2} \rfloor m_i x^i . To decrypt, Alice computes

c_{0} \cdot s - c_{1} = (v \cdot a + e')\cdot s - v \cdot (a\cdot s + e) + e'' + \textnormal{Encode}(m),

which is equal to e' \cdot s - v \cdot e + e'' + \textnormal{Encode}(m). Finally, Alice recovers m from the noisy encoding of m where e' \cdot s - v \cdot e + e'' is the noise. In the Module-LWE variant the elements essentially live in \left(\mathbb{Z}_q[x]/(x^n+1)\right)^k, e.g. a is not a polynomial but a vector of polynomials.

Thus, both encryption and decryption involve polynomial multiplication modulo x^n+1. Using schoolbook multiplication this costs \mathcal{O}(n^2) operations. However, when selecting parameters for Ring-LWE, we can choose q \equiv 1 \bmod 2n which permits to use an NTT to realise this multiplication (we require \equiv \bmod 2n to use the negacyclic NTT which has modular reductions modulo x^n+1 baked in). Then, using the NTT we can implement multiplication by

  1. evaluation (perform NTT),
  2. pointwise multiplication,
  3. interpolation (perform inverse NTT).

Steps (1) and (3) take \mathcal{O}(n \log n) operations by using specially chosen evaluation points (roots of one). Step (2) costs \mathcal{O}(n) operations.

This is trick is very popular. For example, many (but not all!) Ring-LWE based schemes submitted to the NIST PQC competition process use it, namely NewHope, LIMA (go LIMA!), LAC, KCL, HILA5, R.EMBLEM, Ding Key-Exchange, CRYSTALS-KYBER, CRYSTALS-DILITHIUM (sorry, if I forgot one). Note that since steps (1) and (3) are the expensive steps, it makes sense to remain in the NTT domain (i.e. after applying the NTT) and only to convert back at the very end. For example, it is faster for Alice to store s, e in NTT domain and, since the NTT maps uniform to uniform, to sample a in NTT domain directly, i.e. to just assume that a random vector a is already the output of an NTT on some other random vector.

This post is about two recent results I was involved in suggesting that this is not necessarily always the best choice (depending on your priorities.)

Warning: This is going to be one of those clickbait-y pieces where the article doesn’t live up to the promise in the headline. The NTT is fine. Some of my best friends use the NTT. In fact I’ve implemented and used the NTT myself.

Continue reading “NTT Considered Harmful?”

Fplll Days 3: July 6 – 14, Amsterdam

We’ll have an fplll coding sprint aka “FPLLL Days” in July. This time around, we plan a slightly modified format compared to previous instances. That is, in order to encourage new developers to get involved, we plan to have a 2 day tutorial session (shorter or longer depending on participants/interest) before the start of FPLLL Days proper.

Continue reading “Fplll Days 3: July 6 – 14, Amsterdam”