Production ML-DSA Verification in 350 Lines of Python

I don’t do a lot of Python, at least not in my most recent life.¹ However, I happen to have just written a production ML-DSA verifier in pure Python. It’s 350 lines of code (plus many more of tests), it supports all parameter sets, and I am pretty satisfied with it.

You can fetch it as mldsa from PyPI, thanks to William Woodruff, or you can copy-paste it: it’s a single file without dependencies and it’s dual-licensed CC0 and 0BSD. It works with Python 3.8 and later. The API is modeled after the excellent pyca/cryptography.

import mldsa

vk = mldsa.VerificationKey(verification_key_bytes)

try:
    vk.verify(signature, message)
except mldsa.VerificationError:
    print("invalid signature!")

I hope this will make it easier for some projects to migrate to post-quantum authentication, which has suddenly become more urgent than we all anticipated. In particular, I hope it will unblock some client applications that can’t use C extensions for portability reasons.

Modern Python package management, typing, and linting are also a lot more powerful² than in the early Python 3 days, and the result is a pretty readable ML-DSA verifier.

ML-DSA is actually very simple to implement with its 23-bit base field: we use Python integers (without even needing Python’s big integer support) and SHA-3 from hashlib. There are 86 lines of throat clearing, 27 lines of base field (arithmetic, centered_mod, decompose), 28 lines of sampling (sample_ntt, sample_in_ball), 39 of polynomials (Poly, NTTPoly), 25 of NTT, 30 of parsing and packing (pack, unpack, unpack_signed), 35 of key expansion (VerificationKey.__init__, public_key_hash), and 80 of actual signature verification (VerificationKey.verify, message_hash, use_hint).

Performance is… decent? 230 ML-DSA-44 verifications per second without precomputation. That’s 60x slower than Go, but not 1000x. The only optimization change I made was using integers instead of field elements in the NTT hot loop.

                             │   sec/op    │
Verify/ML-DSA-44/Whole         4.296m ± 2%
Verify/ML-DSA-65/Whole         6.509m ± 1%
Verify/ML-DSA-87/Whole         9.885m ± 3%
Verify/ML-DSA-44/Precomputed   2.635m ± 3%
Verify/ML-DSA-65/Precomputed   3.712m ± 4%
Verify/ML-DSA-87/Precomputed   5.363m ± 1%

The implementation is tested with the full reusable ML-DSA testing stack: Wycheproof test vectors and CCTV accumulated vectors, using pytest and muzoo for mutation testing. It has 96% branch coverage, and more importantly it kills every mutation I (and Claude) could think of. (ML-DSA testing techniques deserve their own article.)

Why Python?

The project started as a way to double-check the tests of the tests of my Go crypto/mldsa implementation. How do you know your tests are good and comprehensive? You add bugs (“mutations”) and you check that the tests fail. What if you skipped a check though? There won’t be any code to introduce a bug in! The obvious solution is to write a different implementation from scratch, then introduce bugs there, check that the tests catch the bugs, and then port the tests back. Duh.

Anyway, pure Python might not be particularly well-suited for cryptography that involves secrets because producing constant-time code could be difficult. However, a signature verifier involves no secrets, and Python is expressive and, most importantly, different from Go, making shared mistakes less likely.

You might want to follow me on Bluesky at @filippo.abyssdomain.expert or on Mastodon at @filippo@abyssdomain.expert, but I can’t promise any more Python.

The picture

The CENTOPASSI is not all smooth riding, that’s part of the point. However, I am a little annoyed at the local who I had called and who said this road was closed but totally doable on a motorcycle.

My work is made possible by Geomys, an organization of professional Go maintainers, which is funded by Ava Labs, Teleport, Datadog, Tailscale, and Sentry. Through our retainer contracts they ensure the sustainability and reliability of our open source maintenance work and get a direct line to my expertise and that of the other Geomys maintainers. (Learn more in the Geomys announcement.) Here are a few words from some of them!

Teleport — For the past five years, attacks and compromises have been shifting from traditional malware and security breaches to identifying and compromising valid user accounts and credentials with social engineering, credential theft, or phishing. Teleport Identity is designed to eliminate weak access patterns through access monitoring, minimize attack surface with access requests, and purge unused permissions via mandatory access reviews.

Ava Labs — We at Ava Labs, maintainer of AvalancheGo (the most widely used client for interacting with the Avalanche Network), believe the sustainable maintenance and development of open source cryptographic protocols is critical to the broad adoption of blockchain technology. We are proud to support this necessary and impactful work through our ongoing sponsorship of Filippo and his team.