10 June: Jean-François Blanchette Talk in London

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.

Title

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

Blurb

10-june:-jean-françois-blanchette-talk-in-london.png

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.

Speaker Bio

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.

Venue

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

Date/Time

Tuesday, 10 June, 2pm to 4pm

Registration

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.

Analysis of the Telegram Key Exchange

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.

Continue reading “Analysis of the Telegram Key Exchange” →

Rerandomising LWE

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

Continue reading “Rerandomising LWE” →

PhD Position in Cryptography

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.

PhD Position in Lattice-Based Cryptography

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 us in the area of lattice-based cryptography. We are particularly interested in the study of and constructions from new lattice-based assumptions and privacy-preserving technologies based on lattices.

The PhD could cover studying the underlying hard mathematical problems, cryptanalysis, constructions or applications of lattice-techniques. This can cover post-quantum aspects of lattice-based cryptography and/or advanced functionalities.

The applicant would work with me, Ngoc Khanh Nguyen and/or Eamonn Postlethwaite. We encourage applicants to reach out to me to discuss the position informally before applying.

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

Verifiable Oblivious Pseudorandom Functions from Lattices: Practical-ish and Thresholdisable

Our paper (with Kamil Doruk Gur) “Verifiable Oblivious Pseudorandom Functions from Lattices: Practical-ish and Thresholdisable” is now available on ePrint and will appear at Asiacrypt 2024. Doruk and I started working on this together when he did his residency at SandboxAQ.

Here’s the abstract:

We revisit the lattice-based verifiable oblivious PRF construction from PKC’21 and remove or mitigate its central three sources of inefficiency. First, applying Rényi divergence arguments, we eliminate one superpolynomial factor from the ciphertext modulus q, allowing us to reduce the overall bandwidth consumed by RLWE samples by about a factor of four. This necessitates us introducing intermediate unpredictability notions to argue PRF security of the final output in the Random Oracle model. Second, we remove the reliance on the 1D-SIS assumption, which reduces another superpolynomial factor, albeit to a factor that is still superpolynomial. Third, by applying the state-of-the-art in zero-knowledge proofs for lattice statements, we achieve a reduction in bandwidth of several orders of magnitude for this material. Finally, we give a t-out-of-n threshold variant of the VOPRF for constant t and with trusted setup, based on a n-out-of-n distributed variant of the VOPRF (and without trusted setup).

The TL;DR is that we get a (plausibly) post-quantum (V)OPRF following the blueprint of [PKC:ADDS21] with about 100KB bandwidth cost for offline communication (once) and 200KB bandwidth cost for online communication (per query), if you’re happy with $\lambda \approx 100$ . Note that we could amortise the online cost to roughly 100KB per query if several queries are sent in parallel, but we do not cost this in our work.

Continue reading “Verifiable Oblivious Pseudorandom Functions from Lattices: Practical-ish and Thresholdisable” →

Social Foundations of Cryptography

I’m rather excited to report that EPSRC decided to fund our grant titled “Social Foundations of Cryptography”. Our project tries to do two things.

First, we want to ground cryptographic security notions in rigorous social science findings rather than “simply” our intuitions that we write down in the introductions of our papers. In Burdens of Proof, Jean-François Blanchette characterises what we – as cryptographers – do as follows:

New cryptographic objects are generated through more or less straightforward combinations of elements of the cryptographic toolbox, such as threshold, proxy, or fairness properties. Like so many modular Lego pieces, cryptographic primitives and design patterns are assembled in new schemes and protocols exhibiting security properties with no obvious real-world equivalents. This creative process is one of the core professional activities of cryptographers, rewarded through conference presentations, journal publications, and commercial patents. Yet the cryptographic paper genre seems to require that these products of mathematical creativity be justified in some “real-world” setting, motivated either by their potential application, their evidential value, or the new threats they identify. These justificatory scenarios are remarkable in their assumptions that the properties of cryptographic objects, as designed and discussed by cryptographers, will translate transparently into the complex social settings they describe.

Our approach is to flip this approach around: make cryptographic security notions contingent on ethnographic findings. This is, of course, a tall order when it comes to, say, PRP security of a block cipher (I enjoy Phil Rogaway’s discussion of cryptographic definitions, Phil is also on our advisory board), but it is perhaps a bit more obvious when we talk about ideal functionalities in simulation-based proofs of complex cryptographic protocols. For these ideal functionalities it is not at all immediately clear they are indeed “ideal”. Still, this remains quite a daunting project and I’m rather nervous about it.

