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”

Open Letters v Surveillance

A letter, signed by 177 scientists and researchers working in the UK in the fields of information security and privacy, reads:

“Echoing the letter signed by 300 international leading researchers, we note that it is vital that, when we come out of the current crisis, we have not created a tool that enables data collection on the population, or on targeted sections of society, for surveillance. Thus, solutions which allow reconstructing invasive information about individuals must be fully justified.1 Such invasive information can include the ‘social graph’ of who someone has physically met over a period of time. With access to the social graph, a bad actor (state, private sector, or hacker) could spy on citizens’ real-world activities.”

Our letter2 stands in a tradition of similar letters and resolutions. For example, here is the “Copenhagen Resolution” of the International Association for Cryptologic Research (IACR), i.e. the professional body of cryptographers, from May 2014:

“The membership of the IACR repudiates mass surveillance and the undermining of cryptographic solutions and standards. Population-wide surveillance threatens democracy and human dignity. We call for expediting research and deployment of effective techniques to protect personal privacy against governmental and corporate overreach.”

Both of these documents, in line with similar documents, treat privacy and surveillance rather abstractly. On the one hand, this has merit: many of us, including myself, are experts on the technology and can speak to that with authority. Also, getting people working on privacy to agree that privacy is important is straight forward, getting them to agree on why is a much more difficult proposition. On the other hand, when we are making political interventions such as passing resolutions or writing open letters, I think we should also ask ourselves this question. I suspect we won’t all agree, but the added clarity might still be helpful.

Similar considerations have been voiced in several works before, e.g.

“The counter-surveillance movement is timely and deserves widespread support. However, as this article will argue and illustrate, raising the specter of an Orwellian system of mass surveillance, shifting the discussion to the technical domain, and couching that shift in economic terms undermine a political reading that would attend to the racial, gendered, classed, and colonial aspects of the surveillance programs. Our question is as follows: how can this specific discursive framing of counter-surveillance be re-politicized and broadened to enable a wider societal debate informed by the experiences of those subjected to targeted surveillance and associated state violence?” – Seda Gürses, Arun Kundnani & Joris Van Hoboken. Crypto and empire: the contradictions of counter-surveillance advocacy in Media, Culture & Society, 38(4), 576–590. 2016


“History teaches that extensive governmental surveillance becomes politicalin character. As civil-rights attorney Frank Donner and the Church Commission reports thoroughly document, domestic surveillance under U.S. FBI director J. Edgar Hoover served as a mechanism to protect the status quo and neutralize change movements. Very little of the FBI’s surveillance-related efforts were directed at law-enforcement: as the activities surveilled were rarely illegal, unwelcome behavior would result in sabotage, threats, blackmail, and inappropriate prosecutions, instead. For example, leveraging audio surveillance tapes, the FBI’s attempted to get Dr. Martin Luther King, Jr., to kill himself. U.S. universities were thoroughly infiltrated with informants: selected students, faculty, staff, and administrators would report to an extensive network of FBI handlers on anything political going on on campus. The surveillance of dissent became an institutional pillar for maintaining political order. The U.S. COINTELPRO program would run for more than 15 years, permanently reshaping the U.S. political landscape.” – Phillip Rogaway, The moral character of cryptographic work in Cryptology ePrint Archive. 2016

The pertinent question then is what surveillance is for. For an answer we have to look no further than GCHQ’s page about the Investigatory Powers Act 2016, which “predominantly governs” its mission:

“Before an interception warrant can be issued, the Secretary of State must believe that a warrant is necessary on certain, limited grounds, and that the interception is proportionate to what it seeks to achieve.

These grounds are that interception is necessary:

  • In the interests of national security; or
  • In the interests of the economic well-being of the UK; or
  • In support of the prevention or detection of serious crime” – GCHQ. Investigatory Powers Act. 2019

