malb::blog

Our work – “At-Compromise Security: The Case for Alert Blindness” – was accepted at EUROCRYPT 2026; with “us” being Simone Colombo, Benjamin Dowling, Rikke Bjerg Jensen and, well, me.

Abstract. We start from the observation in prior work that cryptography broadly intuits security goals – as modelled in games or ideal functionalities – while claiming realism. This stands in contrast to cryptography’s attentive approach towards examining assumptions and constructions through cryptanalysis and reductions. To close this gap, we introduce a technique for determining security goals. Given that games and ideal functionalities model specific social relations between various honest and adversarial parties, our methodology is ethnography: a careful social science methodology for studying social relations in their contexts. As a first application of this technique, i.e. ethnography in cryptography, we study security at-compromise (neither pre- nor post-) and introduce the security goal of alert blindness. Specifically, in our 2024/2025 six-and-a-half-month ethnographic fieldwork with protesters in Kenya, we observed that alert blindness captures a security goal of abducted persons who were taken by Kenyan security forces for their presumed activism. We show this notion is achievable under standard assumptions by providing a construction secure in our model. We discussed both the notion and the construction with some interlocutors in Kenya.

As can be gleaned from the abstract, our work does two things. First, we introduce to cryptography a technique for establishing security goals (ethnography) that we then (as cryptographers) formalise in games or ideal functionalities. This starts from the observation that these security goals are typically intuited in cryptographic works yet, at the same time, claim realism. This is also the starting point of our project Social Foundations of Cryptography and you can find introductory ethnography-focused and cryptography-focused posts on our website. A notable and integral component of our work is that we did not validate some security notion after we came up with it, but rather that it emerged from our data. In other words, we (i.e. Rikke) did not go to Kenya to study at-compromise security but this focus emerged from the fieldwork.

Second, we study at-compromise security, i.e. security during a ‘compromise’, here an abduction by Kenyan President William Ruto’s security forces. That is, our data reveals how protection during such an abduction was a major concern during the 2024 Anti-Finance Bill protests in Kenya. In particular, several surviving targets of such abductions attribute their survival to their ability to inform others about being taken. Public calls for their release eventually led their abductors to let them go. Our data also revealed that the reason for these abductions at that time1 was intelligence gathering about these unprecedented protests. Our security notion ‘exploits’ this adversarial goal to establish a covert channel to a remote server to raise the alarm, i.e. to realise the security goal of many of those targeted for abduction. However, given the brutality of these abductions, it was paramount that the abductors did not discover this act of defiance of their targets before protective mechanisms, such as those public calls for their release, could be deployed. That is, we want the alert to be blind. A consequence of this blindness requirement is that the cooperating server which registers the alarm will unconditionally return the correct decryption key: we surrender confidentiality to realise alert blindness. This – perhaps – counter-intuitive decision is well-justified from our data, and we consider this justification as a central contribution of this work.

We will also present our work at RWC 2026 and we are organising an autumn school on the social foundations of cryptography.

The Kenyan security forces have since changed their approach and now also target people for abductions with the apparent intent of terrorising them. Our work does not address this new threat.

We‘re hosting an Autumn School in London, UK, from 15 to 17 September 2026, to bring together ethnographers and cryptographers to discuss ways in which the two fields can be meaningfully brought into conversation.

This is also the premise of our Social Foundations of Cryptography project: to ground cryptography in ethnography. Here, we rely on ethnographic methods, rather than our intuition, to surface security notions that we then formalise and sometimes realise using cryptography.

Our intention is to ‘flip’ the typical relationship between the computer and social sciences, where the latter has traditionally ended up in a service role to the former. Rather, we want to put cryptography at the mercy of ethnography.

But how do we do this? How do we as cryptographers interact with and make sense of ethnographic field data? How can we refine, improve or extend this interaction? What obstacles do we face when we make cryptography rely on ethnographic data which is inherently ‘messy’? How do we handle that cryptographic notions tend to require some form of generalisation but ethnographic findings can only be particular?

