# 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 Veriﬁable, 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 $d$ (or, equivalently, a large number $m$ 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.

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

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

# 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:

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