To unpack what this means in detail, we can recall how and when the means of surveillance have been deployed in recent history, by GCHQ and other departments of the British State. A programme that might cover all three aspects was GCHQ’s Tempora programme which tapped into fibre-optic cables for secret access to the world’s communications. Similarly, hacking the SIM manufacturer Gemalto would also cover all three. Spying on the German government is probably one for the economic well-being of the UK. Similarly, the London Metropolitan Police working with construction firms to blacklist trade unionists would fall into that category. UK intelligence services spying on Privacy International, police officers infiltrating Greenpeace and other activist groups, and databases of activists are plausibly done in the name of national security. The stop and search policy tackles, amongst other things, the serious crime of walking while black.

When we write that “solutions which allow reconstructing invasive information about individuals must be fully justified” it is worth to pay close attention to the justifications offered and to ask: justified to whom and by what standard.

Appendix: The letter in full

We, the undersigned, are scientists and researchers working in the UK in the fields of information security and privacy. We are concerned about plans by NHSX to deploy a contact tracing application. We urge that the health benefits of a digital solution be analysed in depth by specialists from all relevant academic disciplines, and sufficiently proven to be of value to justify the dangers involved.

A contact tracing application is a mobile phone application which records, using Bluetooth, the contacts between individuals, in order to detect a possible risk of infection. Such applications, by design, come with risks for privacy and medical confidentiality which can be mitigated more or less well, but not completely, depending on the approach taken in their design. We believe that any such application will only be used in the necessary numbers if it gives reason to be trusted by those being asked to install it.

It has been reported that NHSX is discussing an approach which records centrally the de-anonymised ID of someone who is infected and also the IDs of all those with whom the infected person has been in contact. This facility would enable (via mission creep) a form of surveillance. Echoing the letter signed by 300 international leading researchers, we note that it is vital that, when we come out of the current crisis, we have not created a tool that enables data collection on the population, or on targeted sections of society, for surveillance. Thus, solutions which allow reconstructing invasive information about individuals must be fully justified. Such invasive information can include the “social graph” of who someone has physically met over a period of time. With access to the social graph, a bad actor (state, private sector, or hacker) could spy on citizens’ real-world activities. We are particularly unnerved by a declaration that such a social graph is indeed aimed for by NHSX.

We understand that the current proposed design is intended to meet the requirements set out by the public health teams, but we have seen conflicting advice from different groups about how much data the public health teams need. We hold that the usual data protection principles should apply: collect the minimum data necessary to achieve the objective of the application. We hold it is vital that if you are to build the necessary trust in the application the level of data being collected is justified publicly by the public health teams demonstrating why this is truly necessary rather than simply the easiest way, or a “nice to have”, given the dangers involved and invasive nature of the technology.

We welcome the NHSX commitment to transparency, and in particular Matthew Gould’s commitment made to the Science & Technology committee on 28 April that the data protection impact assessment (DPIA) for the contact tracing application will be published. We are calling on NHSX to publish the DPIA immediately, rather than just before deployment, to enable (a) public debate about its implications and (b) public scrutiny of the security and privacy safeguards put in place.

We are also asking NHSX to, at a minimum, publicly commit that there will not be a database or databases, regardless of what controls are put in place, that would allow de-anonymization of users of its system, other than those self reporting as infected, to enable the data to be used for building, for example, social graphs.

Finally, we are asking NHSX how it plans to phase out the application after the pandemic has passed to prevent mission creep.



It is worth noting that this sentence does not, in fact, echo the international letter. Where the UK letter asks to justify such invasions, the international letter outright rejects them “without further discussion”. I think the international letter is better on this point.


I should note that I was involved in coordinating and drafting that letter and that I signed the “letter signed by 300 international leading researchers”.

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.

Continue reading “The Approximate GCD Problem”

Lecturer/Assistant Professor in Cryptography in the ISG

Unfortunately, recruitment for this post was stopped due to the uncertain financial position that UK universities are in at the moment.

The ISG is recruiting a lecturer (≡ assistant professor in the US system, ≡ Juniorprofessor in the German system, ≡ Maître de conférences in the French system; that’s all the systems I know). This is a full-time, permanent research and teaching position.

