Lena Heimberger

📢 We have extended the deadline for our EC workshop to *Monday AoE*!

Submit your talk proposal on any topic related to cryptographic proofs and proof techniques 🤓

Take the opportunity to advertise your ongoing, submitted or published work, or to share other insights related to security proofs

Finally got around to upload the slides from my Paris Crypto Day talk "Oblivious Pseudorandom Functions in
a Post-Quantum World"- check them out here: heimberger.xyz/docs/cryptod...

DCTF26 Schedule, talks and talk submissions for DCTF26

DCTF26 will happen from March 21, 2026 - March 22, 2026 in Ljubljana, which is most beautiful in Spring.
DCTF is my favourite conference of the year. It's technically challenging, student-organized and also free. Please consider submitting to the CFP: cfp.dragonsec.si/dctf26/cfp (speaker dinner!)

15:00–16:00: Duy Nguyen: "OMIX: Offline Mixing for Scalable Self-Tallying Elections"
16:00 - 16:15: Coffee
16:15–17:15: Ivan Visconti : “Towards Optimal Concurrent-Secure Blind Schnorr Signatures"

Schedule for the Paris Crypto Days on January 16th at Telecom Paris:
09:30–10:15: Breakfast
10:15–12:15: T. Debris & A. Chailloux “From Regev’s Reduction to Quantum Advantages”
12:15–14:00: Lunch
14:00–15:00: Lena Heimberger: “Oblivious Pseudorandom Functions in a Post-Quantum World”

Abstract. In this work, we initiate the study of aborting hash functions, i.e., hash functions that may abort on a non-negligible fraction of inputs. We introduce the aborting random oracle model (aROM), an idealized framework that extends the standard random oracle model (ROM) to account for aborts. Within this model, we derive bounds for various security notions and establish generic indifferentiability results demonstrating how to construct aborting random oracles from standard ones. Consequently, the derived bounds ultimately hold in the standard ROM. In this way, the aROM and its associated bounds provide a convenient and easy-to-use framework for analyzing cryptographic constructions that rely on potentially aborting hash functions. To illustrate the utility of our framework, we apply our techniques to two settings: (1) the analysis of SNARK-friendly incomparable hypercube encodings, a core primitive in hash-based signature schemes, and (2) the analysis of grinding in Fiat–Shamir-based non-interactive arguments. Through our generic indifferentiability results, we can easily translate these analyses into concrete security bounds in the standard (non-aborting) random oracle model.

Image showing part 2 of abstract.

Aborting Random Oracles: How to Build them, How to Use them (Gottfried Herold, Dmitry Khovratovich, Mikhail Kudinov, Stefano Tessaro, Benedikt Wagner) ia.cr/2026/016

The EU says it is considering designating WhatsApp a "very large platform", after WhatsApp published user numbers above the DSA threshold in February 2025 (Louise Breusch Rasmussen/Reuters)

Main Link | Techmeme Permalink

Abstract. We study a new pairing, beyond the Weil and Tate pairing. The Weil pairing is a non-degenerate pairing E[m] × E[m] → μ_(m), which operates on the kernel of [m]. Similarly, when μ_(m) ⊆ 𝔽_(q)^(*), the Tate pairing is a non-degenerate pairing E[m](𝔽_(q)) × E(𝔽_(q))/[m]E(𝔽_(q)) → μ_(m), which connects the kernel and the rational cokernel of [m]. We define a pairing ⟨  ⟩_(m) : E(𝔽_(q))/[m]E(𝔽_(q)) × E(𝔽_(q))/[m]E(𝔽_(q)) → μ_(m) on the rational cokernels of [m], filling the gap left by the Weil and Tate pairing. When E[m] ⊆ E(𝔽_(q)), this pairing is non-degenerate, and can be computed using three Tate pairings, and two discrete logarithms in μ_(m), assuming a basis for E[m]. For m = ℓ prime, this pairing allows us to study E(𝔽_(q))/[ℓ]E(𝔽_(q)) directly and to simplify the computation for a basis of E[ℓ^(k)], and more generally the Sylow ℓ-torsion. This finds natural applications in isogeny-based cryptography when computing ℓ^(k)-isogenies.

The Cokernel Pairing (Krijn Reijnders) ia.cr/2026/001

I'll be around Melbourne for LatticeCC before asiacrypt. Let me know if you want to talk lattices!

📣 Germany's close to reversing its opposition to mass surveillance & private message scanning, & backing the Chat Control bill. This could end private comms-& Signal-in the EU.

Time's short and they're counting on obscurity: please let German politicians know how horrifying their reversal would be.