How do ethnographers retain the richness of ethnographic field data in conversations with cryptographic work? Indeed, our project has already highlighted some limitations of our approach. It has brought to the fore concrete challenges in ‘letting the ethnographic data speak’ while still making it speak to cryptography.

The Autumn School is an opportunity to explore these questions jointly across ethnography and cryptography, through a series of talks, group discussions and activities.

We say a bit more about the programme and registration for the Autumn School here.

We are looking to recruit a lecturer in cryptography at King’s College London to work with us within the cybersecurity group:

https://www.kcl.ac.uk/jobs/134305-lecturer-in-cryptography

I think it’s fair to say we got strong expertise in lattice-based and post-quantum cryptography here, as well as in protocols with an applied cryptography bent. Check out our publications to get a better picture. For this position, we do not aim to strengthen lattices further, but rather aim to strengthen other areas of cryptography, e.g. protocols, applied cryptography, cryptography in the wild or theory.

The application deadline is somewhat far into the future (5 March 2026). So, if you like, there’s 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.

Job id: 134305.
Salary: £53,947 – £63,350 per annum, including London Weighting Allowance.
Posted: 17 December 2025.
Closing date: 05 March 2026.
Business unit: Natural, Mathematical & Engineering Sci. Department: Informatics.
Contact details: Martin Albrecht. martin.albrecht@kcl.ac.uk
Location: Strand Campus.
Category: Academic & Teaching.

[snip]

We welcome applications from candidates who have an international profile in research in any area of cryptography. Areas of research expertise of particular interest include protocols, applied cryptography, cryptography in the wild or theoretical cryptography. Lattice-based cryptography is not an area of interest for this position.

We consider cryptographic challenges from a broad perspective. Members of the department regularly publish in and sit on the program committees of top-tier and well-known venues in cryptography and information security. It is the research transformative aspect that provides the opportunity to serve society while supporting King’s as an outstanding institution in science and technology. The Department has strong links with industry, who engage with us in collaborative research projects.

See our list of publications and our people in cryptography for more details or reach out to us to find out if this environment might be a good fit for you.

[snip]

Eamonn and I are looking to hire an intern for four months to work on the Lattice Estimator. The internship will be based at King’s College London and is funded by a gift from Zama. We are ideally looking for someone in a PhD programme also working on lattice cryptanalysis who is happy to interrupt their studies for a few months to help us improve the estimator. We’re offering a salary of roughly £4,400 per month before tax.(*)

This would involve reviewing and closing tickets, reviewing the literature for what is currently missing from the estimator to add it and reviewing the code already there for correctness.

If you’re interested, please get in touch with Eamonn Postlethwaite <eamonn.postlethwaite@kcl.ac.uk> and me Martin R. Albrecht <martin.albrecht@kcl.ac.uk> to discuss this position. We are somewhat flexible on timing.

(*) I am writing “roughly” here because internships are not a common thing at King’s College London. In particular, the position would formally be through the King’s Talent Bank and crunching the numbers, the monthly salary ends up being roughly the figure stated above.

We are recruiting a postdoc to work with us on “practical advanced post-quantum cryptography from lattices”, the title of my ERC selected, UKRI Frontier Research funded project:

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.

So when I say “advanced”, I don’t mean Functional Encryption or Indistinguishability Obfuscation, but OPRFs, Blind Signatures, Updatable Public-Key Encryption, even NIKE (sadly!).

I’m quite flexible on what background applicants bring to the table

• Do you like breaking newfangled (and not so newfangled) lattice assumptions?
• Do you like to build constructions from those assumptions?
• Do you like to reduce lattice problems to each other?
• Do you think we can apply tricks from iO or FE to less fancy protocols?

All of that is in scope. If in doubt, drop me an e-mail and we can discuss.

Here is some key data of the position:

As mentioned in the job ad, the postdoc will sit in the Cryptography Lab at King’s (which itself is part of the Cybersecurity Group). Currently, the cryptography lab are:

