Martin R. Albrecht

Slides of my talk titled "Lattices give us KEMs and FHE, but where are the efficient lattice PETs? -- By Example of (Verifiable) Oblivious PRFs" given at spiqe-workshop.github.io are here: github.com/malb/talks/b...

Thanks @kennyog.bsky.social and @jurajsomorovsky.bsky.social for inviting me.

Abstract. The Unbalanced Oil and Vinegar construction (UOV) has been the backbone of multivariate cryptography since the fall of HFE-based schemes. In fact, 7 UOV-based schemes have been submitted to the NIST additional call for signatures, and 4 of these made it to the second round. For efficiency considerations, most of these schemes are defined over a field of characteristic 2. This has as a side effect that the polar forms of the UOV public maps are not only symmetric, but also alternating. In this work, we propose a new key-recovery attack on UOV in characteristic 2 that makes use of this property. We consider the polar forms of the UOV public maps as elements of the exterior algebra. We show that these are contained in a certain subspace of the second exterior power that is dependent on the oil space. This allows us to define relations between the polar forms and the image of the dual of the oil space under the Plücker embedding. With this, we can recover the secret oil space using sparse linear algebra. This new attack has an improved complexity over previous methods and reduces the security by 4, 11, and 20 bits for uov-Ip, uov-III, and uov-V, respectively. Furthermore, the attack is applicable to MAYO₂ and improves on the best attack by 28 bits.

Image showing part 2 of abstract.

Wedges, oil, and vinegar – An analysis of UOV in characteristic 2 (Lars Ran) ia.cr/2025/1143

A chart for quantum computers, of number of qubits versus error rate, on a logarithmic scale. Broadly it shows a large gap between current quantum computers in the bottom left, and a curve in the top right of the resources they need to break RSA.

An out-of-schedule update to my quantum landscape chart: sam-jaques.appspot.com/quantum_land..., prompted by
@craiggidney.bsky.social 's new paper: arxiv.org/abs/2505.15917.

A startling jump (20x) in how easy quantum factoring can be!

Also: much improved web design!

On the Virtues of Information Security in the UK Climate Movement 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 …

New blog post on our (with @rikkebjerg.bsky.social and @mikaelabrough.bsky.social) USENIX'25 paper "On the Virtues of Information Security in the UK Climate Movement" where I end up reflecting on writing this, for me, unusual work.

martinralbrecht.wordpress.com/2025/06/14/o...

GitHub - malb/lattice-estimator: An attempt at a new LWE estimator An attempt at a new LWE estimator. Contribute to malb/lattice-estimator development by creating an account on GitHub.

Eamonn and I received a Zama Cryptanalysis Grant to help with the lattice estimator github.com/malb/lattice.... We hope to hire interns to work on the estimator over two periods over the next 18 months.

Zama are still taking applications for this grant, see here: www.zama.ai/post/announc...

10 June: Jean-François Blanchette Talk and Discussion on "Burdens of Proof" in London

martinralbrecht.wordpress.com/2025/04/15/1...

Isn't the answer mostly Heartbleed?