Abstract. Embedded devices commonly rely on digital signatures to ensure both integrity and authentication. For example, digital signatures are typically verified during the boot process or firmware updates to verify the integrity of a system. They are also used to ensure authenticity of a communication party in secure protocols. Fault injection can be used to tamper with a device in order to cause malfunctioning during cryptographic computations. For example, fault injections can be used to disturb digital signing operations. With the right type of fault an attacker can compute private keys from faulted signatures. However, fault injections can also be used during verification to get maliciously crafted digital signatures accepted during signature verification with catastrophic consequences for the security of an embedded device. In this paper, we introduce new non-obvious fault injection attacks on the verification routines of Dilithium and Falcon signature schemes, which allow an attacker to get signatures for arbitrary messages accepted by fault injection. We demonstrate the feasibility of our attacks by simulations using an ARM Cortex-M4 and the pqm4 library as a target of evaluation and pinpoint vulnerable instructions. Finally, we propose and discuss possible countermeasures against these attacks.

Image showing part 2 of abstract.

Forging Dilithium and Falcon Signatures by Single Fault Injection (Sven Bauer, Fabrizio De Santis) ia.cr/2025/2029

Thank you!

Policy, privacy and post-quantum: anonymous credentials for everyone The world is adopting anonymous credentials for digital privacy, but these systems are vulnerable to quantum computers. This post explores the cryptographic challenges and promising research paths tow...

Anonymous credentials are going to have a big year. In the realm of "fancy" cryptography, they're perhaps the most important primitive we'll need to make PQ. Where do we stand? Lena Heimberger spent part of the summer finding out.
blog.cloudflare.com/pq-anonymous...

Policy, privacy and post-quantum: anonymous credentials for everyone The world is adopting anonymous credentials for digital privacy, but these systems are vulnerable to quantum computers. This post explores the cryptographic challenges and promising research paths tow...

@cjpatton.bsky.social and @meyira.bsky.social also dive into how we can make these primitives post-quantum secure
blog.cloudflare.com/pq-anonymous...

Anonymous credentials- rate-limiting bots and agents without compromising privacy As AI agents change how the Internet is used, they create a challenge for security. We explore how Anonymous Credentials can rate limit agent traffic and block abuse without tracking users or compromi...

Anonymous credentials are mostly talked about in the context of age verification. We also looked how to use them to verify bots, laying the foundation for a new version of rate limiting- more refined, with more functionality, and still private!
blog.cloudflare.com/private-rate...

Anonymous credentials- rate-limiting bots and agents without compromising privacy As AI agents change how the Internet is used, they create a challenge for security. We explore how Anonymous Credentials can rate limit agent traffic and block abuse without tracking users or compromi...

Most AI traffic comes from massive shared, platforms. If one user is abusive, how do you rate-limit them without blocking everyone? IP blocks won't work.
We explore private rate limits, a way to stop abuse without tracking users.
blog.cloudflare.com/private-rate...

Update: the claimed bugfix is refuted!

This is amazing research by Nadia Heninger and her co-authors Wenyi Morty Zhang, Annie Dai, Keegan Ryan, Dave Levin and Aaron Schulman. TL;DR a huge number of satellite links over our heads are totally unencrypted. satcom.sysnet.ucsd.edu

Why Signal’s post-quantum makeover is an amazing engineering achievement | Ars Technica Happy to read this, not least because I’ve often seen the push for rapid adoption of PQ as coming from intelligence agencies seeking to sow confusion & discord; having a well researched h…

Why Signal’s post-quantum makeover is an amazing engineering achievement | Ars Technica
https://alecmuffett.com/article/117370
#EndToEndEncryption #PostQuantum #signal

Abstract. Poseidon and Poseidon2 are cryptographic hash functions crafted for efficient zero-knowledge proof systems and have seen wide adoption in practical applications. We introduce the use of the Graeffe transform in univariate polynomial solving within this line of work. The proposed method streamlines the root recovery process in interpolation attacks and achieves several orders of magnitude acceleration in practical settings, enabling a new and more efficient class of attacks against Poseidon targeting round-reduced permutations and constrained input/output instances. We release open-source code and describe our method in detail, demonstrating substantial improvements over prior approaches: reductions in wall time by a factor of 2¹³ and in memory usage by a factor of 2^(4.5). Memory-access costs for NTTs turn out to be a dominant barrier in practice. And we prove that this cost increases at least as the 4/3-power of the input size (up to logarithmic factors), which suggests the commonly used pseudo-linear cost model may underestimate the true resource requirements. This behavior contrasts with multivariate equation solving, whose main bottleneck remains finite-field linear algebra. We argue that, when selecting parameters, designers should account for interpolation-based attacks explicitly, since their practical hardness is determined by different, and sometimes stronger, resource constraints than those of multivariate techniques.

Image showing part 2 of abstract.

Graeffe-Based Attacks on Poseidon and NTT Lower Bounds (Ziyu Zhao, Antonio Sanso, Giuseppe Vitto, Jintai Ding) ia.cr/2025/1916

