TCR (Taurus Cybersecurity Research)

In our last blog, we talked about the PQC signature algorithms standardized and currently being evaluated by NIST. Some of the key characteristics of these algorithms are:

1. either the public key or the signature size is bigger, significantly so in some algorithms, compared to the conventional elliptic curve digital signature algorithm (ECDSA), and
2. The processing time to generate and verify a signature becomes longer than ECDSA (i.e., slow algorithms). How slow it becomes is dependent on the algorithm.

Before we go into specific numbers, we first need to define some terminology.

Security levels

All signature algorithms have several different variants based on what’s called “security levels.” There are 5 levels (category 1 ~ 5) with increasing level of security. These level are:

Table 1: Security level definition

Security level (category)	Definition (resistant to attacks equivalent to)
1	brute-force attack to break AES-128 (i.e., 2^128 possibilities)
2	brute-force hash collision search in SHA-256 (i.e., ~2^128 operations)
3	brute-force attack to break AES-192 (i.e., 2^192 possibilities)
4	brute-force hash collision search in SHA-384 (i.e., ~2^192 operations)
5	brute-force attack to break AES-256 (i.e., 2^256 possibilities)

Public key and signature sizes

How big they become reflects the underlying mathematical problems (e.g., lattice, multivariate, etc.) and the security level (1~5). As the security level increases, so do the public key and the signature size in each algorithm type. Table 2 below lists both the public key and the resulting signature size and their relative size ratio against ECDSA (indicated as “|PK|, Ratio vs. ECDSA (x)” and “|Sig|, Ratio vs. ECDSA (x)” in the table header, respectively.).

Table 2: Public key & signature size increase

Algorithm	Security Level	Public Key		Signature
		|PK| (byte)	Ratio vs. ECDSA(x)	|Sig| (byte)	Ratio vs. ECDSA (x)
ECDSA	n/a	32	1.00	64	1.00
ML_DSA_44	2	1312	x41.00	2420	x37.81
ML_DSA_65	3	1952	x61.00	3309	x51.70
ML_DSA_87	5	2592	x81.00	4627	x72.30
Falcon-512	1	897	x28.03	752	x11.75
Falcon-1024	5	1793	x56.03	1462	x22.84
DILITHIUM2	2	1312	x41.00	2420	x37.81
DILITHIUM3	3	1952	x61.00	3293	x51.45
DILITHIUM5	5	2592	x81.00	4595	x71.80
SPHINCS_SHA2_128f_simple	1	32	x1.00	17088	x267.00
SPHINCS_SHA2_128s_simple	1	32	x1.00	7856	x122.75
SPHINCS_SHA2_192f_simple	3	48	x1.50	35664	x557.25
SPHINCS_SHA2_192s_simple	3	48	x1.50	16224	x253.50
SPHINCS_SHA2_256f_simple	5	64	x2.00	49856	x779.00
SPHINCS_SHA2_256s_simple	5	64	x2.00	29792	x465.50
SPHINCS_SHAKE_128f_simple	1	32	x1.00	17088	x267.00
SPHINCS_SHAKE_128s_simple	1	32	x1.00	7856	x122.75
SPHINCS_SHAKE_192f_simple	3	48	x1.50	35664	x557.25
SPHINCS_SHAKE_192s_simple	3	48	x1.50	16224	x253.50
SPHINCS_SHAKE_256f_simple	5	64	x2.00	49856	x779.00
SPHINCS_SHAKE_256s_simple	5	64	x2.00	29792	x465.50
CROSS_RSDP_128_fast	1	77	x2.41	18432	x288.00
CROSS_RSDP_128_small	1	77	x2.41	12432	x194.25
CROSS_RSDP_128_balanced	1	77	x2.41	13152	x205.50
CROSS_RSDP_192_fast	3	115	x3.59	41406	x646.97
CROSS_RSDP_192_small	3	115	x3.59	28391	x443.61
CROSS_RSDP_192_balanced	3	115	x3.59	29853	x466.45
CROSS_RSDP_256_fast	5	153	x4.78	74590	x1165.47
CROSS_RSDP_256_small	5	153	x4.78	50818	x794.03
CROSS_RSDP_256_balanced	5	153	x4.78	53527	x386.36
CROSS_RSDPG_128_fast	1	54	x1.69	11980	x187.19
CROSS_RSDPG_128_small	1	54	x1.69	8960	x140.00
CROSS_RSDPG_128_balanced	1	54	x1.69	9120	x142.50
CROSS_RSDPG_192_fast	3	83	x2.59	26772	x418.31
CROSS_RSDPG_192_small	3	83	x2.59	20452	x319.56
CROSS_RSDPG_192_balanced	3	83	x2.59	22464	x351.00
CROSS_RSDPG_256_fast	5	106	x3.31	48102	x751.59
CROSS_RSDPG_256_small	5	106	x3.31	36454	x569.59
CROSS_RSDPG_256_balanced	5	106	x3.31	40100	x626.56
FAEST_128f	1	32	x1.00	5924	x92.56
FAEST_128s	1	32	x1.00	4506	x70.41
FAEST_192f	3	48	x1.50	14948	x233.56
FAEST_192s	3	48	x1.50	11260	x175.94
FAEST_256f	5	48	x1.50	26548	x414.81
FAEST_256s	5	48	x1.50	20696	x323.38
MAYO_1	1	1420	x44.38	454	x7.09
MAYO_2	2	4912	x153.50	186	x2.91
MAYO_3	3	2986	x93.31	681	x10.64
MAYO_5	5	5554	x173.56	964	x15.06
OV_Is	1	412160	x12880.00	96	x1.50
OV_Ip	1	278432	x8701.00	128	x2.00
OV_III	3	1225440	x38295.00	200	x3.13
OV_V	5	2869440	x89670.00	260	x4.06
OV_Is_pkc	1	66576	x2080.50	96	x1.50
OV_Ip_pkc	1	43576	x1361.75	128	x2.00
OV_III_pkc	3	189232	x5913.50	200	x3.13
OV_V_pkc	5	446992	x13968.50	260	x4.06
OV_Is_pkc_skc	1	66576	x2080.50	96	x1.50
OV_Ip_pkc_skc	1	43576	x1361.75	128	x2.00
OV_III_pkc_skc	3	189232	x5913.50	200	x3.13
OV_V_pkc_skc	5	446992	x13968.50	260	x4.06

As you can see in Table 2, both public key and signature sizes for all algorithm are bigger compared to the conventional ECDSA (the 1st row). In some algorithms, the level of increase is significant – well over 10,000x increase of public key in multivariate-based algorithms (e.g., OV) and over 1,000x increase of the signature size in CROSS. One the other hand, the level of increase of the public key is much less in SPHINCS and FAEST, and the increase of the signature is much less in MAYO and OV. In general, hash-based algorithms (e.g. SPHINCS) tend to have relatively smaller public key size but have significantly larger signature size, and multivariate-based algorithms (e.g. OV) tend to have rather large public key but the signature size is relatively small.

Equally, performance of signature generation and verification also increases compared to that of ECDSA (i.e., it becomes slower). Although we don’t show figures here, but we know this as the result of our simulation. How slow the signature generation takes varies from one algorithm to another, but some of them takes well over multiple of seconds in a generic laptop computer. On the contrary, signature verification is much more consistent across all signature algorithms in the order of a few msec.

It turns out that this blog is rather short. But in our next blog, we’ll talk about the implications of what these public key / signature size increase and slower performance mean in practice.