• Benjamin Dowling
• Ngoc Khanh Nguyen
• Eamonn Postlethwaite
• Joël Felderhoff
• Simone Colombo
• Filip Trenkic
• George O’Rourke
• Jan Niklas Siemer
• Sasha Lapiha
• Shubham Pawar

I’d appreciate if you could help me to spread the word to people who might be a good fit for this position. Any questions, drop me an e-mail.

Apply here.

Our paper – titled “On the Virtues of Information Security in the UK Climate Movement” – was accepted at USENIX Security’25. Here’s the abstract:

We report on an ethnographic study with members of the climate movement in the United Kingdom (UK). We conducted participant observation and interviews at protests and in various activist settings. Reporting on the findings as they relate to information security, we show that members of the UK climate movement wrestled with (i) a fundamental tension between openness and secrecy; (ii) tensions between autonomy and collective interdependence in information-security decision-making; (iii) conflicting activist ideals that shape security discourses; and (iv) pressures from different social gazes – from each other, from people outside the movement and from their adversaries. Overall, our findings shed light on the social complexities of information-security research in activist settings and provoke methodological questions about programmes that aim to design for activists.

Here, “we” is Mikaela Brough, Rikke Bjerg Jensen and me. Mik is doing a PhD (with Rikke and me) on how members of environmental social movements navigate their information security. She is an ethnographer and her previous degree was in social anthropology. Rikke is a professor in the Information Security Group at Royal Holloway, University of London. She also is an ethnographer and heads up the Ethnography Group there.

If you are one of the handful of people who actually read this blog (hi!), you might wonder what the heck I did on that paper: I am a cryptographer but this paper is neither cryptography nor in a closely related field. Rather, it is a social science paper throwing up methodological questions about social science (granted, in the field of information security). Thus, it makes immediate sense that two trained and qualified social scientists – Mik and Rikke – would write such a paper; me, not so much.

Indeed, this work – for good reason – breaks from the cryptographic and mathematical convention of naming authors in alphabetical order. The AMS explains this mathematical convention as follows (I’ll return to this below):

“In most areas of mathematics, joint research is a sharing of ideas and skills that cannot be attributed to the individuals separately. The roles of researchers are seldom differentiated (in the way they are in laboratory sciences, for example). Determining which person contributed which ideas is often meaningless because the ideas grow from complex discussions among all partners. Naming a ‘senior’ researcher may indicate the relative status of the participants, but its purpose is not to indicate the relative merit of the contributions. Joint work in mathematics almost always involves a small number of researchers contributing equally to a research project. For this reason, mathematicians traditionally list authors on joint papers in alphabetical order.” — AMS Statement on The Culture of Research and Scholarship in Mathematics: Joint Research and Its Publication

Now, ethnography is a method that is mostly known for being slow, long, expensive, extensive and immersive. Ethnography insists on “fieldwork” which literally means to do a lot of work in the field. In particular, researchers spend extended periods of time (think months) with the groups they study. As such, this method is particularly well-suited for settings where you have to expect that the answers people give might differ from their lived experience. This might be because they hardly step back to reflect on this lived experience or this might be because those questions are loaded for some reason. Information security is certainly a loaded question, touching on people’s self-images about whether they’re “qualified” to have an opinion, for example. You will find this reported in many prior qualitative studies in information security where many participants actually were themselves security trainers or at least attended security trainings; but it is the people who think “information security is not for me” who we might want to reach and understand.

This part of the research, the work in the field or the “data gathering”, was done by Mik, the fieldworker in this project. Hence, Mik is listed as the first author.

If you opened our paper, you’ll also find a “positionality statement” (the first one I have ever written): who we are, how we are perceived and what are some general outlooks we have. Such statements are necessary in this line of work because the fieldworker’s data will be shaped by how the participants read them. This doesn’t mean the data is biased or wrong but it is particular: some people will open up to you if they read you a certain way, others only if they read you in a different way. Similarly, some stuff will catch your attention, some stuff will not. We cannot really speak of “bias” here because there is no neutral ground truth to fall back to, every study will be shaped by the fieldworker and the job of the analysis is also to account for this. 1