Second, we picked the settings of large-scale urban protests, i.e. ask about security notions and needs of protesters confronting agents of the state. We think these settings (we plan on doing field work in different sites internationally) are rich yet specific. That is, notions of security depend on context and grounding cryptographic notions in such contexts can unlock insights. Post-compromise security needs for a business traveller (having their phone confiscated at an airport) and for protesters (who face arrest) may be quite different.

Another key, distinguishing, feature of these settings is that security notions are quite collective rather than individual, according to our pilot study. In this study we interviewed protesters involved in the Anti Extradition Bill protests in Hong Kong (2019/2020). This work then motivated us to then take a deeper look at Telegram. However, this pilot study has the big caveat that its inquiry was somewhat limited, by necessity.

Our study was an interview study, meaning participants self-selected to discuss their security needs with us. Yet, a key challenge in engaging those who depend on security technology is that they are not trained information security professionals. They do not know and, indeed, should not need to know, for example, that confidentiality requires integrity, that existing onboarding practices can be phrased in the language of information security, which different security notions cannot be achieved simultaneously and what guarantees, say, cryptography, can give if asked. Therefore, to know exactly what is taken for granted, or put otherwise, expected or desired, in social interactions, social and technical protocols and, indeed, cryptography is of critical import.

This is where ethnography comes in, as it is uniquely placed to “unearth what the group (under study) takes for granted”. In a nutshell, it’s a social science method involving prolonged field work, i.e. staying with the group under study, to observe not only what they say but also what their social reality and practice is.

On the cryptographic side, our project consists of Ben Dowling (Sheffield) and me. On the ethnography side, it’s Andrea Medrado (Westminster) and Rikke Jensen (RHUL). But we’re hiring! We will have one postdoc position in ethnography at RHUL (perhaps not so relevant to the audience of this blog, see Rikke’s blog post) and one postdoc position in cryptography. This position is only scheduled to start in a year, but if you’re interested please let us know, we have some flexibility about when to put it on the market.

I’ve hired for postdoc positions before, but I think I’ve never been this nervous about that process as here. If working on the protest setting and putting what you’ll do at the mercy of ethnographic findings is for you, please reach out!

Our project website is here: https://social-foundations-of-cryptography.gitlab.io/

A Surfeit of SIS with Hints Assumptions

After a “lattice-assumptions winter”™ (there, I coined it now!) because “knapsack”, the last few years have seen the introduction of a bunch of newfangled SIS-like assumptions along the lines of:

Given $\left(\mathbf{A}, \{\mathbf{u}_i\}_{0 \le i < k}, \{\mathbf{t}_i\}_{0 \le i < k}\right)$ s.t. $\mathbf{A} \cdot \mathbf{u}_i \equiv \mathbf{t}_i \bmod q$ , with $\mathbf{u}_i$ short, it is hard to find a short $\mathbf{u}^*$ s.t. $\mathbf{A} \cdot \mathbf{u}^* \equiv \mathbf{0} \bmod q$ .

That is, in some shape or form, these assumptions posit that some variant of SIS or ISIS remains hard even if you hand out some short preimages of some specially selected targets. There’s quite some variety here: BASIS instead hands out a trapdoor for a bigger related matrix, one-more-ISIS allows the adversary to pick the targets but has tight norm constraints etc.

I’ve started to track these new assumptions in the SIS with Hints Zoo, with the hope of encouraging cryptanalysis, reductions and/or re-use of existing assumptions. That page has been up for a little while. I’m blogging about it now, because it now has a few “non-trivial” entries, that you might have missed and that illustrate well that cryptanalysis and reductions are fruitful endeavours here:

Knowledge k-R-ISIS is false: Knowledge (I’m good with words like that!) of this break has been circulating a while, but since the paper breaking it is finally out, it is time to amplify the message: The knowledge version of the k-R-ISIS assumption from https://eprint.iacr.org/2022/941 is (at least morally) false. It thus gets a “BROKEN” tag.
Twin k-R-ISIS is no easier than k-R-ISIS: In Appendix A of https://eprint.iacr.org/2023/1469 we show that if you can solve Twin k-R-ISIS you can also solve k-R-ISIS (under parameters etc). It thus gets an “EQUIVALENT” tag.
$h$ -PRISIS is hard: under the M-SIS assumption and for degree $\ell=2$ , as was shown in https://eprint.iacr.org/2023/846. That $\ell=2$ is useful is established in https://eprint.iacr.org/2023/1469. It thus gets a “STANDARD” tag.

If your (favourite) assumption is missing or is misrepresented, please get in touch: PRs welcome, too.

Post-quantum oblivious PRFs from shallow PRFs and TFHE