Look, I know this is England post-Brexit 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 lots of cryptography going on. As mentioned in the ad below, eight permanent members of staff, five postdocs and about 15 PhD students focus on or contribute to cryptographic research. As a corollary, we also have plenty of cryptographers coming through for visits and talks. We got a weekly cryptography reading group, our students have another one and our seminar regularly has cryptography talks.
  • 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 four 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. It is unlikely, though, that you will get to teach cryptography specifically.
  • 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 cryptographers there, aren’t too far away. London Crypto Day is a thing and so are the London-ish Lattice Coding & Crypto Meetings. Also, you get to live in London (or near Egham if that’s your thing, no judgement).

I’m happy to answer informal inquiries etc. We’d appreciate any help in spreading the word.

Continue reading “Lecturer/Assistant Professor in Cryptography in the ISG”

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 ISG/at Royal Holloway: currently, there are nine permanent members of staff working on cryptography: Simon Blackburn (Maths), Carlos Cid, Keith Martin, Sean Murphy, Siaw-Lynn Ng, Rachel Player, Liz Quaglia and me. In addition, there are five postdocs working on cryptography and roughly 15 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.

Note that most of these positions are reserved for UK residents, which does, however, not mean nationality (see CDT website for details) and there might also be some wiggle room for EU residents (yes, still!).

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

UDP Idle Scanning

We describe a (seemingly) new scanning technique for determining whether a UDP port is open without sending IP packets with the scanner’s IP to the target. It is a (UDP specific) variant of the TCP Idle Scan1 that was uncovered 20 years ago. It proceeds similarly to the TCP RST Ratelimit Scan2, but uses ICMP rate limiting as the side-channel. It only works for UDP protocols where we can solicit a reply.3 For a list of such protocols, see e.g. ZMap’s UDP Probe Module4 or NMap’s payloads5.


Consider three machines:

S : Scanner

Z : Zombie, we assume Z is sufficiently close to S to allow burst IP packets to arrive in, well, bursts. We also assume the zombie is running a Linux kernel with version at least v3.18-rc16 and with default options set. In particular, we assume icmp_msgs_burst = 50 (other small values are fine, too) and icmp_ratemask = 0x1818. We will make use of the Destination Unreachable bit being set.7

T : Target, we wish to check if the target is listening on $UDPPORT, speaking a protocol for which we can solicit a reply (e.g DNS, PCAnywhere, NetBios, SIP or anything speaking DTLS, see above).

The scan proceeds as follows:

  1. S(Z) -> T: 1 UDP packet to $UDPPORT at T, spoofed from Z’s IP address
  2. S -> Z: 49 UDP packets to a closed port from 49 different spoofed source IPs (to prevent per host ICMP rate limiting to kick in)
  3. T -> Z: If the target port is open then the target will respond to Z. Otherwise an ICMP Destination Unreachable message is sent from the target to the zombie.
  4. Z -> T: If a UDP response was generated, the zombie will respond with ICMP Destination Unreachable message to the target. Otherwise, nothing happens.
  5. S -> Z: 1 UDP probe to some closed port.
  6. Z -> S: If the zombie has exhausted its budget of 50 burst messages by responding to the target, the scanner will not receive a response. Otherwise, it will.

Note: A variant of this scan is to target icmp_msgs_per_sec which is 1000 by default.

Continue reading “UDP Idle Scanning”

17th IMA Conference on Cryptography and Coding

IMA-CC is a crypto and coding theory conference biennially held in the UK. It was previously held in Cirencester. So you might have heard of it as the “Cirncester” conference. However, it has been moved to Oxford, so calling it Cirencester now is a bit confusing. Anyway, it is happening again this year. IMA is a small but fine conference with the added perk of being right before Christmas. This is great because around that time of the year Oxford is a fairly Christmas-y place to be.

16 – 18 December 2019, St Anne’s College, University of Oxford