After the fieldwork come several analysis cycles. First, only by the fieldworker to produce some synthesis of the data to discuss with the rest of the research team; well, in our case, because most ethnographic studies, in contrast, have a research team of size one. For example, for methodological and ethical reasons, I never saw any raw data from Mik’s fieldwork. In some sense, I could only interact with Mik as an oracle who may or may not have an answer to my queries about the data. In any case, in a multi-stage process (Rikke and Mik did coding first, I got involved in a later stage of the analysis), we eventually transitioned to collective analysis, where the three of us would discuss Mik’s initial findings, interrogate them, iterate over them, have ideas how to code/group them and see how they might relate to information security. This process took several months and could take the form of someone suggesting “I think the data suggests that X” to then later hear “sorry, the data does not actually suggest this, rather Y”, etc. Thus, this part of the analysis was quite interactive with us discussing the data and tentative findings. An example of what this sort of process might throw up is our finding regarding autonomy and necessity in the paper. In our discussions we noticed this tension, Mik went back through the data to see if there was more on this “theme” and we then refined our understanding of this tension.

Thus, this part of the research, the analysis, is closer to the culture the AMS described in the quote above. I could not attribute several findings to Mik, Rikke or me individually, because here too “which person contributed which ideas is often meaningless because the ideas gr[e]w from complex discussions among all partners.”

This is what is meant by “reflexivity” in the paper. In a more positivist strand of qualitative social science research, the authors would instead aim for what is called “inter-coder reliability”. This is based on the idea that if several people draw the same conclusion from the same data, this conclusion is not shaped (so strongly) by their subjectivity. This, on the one hand, will only be of limited success because of the selection of who looks at this data and with what questions in mind. On the other hand, and this is the point I’m going for here, it limits what you can get from the data. Us discussing these findings over many weeks produced our findings, including the one that produced our title, i.e. that in this setting “security” served as the material to express your activist virtues which trumped operational security concerns.

An illustration of this iterative process is how the focus shifted as we went on. The initial plan here was for my involvement to be similar as it was in “Collective Information Security in Large-Scale Urban Protests: the Case of Hong Kong”. There, Rikke had conducted interviews with participants of the Anti-ELAB protests of 2019 and our discussion contrasted our findings with established security notions also in cryptography, such as forward secrecy and post-compromise security. Thus, when Mik, Rikke and I set out to collaborate on the analysis here, we had something like this in mind. As indicated above, it did not play out this way and the data lead us to discuss rather different questions in the end.

In some sense, this “reflexivity” resembles more the approach taken in mathematics and cryptography than “inter-coder reliability” would. After all, we routinely discuss and co-write the proofs for our theorems and do not maintain the standpoint: if two people arrive at the same proof, it will be correct. Rather, we criticise each other’s mistake and fix them to arrive at hopefully a correct proof within the research team.

Overall, and that’s a point we also make in the paper, ethnography is not merely a different data gathering method but also requires a different analytical approach to account for the data gathered. The data will be richer than with other methods but it will also be more particular.

Put in our jargon, ethnography is an approach to establish ∃ statements but it will not tell you ∀. I’d claim we often want the former in information security research: “What does security mean in this context and how does that relate to our established notions?” “What are the threats?” “What are the security goals?” We can argue about how these findings generalise after, but first we should establish what it is that may or may not generalise.

Using a finding from our paper, we found that those we – information security researchers – would typically interview about the security practices of a particular group under study – i.e. those who would self-select to respond to us – were in a somewhat entrenched conflict with other members of their movement over being a good activist. Thus, if we interview this particular set of people from a particular population, we are prone to end up with ideas for design that might end up being rejected outright by others. We can say this with some confidence about some parts of the UK climate movement and I suspect a similar dynamic can be observed elsewhere, but our data does not speak to this. What we can say, though, is that it is worth finding out.

This also partially explains why the positionality statement in our paper covers also Rikke and me, and not just Mik. For Rikke and me, it’s not so important how we’re read – we didn’t do the fieldwork – but it matters to inform the reader what catches our attention, how we looked at the data and what we would consider worthwhile pulling out. This is important because of the second piece of the puzzle: we cannot publish the actual underlying data: we would never get ethics approval for this, nor would we want to. As a consequence, the reader needs to rely more on us than in, say, cryptography, where we can usually publish our underlying data if there is some.

Together with Rikke Jensen, we’re organising a talk and discussion with Jean-François Blanchette in London on his book Burdens of Proof, which has been tremendously influential on our thinking around the social foundations of cryptography.

Yeah yeah yeah he has a thing about steganography: Mathematical formalism, disciplinary boundaries, and cryptography’s design culture

https://x.com/martinralbrecht/status/1793640473841881452

What does it take for cryptographic protocols to become credible outside the narrow world of mathematical proofs? In Burdens of Proof (MIT Press, 2012), I examined this question in the early 2000s, as cryptography began to move into legal, bureaucratic, and professional domains. Drawing on fieldwork during the reform of the French Civil Code and its aftermath, the book traced how digital signatures were translated into legal and institutional practice—not through seamless adoption, but through negotiation, reinterpretation, and friction. It argued that mathematical guarantees alone were never enough: to function in the world, cryptographic systems had to be made intelligible, authoritative, and usable within existing structures of trust and responsibility.

This talk revisits the book through the lens of what the field itself historically sidelined as it sought great institutional credibility and social relevance. Steganography, the art of hiding in plain sight, plays a central role here—not only as a technique excluded from the modern cryptographic canon, but as a pointer to everything cryptography has tended to avoid: context, embodiment, ambiguity, and the materiality of technical systems. Paying close attention to has been excluded and avoided, we can better understand the contradictions, assumptions, and imaginaries built into cryptography’s design culture.

Jean-François Blanchette serves as director of the Responsible Data Governance program at the École nationale des sciences de l’information et des bibliothèques in Lyon, France, and is Research Professor Emeritus in the Department of Information Studies at UCLA. He is currently writing about the future of personal digital collections in the age of streaming media.

Royal Holloway (Central London Campus)
Room 1-01
11 Bedford Square
London WC1B 3RE
https://maps.app.goo.gl/U8yyTBgbHtsnoU5Z6

Tuesday, 10 June, 2pm to 4pm

Registration is not necessary but we’d appreciate if you could let us know if you’re planning to attend, so we can get a sense of numbers to expect.

Together with Lenka Mareková, Kenny Paterson, Eyal Ronen and Igors Stepanovs, we have finally completed our (first, formal, in-depth, computational) analysis of the Telegram key exchange. This work is going to be presented at Eurocrypt 2025 in Madrid.

Abstract. We describe, formally model, and prove the security of Telegram’s key exchange protocols for client-server communications. To achieve this, we develop a suitable multi-stage key exchange security model along with pseudocode descriptions of the Telegram protocols that are based on analysis of Telegram’s specifications and client source code. We carefully document how our descriptions differ from reality and justify our modelling choices. Our security proofs reduce the security of the protocols to that of their cryptographic building blocks, but the subsequent analysis of those building blocks requires the introduction of a number of novel security assumptions, reflecting many design decisions made by Telegram that are suboptimal from the perspective of formal analysis. Along the way, we provide a proof of IND-CCA security for the variant of RSA-OEAP+ used in Telegram and identify a hypothetical attack exploiting current Telegram server behaviour (which is not captured in our protocol descriptions). Finally, we reflect on the broader lessons about protocol design that can be taken from our work.

Let me expand a bit on what “the Telegram key exchange” means, here. Telegram uses its bespoke MTProto protocol to secure its client-server communications. The cryptographic core of MTProto consists of a key exchange protocol and an encryption protocol. A few years back we had already analysed the encryption protocol.

Although that prior work focused on the encryption protocol, we also uncovered a vulnerability in Telegram’s key exchange protocol which Telegram fixed in response. We now completed a formal analysis of Telegram’s key exchange protocol and, in a sense, established that this fix works – but with many caveats.

Broadly, we establish that Telegram’s key exchange protocol provides some standard security guarantees. These guarantees, however, rely on several “non-standard” assumptions that appear to be necessary because of the brittle and ad-hoc nature of how Telegram’s protocol was designed.

Below, I reproduce a section from our paper which discusses this. I have edited it to make it somewhat work without the context of the entire paper. The reason why I pulled out this section for this blog post is because we are also trying to convince practitioners to design their protocols to be – at least – “analysis friendly” (ideally, they’d come with such an analysis directly). Friends don’t let friends deploy a cryptographic protocol without a formal cryptographic analysis.

In theory, the design of a cryptographic protocol has the sole purpose of achieving the protocol’s security goals efficiently. In actuality, however, to achieve this goal it must also achieve the goal of allowing at least a sufficiently motivated expert to convince themselves that the protocol achieves these goals. In other words, the central insight of what is commonly referred to as “modern cryptography” is that a cryptographic design is also tasked with being easy to reason about.

A fundamental paradigm of achieving this goal is modularity, where different components of the design can be reasoned about in isolation and then (generically) composed to establish overall security guarantees. This modularity is typically achieved by relying on building blocks that provide strong security guarantees on their own (as opposed to only and potentially in specific compositions) and by breaking the dependency between different components of a protocol by avoiding re-use of secret material.

Telegram’s failure to achieve this design goal is the root cause for the limitations and complexity of our proofs and our seeming need to reach for unstudied assumptions on cryptographic building blocks than would otherwise be necessary.

Below, we discuss these issues and highlight several of the main Telegram design choices and their effect on our proofs of security. We begin with mere complications, then move on to limitations and seemingly necessary ad-hoc assumptions. We finish by briefly recapping our hypothetical attack. We also discuss design choices that led to these issues and note that the same design choice often lead to several different difficulties for arguing for the security of Telegram, leading to necessary repetitions in what follows.

Several design choices made by Telegram introduced many otherwise avoidable complications in our proofs.

Lack of a suitable key schedule. Some value – referred to as a nonce but also used as a key – is passed to a custom key derivation function (KDF), to a function computing a key confirmation hash h and is partially XORed with the server’s nonce to form the server’s salt. These three uses of are across three different Send calls, rendering it impossible to replace values one-by-one with random values and appealing to some pseudorandom function (PRF) notion to justify the changes. If instead had been used solely as an input to the KDF to produce pseudorandom values, with these values replacing the three uses of , then a significantly simpler proof would have been obtainable.

Similarly, two values called ax and aid are both the result of a single SHA-1 call, which prevents the proof from manipulating them independently.

Use of a (truncated) weak hash function. Although more efficient and secure alternatives such as SHA-256 and SHA3 exist, Telegram also uses the now mostly deprecated SHA-1 algorithm. SHA-1 has been shown not to be collision resistant via practical attacks. The use of SHA-1 to compute the key confirmation hash h complicates our proof. If a collision-resistant hash function had been used, we could have relied on this property in the first step of the proof to establish public session matching.

Further, the output of the SHA-1 hash is truncated to only 64 bits. This prevents us from using a simple PRF notion due to easy attacks even in the one-time PRF setting.

Short session identifiers. The 64-bit value output of the above-mentioned truncated hash function is aid. This value is used by the Telegram servers to identify sessions. On the one hand, this imposes a hard bound of on the number of sessions each responder can accept. On the other hand, the shortness of the value suggests that collisions between session state identifiers are likely, which complicates the proof. A longer value, even of 128 bits, would have allowed for a simpler proof.

Lack of ciphertext integrity. Telegram’s MTProto relies on a custom mode of operation composing IGE-mode and SHA-1. The composition achieves neither INT-CTXT nor IND-CCA. Had an established authenticated encryption scheme or an unforgable MAC been used, this would have simplified the proof in allowing us to declare the Diffie-Hellman shares authenticated and using the ciphertext/mac tag as part of our session identifiers. This in turn would have enabled public session matching based on transcripts.