We – Alex Davidson, Amit Deo, Daniel Gardham and me – have updated our pre-print Crypto Dark Matter on the Torus: Oblivious PRFs from shallow PRFs and TFHE. It has been around for a while, but I am now somewhat confident that we won’t squeeze more performance out of it for the time being, so this feels like the right time to blog about.

What is an OPRF and why should I care? Oblivious pseudorandom functions allow two parties to compute a pseudorandom function (PRF) $z := F_k(x)$ together: a server supplying a key $k$ and a user supplying a private input $x$ . The server does not learn $x$ or $z$ and the user does not learn $k$ . If the user can be convinced that $z$ is correct (i.e. that evaluation is performed under the correct key) then the function is “verifiable oblivious” (VOPRF), otherwise it is only “oblivious” (OPRF). Both may be used in many cryptographic applications. Example applications include anonymous credentials (e.g. Cloudflare’s PrivacyPass), password-based key exchanges (e.g. OPAQUE) and Private Set Intersection (PSI) enabling e.g. privacy-preserving contact look-up on chat platforms.

Sounds good, seems solved! Despite the wide use of (V)OPRFs, most constructions are based on classical assumptions, such as Diffie-Hellman (DH), RSA or even pairing-based assumptions. Indeed, DH-based OPRFs are currently being standardised by the IETF. Their vulnerability to quantum adversaries makes it desirable to find post-quantum solutions, however, known candidates are much less efficient.

Oblivious PRF and FHE, I see where this is going … Indeed, given fully homomorphic encryption (FHE), there is a natural (P)OPRF candidate. The client FHE encrypts input $x$ and sends it with tag $t$ . The server then evaluates the PRF homomorphically or “blindly” using a key derived from $t$ and its own secret key. Finally, the client decrypts the resulting ciphertext to obtain the PRF output. The first challenge with this approach is performance, PRFs tend to have sufficiently deep circuits that FHE schemes struggle to evaluate them efficiently. Even special purpose PRFs such as the LowMC construction require depth ten or more, making them somewhat impractical. More generally, in a binary circuit model we expect to require depth $\Theta( \log \lambda)$ to obtain a PRF resisting attacks with complexity $2^{\Theta(\lambda)}$ .

Yet, if we expand our circuit model to arithmetic circuits with both mod $p$ and mod $q$ gates for $p\neq q$ both primes, shallow proposals exist. The main proposal even has a kewl name: “Crypto Dark Matter PRF”. In particular, the (weak) PRF candidate is

$z := \sum (\mathbf{A} \cdot \mathbf{x} \bmod 2) \bmod 3$

where arithmetic operations are over the integers and $\mathbf{A}$ is the secret key. That’s it! The same work also contains a proposal to “upgrade” this weak PRF, defined for uniformly random inputs $\mathbf{x}$ , to a full PRF, taking any $\mathbf{x}$ . Furthermore, the works already provide oblivious PRF candidates based on this PRF and MPC, but with non-optimal round complexity. Thus, a natural question to ask is if we can construct a round-optimal (or, 2 message) POPRF based on this PRF candidate using the FHE-based paradigm mentioned above.

So what did you actually do? We construct a novel POPRF from lattice assumptions and the “Crypto Dark Matter” PRF candidate in the random oracle model. At a conceptual level, our scheme exploits the alignment of this family of PRF candidates, relying on mixed modulus computations, and programmable bootstrapping in the torus fully homomorphic encryption scheme (TFHE). This allows us to construct an OPRF candidate using only one level of bootstrapping (the most expensive operation in a FHE computation). We also explore a cut-and-choose based strategy for adding verifiability to our OPRF.

Performance. For the core online OPRF functionality, we require amortised 10.0KB communication per evaluation and a one-time per-client setup communication of 2.5MB. I’d say his makes our OPRF practical size-wise. Client computation costs are also somewhat manageable but server computation costs are quite unattractive unless you’re willing to invest in some FHE co-processor. We have some early benchmarks (using tfhe-rs) running the server code in ~150ms on 64 cores. Let me stress that this does not account for “circuit privacy” which should add a factor of 5x to 10x (or the zk systems we need, but we assume those won’t add that much overhead in computation, we do include their sizes in the estimates above). Moreover, our relatively small sizes are the effect of aggressive packing, unpacked the key material should weight about ~2GB in RAM.

Implementation. We do have a somewhat complete implementation of our scheme, but it is in SageMath and thus extremely slow. I should mention, though, that this implementation, too, does not cover the zero-knowledge proof systems we rely on to achieve malicious security.