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.

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

10 PhD Positions at Royal Holloway’s Centre for Doctoral Training in Cyber Security for the Everyday

At Royal Holloway we are again taking applications for ten fully-funded PhD positions in Information Security. See the CDT website and the ISG website for what kind of research we do. Also, check out our past and current CDT students and our research seminar schedule to get an idea of how broad and diverse the areas of information security are in which the ISG works.

More narrowly, to give you some idea of cryptographic research (and thus supervision capacity) in the Cryptography Group at Royal Holloway: currently, we are nine permanent members of staff: Simon Blackburn (Maths), Saqib A. Kakvi, Keith Martin, Sean Murphy, Siaw-Lynn Ng, Rachel Player, Liz Quaglia and me. In addition, there are three postdocs working on cryptography and roughly 14 PhD students. Focus areas of cryptographic research currently are: lattice-based cryptography and applications, post-quantum cryptography, symmetric cryptography, statistics, access control, information-theoretic security and protocols.

To give you a better sense of what is possible, here are some example projects. These are in no way prescriptive and serve to give some ideas:

  1. I am, as always, interested in exploring lattice-based and post-quantum cryptography; algorithms for solving the hard underlying protocols, efficient implementations, lifting pre-quantum constructions to the post-quantum era.
  2. Together with my colleague Rikke Jensen, we want to explore security needs and practices in large-scale protests using ethnographic methods. We’ve done an interview-based (i.e. not ethnography-based) pilot with protesters in Hong Kong and think grounding cryptographic security notions in the needs, erm, on the ground, will prove rather fruitful.
  3. My colleague Rachel Player is looking at privacy-preserving outsourced computation, with a focus on (fully) homomorphic encryption.
  4. My (new) colleague Guido Schmitz uses formal methods to study cryptographic protocols.

Note that most of these positions are reserved for UK residents, which does, however, not mean nationality (see CDT website for details) and we can award three of our scholarships without any such constraint, i.e. international applicants. The studentship includes tuition fees and maintenance (£21,285 for each academic year).

To apply, go here. Feel free to get in touch if you have questions about whether this is right for you. Official announcement follows.

Continue reading “10 PhD Positions at Royal Holloway’s Centre for Doctoral Training in Cyber Security for the Everyday”

We’re hiring!

The ISG is recruiting two lecturers (≡ assistant professor in the US system/Juniorprofessor in Germany/Maître de conférences in France). These are full-time, permanent research and teaching positions.

Let me give you a personal pitch of why you should apply:

  • It’s a big group. We got 23 permanent members of staff working across the field of information security: cryptography, systems and social foundations. Check out our seminar programme and our publications to get a sense of what is going on in the group.
  • More specific perhaps to this audience: We have a big cryptography group with 9 permanent members of staff, several postdocs and many PhD students. Check out our website, publications and our joint seminar series with ENS Lyon and CWI Amsterdam to get a sense.
  • It’s a group with a good mix of areas and lots of interaction. UK universities don’t work like German ones where professors have their little empires which don’t interact all that much. Rather, the hierarchies are pretty flat within a department (everybody is line managed by the Head of Department, Chris Mitchell, who is great) which facilitates more interaction; at least within the ISG that’s true. For example, I doubt the sort of collaboration that led to our HK paper would have come about if we didn’t attend the same meetings, taught the same modules, went to lunch and the pub together etc. Interdisciplinarity from above is annoying, when it emerges spontaneously it can be great.
  • It’s a nice group. People are genuinely friendly and we help each other out. It will be easy to find someone to proof read your grant applications or share previously successfully funded ones etc. I don’t know any official numbers but the unionisation level seems to be relatively high, which I also take as an indication that people don’t adopt a “everyone for themselves” approach.
  • We got funding for our Centre for Doctoral Training for the next few years (then we have to reapply). This means 10 PhD positions per year. Also, our CDT attracts strong students. My research career really took off after getting a chance to work with our amazing students.
  • The ISG is its own department (in a school with Physics, EE, Mathematics and Computer Science). All of our teaching is on information security with a focus on our Information Security MSc (which is huge). So you’ll get to teach information security.
  • The ISG has strong industry links. Thus, if that’s your cup of tea, it will be easy to get introductions etc. A side effect of these strong links is that consulting opportunities tend to pop up. Consulting is not only permitted by the employer but encouraged (they take a cut if you do it through them).
  • The ISG is a large group but Royal Holloway is a relatively small university. That means getting things done by speaking to the person in charge is often possible, i.e. it’s not some massive bureaucracy and exceptions can be negotiated.
  • It’s within one standard deviation from London. This means UCL and Surrey, and thus the researchers there, aren’t too far away. Also, you get to live in London (or near Egham if that’s your thing, no judgement).

We’d appreciate any help in spreading the word. Happy to answer questions, just get in touch.

Continue reading “We’re hiring!”

Collective Information Security in Large-Scale Urban Protests: the Case of Hong Kong

Our work – with Jorge Blasco, Rikke Bjerg Jensen and Lenka Mareková – on the use of digital communication technologies in large-scale protests in Hong Kong was accepted at USENIX ’21. A pre-print is available on arXiv. Here’s the abstract:

The Anti-Extradition Law Amendment Bill protests in Hong Kong present a rich context for exploring information security practices among protesters due to their large-scale urban setting and highly digitalised nature. We conducted in-depth, semi-structured interviews with 11 participants of these protests. Research findings reveal how protesters favoured Telegram and relied on its security for internal communication and organisation of on-the-ground collective action; were organised in small private groups and large public groups to enable collective action; adopted tactics and technologies that enable pseudonymity; and developed a variety of strategies to detect compromises and to achieve forms of forward secrecy and post-compromise security when group members were (presumed) arrested. We further show how group administrators had assumed the roles of leaders in these ‘leaderless’ protests and were critical to collective protest efforts.

