At present, CRYSTALS (Cryptographic Suite for Algebraic Lattices) supports two quantum robust mechanisms: Kyber for key-encapsulation mechanism (KEM) and key exchange; and Dilithium for a digital signature algorithm. 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 3 is equivalent to a 128-bit signature, and is perhaps the starting point for an implementation This page shows a benchmark for Dilithium 2, Dilithium 3 and Dilithium 5.
CRYSTALS Dilithium (Lattice) - Digital Signature - - Speed test |
Outline
NIST are now assessing just three methods for digital signatures: CRYSTALS-DILITHIUM (led by Vadim Lyubashevsky), FALCON (led by Thomas Present) and RAINBOW (led by Jintai Ding). The three main implementations for Dilithium are: Dilithium 2 (2479 byte - 19,832 bit - signature), Dilithium 3 (3,352 byte - 26,816 bit - signature) and Dilithium 5 (4,654 byte - 37,232 bit - signature). Overall, Dilithium 3 is equivalent to a 128-bit signature and is perhaps the starting point for an implementation. The following does a test for Dilithium 2:
#include stddef.h #include stdint.h #include stdlib.h #include stdio.h #include "cpucycles.h" #include "speed_print.h" static int cmp_uint64(const void *a, const void *b) { if(*(uint64_t *)a < *(uint64_t *)b) return -1; if(*(uint64_t *)a > *(uint64_t *)b) return 1; return 0; } static uint64_t median(uint64_t *l, size_t llen) { qsort(l,llen,sizeof(uint64_t),cmp_uint64); if(llen%2) return l[llen/2]; else return (l[llen/2-1]+l[llen/2])/2; } static uint64_t average(uint64_t *t, size_t tlen) { size_t i; uint64_t acc=0; for(i=0;i < tlen;i++) acc +=t[i]; return acc /tlen; } void print_results(const char *s, uint64_t *t, size_t tlen) { size_t i; static uint64_t overhead=-1; if(tlen < 2) { fprintf(stderr, "ERROR: Need a least two cycle counts!\n"); return; } if(overhead == (uint64_t)-1) overhead = cpucycles_overhead(); tlen--; for(i=0;i<itlen;++i) t[i] = t[i+1] - t[i] - overhead; printf("%s\n", s); printf("median: %llu cycles/ticks\n", (unsigned long long)median(t, tlen)); printf("average: %llu cycles/ticks\n", (unsigned long long)average(t, tlen)); printf("\n"); }
A sample run of Dilithium2 shows:
polyvec_matrix_expand: median: 217108 cycles/ticks average: 282541 cycles/ticks poly_uniform_eta: median: 4516 cycles/ticks average: 5706 cycles/ticks poly_uniform_gamma1: median: 8152 cycles/ticks average: 24239 cycles/ticks poly_ntt: median: 5360 cycles/ticks average: 12331 cycles/ticks poly_invntt_tomont: median: 6828 cycles/ticks average: 15857 cycles/ticks poly_pointwise_montgomery: median: 1060 cycles/ticks average: 2760 cycles/ticks poly_challenge: median: 1936 cycles/ticks average: 2545 cycles/ticks Keypair: median: 385184 cycles/ticks average: 722677 cycles/ticks Sign: median: 1176130 cycles/ticks average: 1541188 cycles/ticks Verify: median: 289880 cycles/ticks average: 307506 cycles/ticks
The code compiles to “test_dilithium2”, and which is a Linux build. To run just run the executable: