The Wonderful World of Dilithium (aka ML-DSA) and The Fiat Shamir Method
When Zero Knowledge Proof Methods Become Digital Signatures
Did you know that Zero Knowledge Proof (ZKP) methods are now being used for Digital Signatures? Well, I’ll explain in this article and where we will meet two of the core builders of scaling ZKP methods into a quantum robust world of digital signatures: Vadim Lyubashevsky and Chris Peikert.
Introduction
Over the past year, I’ve had some great talks with the people who built the foundation of lattice-based cryptography. These include Vadim Lyubashevsky and Chris Peiker. Neither of them actually knew how significant their work was going to be, but in the end, it is now generally lattice-based methods that are going to be used to replace our existing RSA and ECC (Elliptic Curve Cryptography) methods. This includes ML-KEM (aka CRYSTALS Kyber — FIPS 203), ML-DSA (aka Dilithium — FIPS 204) and FN-DSA (aka FALCON — FIPS 206). These methods are generally faster than the other PQC techniques and generally have manageable size keys.
CRYSTALS Dilithium uses lattice-based Fiat-Shamir schemes, and produces one of the smallest signatures of all the post-quantum methods, and with relatively small public and private key sizes. The three main implements for the parameters used are: Dilithium 2, Dilithium 3 and Dilithium 5. Overall, Dilithium 2 is equivalent to a 128-bit signature and is perhaps the starting point for an implementation. CRYSTALS Dilithium has now been standardized by NIST as FIPS 204 (ML-DSA), and defined as ML-DSA-44 (Dilithium 2), ML-DSA-65 (Dilithium 3), and ML-DSA-87 (Dilithium 5).
The Fiat Shamir Method
Overall, the Fiat-Shamir method is a Zero Knowledge Proof method that allows Peggy to generate her own proof of knowledge without Victor sending her a challenge. In the following, Peggy has a secret (x) and creates a public value (x.G), and where G is a base point on an elliptic curve.
Peggy will then generate a random scalar value of v, and produce a hash (c) of the base point G, v.G, x.G and her user ID (userID). She then computes:
r= v -c.x (mod n)
and where n is the order of the curve. She sends this value to Victor, and who checks that:
v.G = r.G + c (x.G).
If they match, Peggy has proven that she knows the value of x. For digital signatures, the secret is obviously Peggy’s private key, and the public value is her public key. And, rather than her userID, she will sign a message (M).
So, now let’s meet two people who applied this method to the world of lattice cryptography: Vadim Lyubashevsky and Chris Peikert.
Vadim Lyubashevsky
Vadim Lyubashevsky is a cryptographer at IBM Research Europe in Zurich. He received his PhD from the University of California, San Diego in 2008. His core research focus is around lattice-based methods, and especially in areas of practical lattice encryption, digital signatures and privacy-preserving primitives. Along with Chris Peiker and Oded Regev (the inventor of LWE), he published a classic paper entitled “On ideal lattices and learning with errors over rings”, which has been used as a foundation for lattice methods within post-quantum cryptography. Vadim has worked in many areas of cryptography, including Zero Knowledge Proofs, Blind Signatures and Multiparty Computation. Here he is:
A classic he wrote outlines how the Fiat-Shamir method can be used to create the signatures we see in Dilithium [1]:
and with [2]:
Chris Peikert
Chris is a Professor in the Computer Science and Engineering department at the University of Michigan. He completed his PhD in 2006 at the MIT Computer Science and AI Laboratory under the mentorship of Silvio Micali. He received a Test of Time award at Crypto 2008 for a paper entitled “A Framework for Efficient and Composable Oblivious Transfer” and also a TCC Test of Time award for his paper on “Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices,” in 2006. In 2024, Chris was elected as a Fellow of the International Association for Cryptologic Research and is seen as one of the world leaders in lattice-based methods. Here he is:
Along with Vadim, Chris laid down many of the core principles involved in lattice-based cryptography, including with [4]:
and with the mighty Craig Gentry [5]:
Dilithium (aka ML-DSA)
Dilithium uses the hardness of finding short vectors in lattices and uses the e “Fiat-Shamir with Aborts” approach [1, 2, 3]. For keygen, we derive the public key (vk) from the secret key (sk) and an error matrix (e) for a classic LWE (learning with errors) approach:
and where A is a matrix of k by l, and t is a vector of k elements. These are all taken(mod q), and where q is a prime number. The verifying key will then be (A,vk), and the signing key will be sk. To sign, we create a short ephemeral secret (r) and a message (msg), and create a challenge commitment of (and where e′ is a sample of e):
Next, we compute:
If z is too large, we try again. In the end, we return (w,z) as the signature. This is a classic Fiat-Shamir sigma method with aborts. The abort is used to stop the signing key from being revealed. To verify, we first check that z is small. Next, we compute:
and then check that
This works because the error value will be relatively small:
Key sizes
The key sizes for Dilithium are larger than RSA and ECC, but are still manageable, with a 1,312-byte public key, 2,528-byte private key, and a 2,420-byte signature for ML-DSA-44:
Method Public key size Private key size Signature size Security level
------------------------------------------------------------------------------------------------------
Crystals Dilithium 2 (Lattice) 1,312 2,528 2,420 1 (128-bit) Lattice
Crystals Dilithium 3 1,952 4,000 3,293 3 (192-bit) Lattice
Crystals Dilithium 5 2,592 4,864 4,595 5 (256-bit) Lattice
Falcon 512 (Lattice) 897 1,281 690 1 (128-bit) Lattice
Falcon 1024 1,793 2,305 1,330 5 (256-bit) Lattice
Sphincs SHA256-128f Simple 32 64 17,088 1 (128-bit) Hash-based
Sphincs SHA256-192f Simple 48 96 35,664 3 (192-bit) Hash-based
Sphincs SHA256-256f Simple 64 128 49,856 5 (256-bit) Hash-based
RSA-2048 256 256 256
ECC 256-bit 64 32 256For a TLS packet, it would thus take two packets to send a Dilithium 2 signature — and which shouldn’t be too much of an overhead. It is really the performance that Dilithium shines, and where it is much faster than most other PQC methods for key generation. The following is an assessment for cycles per second for various operations [here]:
Method Keygen Sign Verify
------------------------------------------------------------
Dilithium 2 300,751 1,081,174 327,362 (Unoptimized, Ref, Skylake)
Dilithium 3 544,232 1,713,783 522,267
Dilithium 5 819,475 2,383,399 871,609
Falcon-512 19,872,000 386,678 82,339 (Intel e5-8259U 2.3GHz)
Falcon-1024 63,135,000 961,208 205,128
SPHINCS+128f 9,649,130 239,793,806 12,909,924 * (3.1 GHz Intel Xeon E3-1220 CPU (Haswell)
SPHINCS+192f 14,215,518 386,861,992 19,876,926
SPHINCS+256f 36,950,136 763,942,250 19,886,032Dilithium is thus a good all-rounder, and that is one of the reasons that it was selected by NIST for the FIPS 204 standard.
Coding
In order to demonstrate the method, I have created a JavaScript program here:
The code for this is [here]:
<script type="application/javascript" src="/dilithium.js"></script>
<style>
.dropdown {
font-size: 16px;
border: 2px solid grey;
width: 100%;
border-left: 12px solid green;
border-radius: 5px;
padding: 14px;
}
pre {
font-size: 16px;
border: 2px solid grey;
width: 100%;
border-left: 12px solid green;
border-radius: 5px;
padding: 14px;
}
textarea {
font-size: 20px;
border: 2px solid grey;
width: 100%;
border-radius: 5px;
padding: 14px;
}
</style>
<div class="indented">
<h2>ML-DSA</h2>
<table width="100%">
<tr>
<th width="15%" valign="top">Key size</th>
<td style="text-align:left">
<p>
<input id="genkey" class="btn btn-large btn-primary" type="button" value="Re-generate Keys" />
</p>
</td>
</tr>
<tr>
<th width="15%" valign="top">Message</th>
<td>
<textarea cols="20" id="message" name="message" rows="2" style="width:100%"></textarea>
</td>
</tr>
<tr>
<th width="15%">Method</th>
<td>
<div class="dropdown">
<select name="method" id="method">
<option value="2">ML-DSA-44</option>
<option value="3">ML-DSA-65</option>
<option value="5">ML-DSA-87</option>
</select>
</div>
</td>
</tr>
<tr>
<th width="15%" valign="top">Signature</th>
<td>
<pre id="sign" valign="top"></pre>
</td>
</tr>
<tr>
<th width="15%" valign="top">Verify</th>
<td>
<pre id="verify"></pre>
</td>
</tr>
</table>
<h2>Generated keys</h2>
<table width="100%">
<tr>
<th width="15%" valign="top">Public Key</th>
<td>
<pre id="publicKey"></pre>
</td>
</tr>
<tr>
<th width="15%" valign="top">Private Key</th>
<td>
<pre id="privateKey"></pre>
</td>
</tr>
</table>
</div>
<script type="application/javascript">
(async function () {
var privateKey, publicKey;
for (let key of Object.keys(DilithiumAlgorithm)) {
window[key] = DilithiumAlgorithm[key];
}
function genKey() {
const level = DilithiumLevel.get(Number(document.getElementById('method').value));
const keyPair = DilithiumKeyPair.generate(level);
privateKey = keyPair.getPrivateKey();
document.getElementById('privateKey').innerText = "Length: "+privateKey.getBytes().length+'\n';
document.getElementById('privateKey').innerText += privateKey.toHex();
publicKey = keyPair.getPublicKey();
document.getElementById('publicKey').innerText = "Length: "+publicKey.getBytes().length+'\n';
document.getElementById('publicKey').innerText+= publicKey.toHex();
}
function sign() {
const level = DilithiumLevel.get(Number(document.getElementById('method').value));
const message = document.getElementById("message").value;
signature = privateKey.sign(message);
document.getElementById('sign').innerText= "Length: "+signature.getBytes().length+'\n';
document.getElementById('sign').innerText += signature.toHex();
valid = publicKey.verifySignature(message, signature);
if (valid) {
document.getElementById('verify').innerText = "Valid Signature";
} else {
document.getElementById('verify').innerText = "Invalid Signature";
}
}
document.getElementById("message").value = "Hello 1234";
genKey();
sign();
document.getElementById("genkey").addEventListener("click", genKey);
document.getElementById("genkey").addEventListener("click", sign);
document.getElementById("message").addEventListener("input", sign);
})();
</script>OpenSSL
The foundation of much of our online security is typically built from OpenSSL, and this week a new version — 3.15.0 — will be released and which integrates ML-DSA:
Conclusions
No excuses any more. The methods for post-quantum cryptography (PQC) are now defined, and we now have to look at migrating our existing key exchange and digital signature methods.
References
[1] Lyubashevsky, V. (2009, December). Fiat-Shamir with aborts: Applications to lattice and factoring-based signatures. In International Conference on the Theory and Application of Cryptology and Information Security (pp. 598–616). Berlin, Heidelberg: Springer Berlin Heidelberg.
[2] Lyubashevsky, V. (2012, April). Lattice signatures without trapdoors. In Annual International Conference on the Theory and Applications of Cryptographic Techniques (pp. 738–755). Berlin, Heidelberg: Springer Berlin Heidelberg.
[3] Güneysu, T., Lyubashevsky, V., & Pöppelmann, T. (2012). Practical lattice-based cryptography: A signature scheme for embedded systems. In Cryptographic Hardware and Embedded Systems–CHES 2012: 14th International Workshop, Leuven, Belgium, September 9–12, 2012. Proceedings 14 (pp. 530–547). Springer Berlin Heidelberg.
[4] Lyubashevsky, V., Peikert, C., & Regev, O. (2010). On ideal lattices and learning with errors over rings. In Advances in Cryptology–EUROCRYPT 2010: 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, May 30–June 3, 2010. Proceedings 29 (pp. 1–23). Springer Berlin Heidelberg.
[5] Gentry, C., Peikert, C., & Vaikuntanathan, V. (2008, May). Trapdoors for hard lattices and new cryptographic constructions. In Proceedings of the fortieth annual ACM symposium on Theory of computing (pp. 197–206).