More is Less: On the End-to-End Security of Group Chats in Signal, WhatsApp, and Threema Secure instant messaging is utilized in two variants: one-to-one communication and group communication. While the first variant has received much attention lately (Frosch et al., EuroS&P16; Cohn-Gordo...

Ooh -- also: The "More is Less" paper (eprint.iacr.org/2017/713 ) pointed out this group membership issue with WhatsApp in 2017 -- almost 8 years ago!

Dan wrote a nice thread about our work on WhatsApp presented at Eurocrypt earlier today and discussed in @dangoodin.bsky.social's article linked below.

WhatsApp provides no cryptographic management for group messages The weakness creates the possibility of an insider or hacker adding rogue members.

... who have to constantly monitor the UI for changes to the member list. And it is a burden that is unnecessary: Signal deploys cryptographic control of group membership at scale, for example. Thanks @dangoodin.bsky.social for your coverage of our work in this piece: arstechnica.com/security/202...

Formal Analysis of Multi-Device Group Messaging in WhatsApp WhatsApp provides end-to-end encrypted messaging to over two billion users. However, due to a lack of public documentation and source code, the specific security guarantees it provides are unclear. Se...

How does WhatsApp implement encrypted group chats? And are they secure? @malb.bsky.social, @bedow.bsky.social and myself were keen to figure this out. After two years of reverse-engineering, analysis and a few too many proofs, I presented our work at Eurocrypt earlier today. So, what did we learn?

This is cool heimberger.xyz/oprfs.html

Just about ready to set off to Madrid for #eurocrypt 2025, where I’ll have the great honour of giving the 2025 IACR Distinguished Lecture on Tuesday afternoon. #iacr #cryptography

Abstract. WhatsApp provides end-to-end encrypted messaging to over two billion users. However, due to a lack of public documentation and source code, the specific security guarantees it provides are unclear. Seeking to rectify this situation, we combine the limited public documentation with information we gather through reverse-engineering its implementation to provide a formal description of the subset of WhatsApp that provides multi-device group messaging. We utilise this description to state and prove the security guarantees that this subset of WhatsApp provides. Our analysis is performed within a variant of the Device-Oriented Group Messaging model, which we extend to support device revocation. We discuss how to interpret these results, including the security WhatsApp provides as well as its limitations.

Formal Analysis of Multi-Device Group Messaging in WhatsApp (Martin R. Albrecht, Benjamin Dowling, Daniel Jones) ia.cr/2025/794

GitHub - Jacksaur/Gorgeous-GRUB: Collection of decent Community-made GRUB themes. Contributions welcome! Collection of decent Community-made GRUB themes. Contributions welcome! - Jacksaur/Gorgeous-GRUB

Okay, this is fun github.com/Jacksaur/Gor... I like the DOOM one.

A paragraph from Boaz Barak's recent NY Times op-ed: 'You might think I can avoid politics in the classroom only because I am a computer scientist. This is not the case. Faculty members who are determined enough can inject politics into any topic, and after all, computer science has brought huge and significant changes to society. The interaction of computer science and policy sometimes arises in my classes, and I make sure to present multiple perspectives. When I teach cryptography, a topic at the heart of the tension between privacy and security, I share with my students writings by former National Security Agency officials as well as "The Crypto Anarchist Manifesto."'

We teach a broad range of political perspectives here at Harvard... ranging from those of *checks notes*... center-right military officials to... *squints* ultra-right market absolutists, and you should be more grateful for that.

The idea that you can just “teach computer science” and be apolitical is a beautiful dream that expired in the 2000s, at the latest. Computer science has re-organized every facet of our society: it is inherently political. Instead of taking this idea seriously, we ran from it. Now we live in hell.

Day two of the strike, and we've ben getting a lot of questions from students about the action. What's it for, why are we doing it now, and how can they help.

So let's run through some Strike Questions! 🧵

clang-format on Ubuntu 24.04 has different ideas · Issue #538 · fplll/fplll It seems clang-format on Ubuntu 24.04 flags some code as non-compliant that previously was considered compliant

If someone is up for helping with some bitrot in FPLLL, FPyLLL and G6K, that'd be nice.

- github.com/fplll/fplll/...
- github.com/fplll/fplll/...
- github.com/fplll/fpylll...

Advanced Cryptography Deciding when to use Advanced Cryptography to protect your data

NCSC-née-GCHQ have a whitepaper on FHE, PIR, MPC, ZK, PSI and ABE out: www.ncsc.gov.uk/whitepaper/a...

There’s just so much shady shit in this story, but this really sticks out. Folks in NLRB’s IT unit were so freaked out by what they saw DOGE doing that they wanted to notify the Cybersecurity and Infrastructure Security Agency. Then this happened:

Website excerpt: Here, the authors consider a whistleblower setting which then motivates the definition of ring signatures. Thus, a ring signature claims to be at least also a formalisation of the social setting in which a member of a group wishes to alert outsides to something without revealing themselves while still convincing the outsider that they have access to the information being leaked. Put differently, cryptography presumes and models social relations. As such, cryptography is also a social science. However, cryptography is unaware of itself as a social science and we cryptographers more or less speculatively make up the social settings we model in our paper’s introductions. I highly recommend Jean-François Blanchette’s “Burdens of Proof: Cryptographic Culture and Evidence Law in the Age of Electronic Documents” for a deeper dive into this observation. This begs the question if cryptography gets that part of its models right? In general, we work hard to have precise definitions and definitional work is a central activity of cryptography. Yet, the correctness of this part of the definitional work is usually simply presumed: “On these questions, the literature remains silent” as Blanchette put it.

Here's a previous take on said book from social-foundations-of-cryptography.gitlab.io/2024/06/12/p...

10 June: Jean-François Blanchette Talk and Discussion on "Burdens of Proof" in London

martinralbrecht.wordpress.com/2025/04/15/1...

Article extract: From what he could see, the data leaving, almost all text files, added up to around 10 gigabytes — or the equivalent of a full stack of encyclopedias if someone printed them, he explained. It's a sizable chunk of the total data in the NLRB system, though the agency itself hosts over 10 terabytes in historical data. It's unclear which files were copied and removed or whether they were consolidated and compressed, which could mean even more data was exfiltrated. It's also possible that DOGE ran queries looking for specific files in the NLRB's system and took only what it was looking for, according to the disclosure.

Article extract: It houses information about ongoing contested labor cases, lists of union activists, internal case notes, personal information from Social Security numbers to home addresses, proprietary corporate data and more information that never gets published openly.

This long read is quite something: www.npr.org/2025/04/15/n...

tariff Make importing great again! A parody package that imposes tariffs on Python imports.

pypi.org/project/tari... !

Meanwhile, S&P is held in a month in San Francisco and there seems to be no plan to switch to hybrid. We've entered the reign of the arbitrary, *everybody* is affected.

An excerpt from the linked FT piece that reads: "So the fight for domination of the future payments system is on — and the US wants to win. The broader European public may be blissfully unaware. But those in charge of the Eurozone are also determined that this battle for technological control over the economy is one that the EU must not lose. This is the fundamental motivation for the digital euro — a central bank-issued official digital currency that, if done well and fast enough, will rival or outperform the attractiveness of dollar stablecoins."

On digital currencies and the great power conflict between the US and the EU: "The battle for the global payments system is under way" www.ft.com/content/40f6...

(I know the FT is paywalled, sorry about that!)

When our union is in dispute and when we take action we ask for solidarity from across the movement and our communities because we are all connected in struggle. So it matters that we also practice solidarity with sibling unions in dispute and when taking action. Solidarity @uniteucu.bsky.social

Breaking and Fixing Content-Defined Chunking Content-defined chunking (CDC) algorithms split streams of data into smaller blocks, called chunks, in a way that preserves chunk boundaries when the data is partially changed. CDC is ubiquitous in ap...

Oh fun! "Breaking and Fixing Content-Defined Chunking" uses G6K in one of the attacks: worlds colliding, lattice reduction in the wild something something.

eprint.iacr.org/2025/558
github.com/fplll/g6k

Actual cryptographers have studied this. Here js their peer-reviewed research:

mtpsym.github.io

eprint.iacr.org/2022/595

eprint.iacr.org/2025/451