Improving the trustworthiness of Javascript on the Web Today, there's no way to audit a site’s client-side code as it changes, making it hard to trust sites that use cryptography. We preview a specification we coauthored that adds auditability to the web.

Javascript just became a bit more trustworthy using transparency protocols! This is a really cool deployment and shows how tk use transparency in ither places than certificates!

blog.cloudflare.com/improving-th...

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.

Registration for the Leuven Isogeny Days 6 is now open!
📅 10–12 Sept 2025 @ KU Leuven
Morning: research talks
Afternoon: brainstorming sessions
More info: www.esat.kuleuven.be/cosic/projec...
#isogeny #isocrypt #erc #postquantum

We (finally) published all the material from this course on SQIsign, including lecture slides and exercise sheets for the Sage laboratory. Available here: github.com/andreavico/S...

🖤🕯️ #graz

BGP handling bug causes widespread internet routing instability

On May 20th 2025 a BGP message was propagated that triggered some surprisingly disruptive behaviours with two major BGP implementations make up a lot of the internet.

In a new blog post, I will dissect what that message was, and my thoughts on how it happened:

blog.benjojo.co.uk/post/bgp-att...

Abstract. At the current state of the art, algebraic attacks are the most efficient method for finding preimages and collisions for arithmetization-oriented hash functions, such as the closely related primitives Poseidon/Poseidon2 and Neptune. In this paper, we revisit Gröbner basis (GB) attacks that exploit subspace trails to linearize some partial rounds, considering both sponge and compression modes. Starting from Poseidon’s original security evaluation, we identified some inaccuracies in the model description that may lead to misestimated round requirements. Consequently, we reevaluate and improve the proposed attack strategy. We find that depending on the concrete instantiation, the original security analysis of Poseidon under- or overestimates the number of rounds needed for security. Moreover, we demonstrate that GB attacks leveraging subspace trails can outperform basic GB attacks for Poseidon/Poseidon2 and Neptune. We propose a variant of the previous attack strategy that exploits a crucial difference between Poseidon/Poseidon2 and Neptune: while Poseidon’s inverse round functions have a high degree, Neptune’s inverse external rounds maintain the same degree as the forward rounds. Using this new model, we demonstrate that Neptune’s security in compression mode cannot be reduced to its security against the Constrained-Input-Constrained-Output (CICO) problem. To the best of our knowledge, this is the first time a concrete example has been provided where finding preimages is easier than solving the corresponding CICO problem. Our results emphasize the importance of considering the mode of operation in security analysis while confirming the overall security of Poseidon/Poseidon2 and Neptune against the presented algebraic attacks.

Image showing part 2 of abstract.

Poseidon and Neptune: Gröbner Basis Cryptanalysis Exploiting Subspace Trails (Lorenzo Grassi, Katharina Koschatko, Christian Rechberger) ia.cr/2025/954

Abstract. Poseidon and Poseidon2 are cryptographic hash functions designed for efficient zero-knowledge proof protocols and have been widely adopted in Ethereum applications. To encourage security research, the Ethereum Foundation announced a bounty program in November 2024 for breaking the Poseidon challenges, i.e. solving the CICO (Constrained Input, Constrained Output) problems for round-reduced Poseidon constructions. In this paper, we explain how to apply the Graeffe transform to univariate polynomial solving, enabling efficient interpolation attacks against Poseidon. We will provide an open-source code and details our approach for solving several challenges valued at $20000 in total. Compared to existing attacks, we improves 2^{13} and 2^{4.5} times in wall time and memory usage, respectively. For all challenges we solved, the cost of memory access turns out to be an essential barrier, which makes the security margin much larger than expected. We actually prove that the memory access cost for FFT grows as the 4/3-power of the input size, up to a logarithmic factor. This indicates the commonly used pseudo linear estimate may be overly conservative. This is very different from multivariate equation solving whose main bottleneck is linear algebra over finite fields. Thus, it might be preferable to choose parameters such that the best known attack is interpolation, as it presents more inherent hardness.

Image showing part 2 of abstract.

Breaking Poseidon Challenges with Graeffe Transforms and Complexity Analysis by FFT Lower Bounds (Ziyu Zhao, Jintai Ding) ia.cr/2025/950

lattirust Lattice zero-knowledge/succinct arguments, and more - lattirust

I'm happy to finally open-source lattirust, a library for lattice-based zero-knowledge/succinct arguments! Lattirust is somewhat like arkworks, but for lattices; and like lattigo, but for arguments.

➔ github.com/lattirust

We're studying user messaging behaviour to get data for a simulation for key transparency. If you have 10 minutes, please fill out this survey: survey.tugraz.at/mobile-messe... (if you are around Graz and fill it out before Thursday, you may win a free drink at the local CTF team's fundraiser!)