Our work can be seen in the tradition of “Can Johnny Build a Protocol? Co-ordinating developer and user intentions for privacy-enhanced secure messaging protocols” which documented the divergence of what higher-risk users – such as those in conflict with the authorities of a nation state – need and want and what secure messaging developers design for. This divergence is noteworthy because “human-rights activists” are a common point of reference in discussions around secure messaging.

However, our focus is not activists but participants in large-scale protests, i.e. our focus is more closely tied to specific needs in moments of heightened conflict, confrontation and mass mobilisation. In particular, we interviewed people who were in some shape or form involved in the Anti-ELAB protests in Hong Kong in 2019/2020. Several of our participants described themselves as “frontliners” which roughly means they were present in areas where direct confrontations with law enforcement took place.

As the title suggests our data speaks to how security needs and practices in this population are collective in nature: how decisions about security are made, what security features are deemed important, how people learn to understand security technologies. As an example take post-compromise security and forward secrecy:

Continue reading “Collective Information Security in Large-Scale Urban Protests: the Case of Hong Kong”

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.

Continue reading “Round-optimal Verifiable Oblivious Pseudorandom Functions from Ideal Lattices”

Reader/Senior Lecturer/Associate Professor in the ISG

The ISG is recruiting a senior lecturer/reader (≡ associate professor in the US system). This is a full-time, permanent research and teaching position.

Look, I know this is post-Brexit England but let me give you a personal pitch of why you should apply:

  • It’s a big group. We got ~20 permanent members of staff working across the field of information security: cryptography, systems and social. Check out our seminar programme and our publications to get a sense of what is going on in the group.
  • It’s a group with a good mix of areas and lots of interaction. UK universities don’t work like German ones where professors have their little empires which don’t interact all too much. Rather, the hierarchies are pretty flat within a department (everybody is line managed by the Head of Department) which facilitates more interaction; at least within the ISG that’s true. For example, I’m currently working on a project with someone from the systems and software security lab and one of our social scientists. I doubt this sort of collaboration would have come about if we didn’t attend the same meetings, taught the same modules, went to lunch and the pub together etc. Interdisciplinarity from above is annoying, when it emerges spontaneously it can be great.
  • It’s a nice group. People are genuinely friendly and we help each other out. It will be easy to find someone to proof read your grant applications or share previously successfully funded ones etc. I don’t know any official numbers but the unionisation level seems to be relatively high, which I also take as an indication that people don’t adopt a “everyone for themselves” approach.
  • We got funding for our Centre for Doctoral Training for the next few years (then we have to reapply). This means 10 PhD positions per year. Also, our CDT attracts strong students. My research career really took off after getting a chance to work with our amazing students.
  • The ISG is its own department (in a school with Physics, EE, Mathematics and Computer Science). All of our teaching is on information security with a focus on our Information Security MSc (which is huge). So you’ll get to teach information security.
  • The ISG has strong industry links. Thus, if that’s your cup of tea, it will be easy to get introductions etc. A side effect of these strong links is that consulting opportunities tend to pop up. Consulting is not only permitted by the employer but encouraged (they take a cut if you do it through them).
  • The ISG is a large group but Royal Holloway is a relatively small university. That means getting things done by speaking to the person in charge is often possible, i.e. it’s not some massive bureaucracy and exceptions can be negotiated.
  • It’s within one standard deviation from London. This means UCL and Surrey, and thus the researchers there, aren’t too far away. Also, you get to live in London (or near Egham if that’s your thing, no judgement).

We’d appreciate any help in spreading the word. Happy to answer any questions I can answer.

The ad says “senior lecturer” but, speaking for myself, I’d recommend to apply even if you’re going for the lecturer/assistant professor/Juniorprofessor stage in your career. Also, I’d encourage people from all areas of information security to apply.

Continue reading “Reader/Senior Lecturer/Associate Professor in the ISG”

On BDD with Predicate: Breaking the “Lattice Barrier” for the Hidden Number Problem

Nadia and I put our pre-print and our source code online for solving bounded distance decoding when augmented with some predicate f(\cdot) that evaluates to true on the target and false (almost) everywhere else. Here’s the abstract:

Lattice-based algorithms in cryptanalysis often search for a target vector satisfying integer linear constraints as a shortest or closest vector in some lattice. In this work, we observe that these formulations may discard non-linear information from the underlying application that can be used to distinguish the target vector even when it is far from being uniquely close or short.

We formalize lattice problems augmented with a predicate distinguishing a target vector and give algorithms for solving instances of these problems. We apply our techniques to lattice-based approaches for solving the Hidden Number Problem, a popular technique for recovering secret DSA or ECDSA keys in side-channel attacks, and demonstrate that our algorithms succeed in recovering the signing key for instances that were previously believed to be unsolvable using lattice approaches. We carried out extensive experiments using our estimation and solving framework, which we also make available with this work.

Continue reading “On BDD with Predicate: Breaking the “Lattice Barrier” for the Hidden Number Problem”

The 31st HP/HPE (Virtual) Colloquium on Information Security

This year, my colleague Rikke Jensen and I took over coordinating “HP/HPE Day”, our department’s annual flagship event. It will take place as a virtual event this year, which allows us to invite a bit more broadly than we usually do. Registration is free but mandatory – tickets will be allocated on a first come, first served basis.

Continue reading “The 31st HP/HPE (Virtual) Colloquium on Information Security”