Continue reading “17th IMA Conference on Cryptography and Coding”

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 ( 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

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: Informal enquiries can be made to Martin Albrecht at

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

More on those 10 PhD Positions at Royal Holloway’s CDT in Cyber Security

My colleagues who work on the social/cultural side of (information) security together with colleagues from other departments have put together an outline for people who come from disciplines such as Human Geography, Sociology, Criminology, Law, Political Science, International Relations, Classics, Archaeology, Cultural Studies and Media Studies.

Fully Funded 4-year PhD Studentships at the EPSRC funded Royal Holloway Centre for Doctoral Training in Cyber Security for the Everyday

We are pleased to advertise positions for up to 10 PhD studentships to begin in September 2019 at the new Centre for Doctoral Training (CDT) in Cyber Security for the Everyday at Royal Holloway University of London.

We seek applications or informal expressions of interest from students and researchers with an interest in cyber security. In addition to Mathematics and Computer Science, relevant disciplines may include Human Geography, Sociology, Criminology, Law, Political Science, International Relations, Classics, Archaeology, Cultural Studies, Media Studies and more.

Building on two previous Centres for Doctoral Training in Cyber Security based at Royal Holloway, and anchored within the Information Security Group, the new CDT reflects the growth in and need for interdisciplinary research which critically engages with everyday cyber security questions. It does so by combining an understanding of technical systems with social science and humanities approaches to cyber security, personal information and growing datafication. In a broad sense, PhD projects will explore cyber security in the context of societal needs, critically evaluate the contribution cyber security makes to societal and individual securities and place discussions over the ethics, rights, responsibility and fairness of cyber security at the centre rather than at the periphery. Other academic departments involved in the Centre include Computer Science, Geography, Law, Psychology and Politics and IR.

Whilst broad in scope, the CDT is driven by two overarching strands of enquiry:

  • The technologies deployed in digital systems that people use, sometimes inadvertently, every day; and
  • Everyday societal experiences of cyber security, including how different societies, communities, groups and individuals conceptualise, materialise, negotiate, and respond to increasingly digitally mediated and technologically driven worlds

A central aspect of the CDT programme is interdisciplinary collaborations as students work on shared projects and other collaborative activities within their PhD cohort. This is encouraged throughout their studies but a key component of the first year, which is devoted to training activities and individual and group projects. Students may not have established project ideas at the time of recruitment but develop these during the first year.

The core strategic objectives of the CDT in Cyber Security for the Everyday are:

  1. To develop cohorts of truly multi-disciplinary researchers, with a broad understanding of cyber security and a strong appreciation of the interplay between technical and social questions;
  2. To promote research in cyber security that is original, significant, responsible, of international excellence and responsive to societal needs; and
  3. To engage with stakeholders in the cyber security community and wider society

We are keen to encourage applications from across the Social Sciences and Humanities. Potential areas of interdisciplinary study include but are not limited to:


  • The arts and critical discourses of cyber security
  • Agenda-setting, framing and cyber security
  • Feminist cyber security
  • Social difference, intersectionality and cyber security
  • Intimate spaces of cyber security (including the body, home, etc.)
  • Everyday/routine violences and cyber security
  • Solidarity and resistance and alternative forms of cyber security
  • Narratives of security
  • Ontological security across disciplines and forms of expression


  • Contemporary archaeologies of cyber security
  • Cyber security and the city
  • The materiality of digital mediation in cyber security
  • Media as data
  • Resistance through data, memes/gifs/films
  • Simulation and simulated affect -emotional security data  & machines


  • Sustainable development goals and cyber security
  • The impact of cyber security and public policy
  • Territory, diplomacy and cyber security
  • Regional and international cyber security
  • Transnational and global governance of cyber security
  • Cyber security of democratic institutions
  • Cybersecurity at work
  • Organisational approaches to and processes of cybersecurity
  • Cybersecurity profession and professionals
  • E-surveillance at work


  • Mobilities, automated and autonomous mobility systems
  • Resistance, dissent and cyber security
  • Hate crimes and affect
  • Cultural economies, crypto-currencies and piracy
  • The dark web, visibility and invisibility
  • Practices of data hacking in media consumption.