Reliance on plaintext checking. Our proof relies on the correctness of a complex parsing behaviour and the checking of various plaintext headers and nonce values. That is, we also could not achieve modularity separating cryptographic operations and higher-level protocol operations.

In particular, to prove soundness we require that all message headers are different, so there cannot be confusion about which state the protocol is in and role confusion is also ruled out.

The main limitation of our proof is that we do not model the actual connection between the initial run of the key exchange and subsequent runs of it (see paper for details). Moreover, our model does not allow for generic composition of our theorems about the key exchange and existing results about the encryption protocol. This is due to several design choices made by Telegram that prevent simple composition of the security proofs.

Key dependence. While being composed of multiple stages, the key exchange protocol does not derive the keys in the different stages independently. This prevents us from using general composition results on key exchanges and encryption protocols to argue about the security of the key exchange when used in conjunction with the encryption protocol.

Another example is the fact that the Diffie-Hellman value in a sub-protocol is used to internally derive ax and aid, and is used afterwards as an encryption key ak. Instead, if the DH value had been used as an input to a KDF to derive ax, aid and authkey as (computationally) independent keys, a composition result would be more feasible to achieve.

Public key reuse. We do not model the fact that the public key pk of the server is used in several sub-protocols. To model this, a proof would have to consistently update it across two different games simultaneously. Using different independent keys would have allowed us to treat the two protocols separately without essentially assuming the co-dependence away.

Lack of key confirmation. We were unable to prove key confirmation for one sub-protocol and only proved key confirmation for the server for the full protocol. Key confirmation would have been possible if h was produced using a secure MAC.

Direct use of non-uniform key material. MTProto uses bits of the agreed DH values directly as key material instead of using them as an input to a key derivation function. However, the existing proof for MTProto assumes a uniform key distribution. This prevents us from composing our results with those prior results. Moreover, this forces us to use a session key distribution for some stage which is not the uniform distribution on strings of a given size.

Retry handling. In general, it is difficult to reason about the security of a protocol without knowing the total number of exchanged messages. For example, the security bound for INT-PTXT depends on the number of encryption and decryption queries, which in turn depends on the number of retries. Two aspects of the protocol design prevent us from making an argument that the number of retries would be bounded in practice. First, there is a question of preventing adversarially-triggered retries: this would necessitate showing that some custom hash function outputs are unforgeable, which is not possible due to its short input length. Second, even if the adversary was not able to directly manipulate the flow of the protocol, it remains in control of creating new sessions, which in turn influences the size of each server’s set of known sessions that determines the likelihood of an honest retry. Thus, we were forced to assume a maximum retry number.

In our paper, we describe several unstudied ad-hoc and new assumptions that we used in our proofs. These assumptions could have been avoided if collision-resistant hash functions (e.g. SHA-256 or SHA3) had been used instead of SHA-1 and if proper key derivation functions had been used.

We can view these assumptions as part of two groups, based on their plausibility and impliciations if they were invalidated. The first two (4PRF, 3TPRF) are lower-level, expressing a pseudorandomness property of SHACAL-1 (the block cipher inside SHA-1): they appear plausible due to the large key length of SHACAL-1, but symmetric cryptanalysis would be needed to determine the concrete reduction in advantage compared to the known results on SHACAL-1 without leakage.

The remaining three (SPR, UPCR, IND-KEY) are higher-level, expressing properties of SHA-1 that are variants of standard assumptions or more novel. However, it appears that breaking either of these would not be sufficient to break the key exchange protocol; there exist versions of these assumptions which if broken would be sufficient to break the protocol, but they place even stricter constraints on the adversary.

Weak channel binding. We also describe an attack on client authentication that is based on the way that a new temporary key is bound to the long-term authentication key ak. The attack exploits the fact that the Telegram server used to not verify the expiration time sent in the binding message. Although Telegram has addressed this specific issue by enforcing the check, the design choice to rely on such checks for session binding is brittle, and its security depends on nuanced details related to the way session key management and expiration are implemented. Instead, more robust cryptographic approaches can be used to bind between the sessions that generate the new temporary key and ak. For example, one approach is to calculate a MAC over the transcript of the current session’s handshake using a key derived from ak as the MAC key.

Our work, titled Hollow LWE: A New Spin — Unbounded Updatable Encryption from LWE and PCE, is now available on ePrint and will be presented at Eurocrypt 2025 in Madrid in May. It is joint work with Benjamin Benčina and Russell W. F. Lai. The main technical contribution is a new approach – a new spin, haha, we’re funny – to rerandomising LWE public keys. Roughly, the security goal here is that even given the rerandomised secret key, an adversary should not be able to distinguish the original LWE public key from uniform (in the appropriate space).

Consider the inhomogeneous dual-Regev public-key encryption scheme, where the secret key is a short vector , and the public key consists of a uniformly random tall matrix (where ), and a vector such that .

The current paradigm of rerandomising such public keys has been to add some small random noise to the public key. This noise can then, for example, be encrypted as an update token, distributed and later decrypted and added to the secret key in a way that ensures the new key-pair is valid.

Our main idea is to instead take a random signed permutation matrix and rotate the public key into and , where can be any random basis change.

Thus, we combine LWE with ideas around the Lattice Isomorphism Problem (LIP). Note that LIP over -ary lattices (with prime) and restricted to integral isometries is precisely the Signed Permutation Equivalence Problem (SPCE) for linear codes over .

However, SPCE is easy for random codes due to so-called “hull attacks”, and we thus have to limit ourselves to public keys that generate a code with hull dimension big enough so that hull attacks are not efficient.

A code has hull dimension if its generator matrix satisfies . In other words, it contains a vector space of dimension that is orthogonal to the remaining dimensions and self-orthogonal.

In the paper we show that LWE with respect to such matrices is hard if LWE is hard and that a Leftover Hash Lemma applies when is of this form.

It is worth noting that while we use signed permutations in our construction, the security of our construction relies on Permutation Code Equivalence (PCE), where is simply a permutation. This is not much of a loss in the worst case because there the two problems are polynomial-time equivalent.

The reason for relying on PCE is that we need to plant a code equivalence instance when arguing that our public key remains pseudorandom even given the rerandomised (public-,secret-)key pair. In order to plant a challenge code equivalence instance – which consists of two matrices which are either equivalent or not – we need to take such an instance and turn it into a dual-Regev public key consistently. Relying on PCE allows us to start from as the “secret key” which we then later rerandomise to obtain . The “trick” here is that for any permutation matrix . See the paper for details.

We use these techniques to build an updatable public-key encryption scheme. The performance of this scheme is not great yet, but its parameters do not grow with the number of updates supported, i.e. it supports an unbounded polynomial number of updates. We are working on ideas to improve performance, see the Open Problems section of our paper for more details.

We are inviting applications for a PhD studentship in the cryptography lab at King’s College London. Specifically, we are looking for an applicant to work with me and Benjamin Dowling.

The PhD could, for example, cover cryptanalysing existing cryptographic technologies/protocols, such as Telegram or WhatsApp, or modelling and designing new cryptographic protocols or primitives.

This PhD will work in a team consisting of social scientists, specifically ethnographers, and us cryptographers. Together, we study what the security needs and wants of participants in large-scale protests are and how these relate to the security guarantees provided by cryptographic solutions.

See, for example, the lecture “Limits of Proofs (Social Foundations)” or this blog post (for another position on this project) for more details of what we’re trying to do here.

We encourage applicants to reach out to us to discuss the position informally before applying, by e-mailing Ben and me: martin.albrecht_AT_kcl.ac.uk and benjamin.dowling_AT_kcl.ac.uk.

Fine print. This is a fully-funded positions covering both fees and maintenance. The latter is at the UKRI rate. We seek applicants with a strong background in mathematics and/or computer science, preferably with some background in cryptography. We will consider applications on a rolling basis.