前回のブログでは、NISTによって標準化された、また現在評価が進められているPQC署名アルゴリズムについて取り上げました。これらのアルゴリズムの主な特徴は以下の通りとなります。
- 従来の楕円曲線デジタル署名アルゴリズム（ECDSA）と比較して、公開鍵または署名のサイズがより大きく、一部のアルゴリズムではその差が顕著である。
- 署名の生成および検証にかかる処理時間がECDSAよりも長くなる（つまり、処理速度の遅いアルゴリズム）。どの程度遅くなるかは、アルゴリズムによって異なります。
具体的な数値について触れる前に、まずいくつかの用語を定義しておく必要があります。
セキュリティーレベル
すべての署名アルゴリズムには、「セキュリティレベル」と呼ばれるカテゴリーの定義に基づいて、いくつかの異なるバリエーションが存在します。セキュリティレベルは5段階（カテゴリー1～5）あり、レベルが上がるにつれてセキュリティ強度が高くなります。これらのレベルは以下の通りです：
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) |
公開鍵と署名サイズ
公開鍵と署名の大きさは、各アルゴリズムの基となる数学的問題（格子、多変量など）およびセキュリティレベル（1～5）によって決まります。セキュリティレベルが上がるにつれて、各アルゴリズムタイプにおける公開鍵および署名のサイズも大きくなります。以下の表2には、公開鍵とそれによって生成される署名のサイズ、およびECDSAに対する相対的なサイズの比較が記されています（表の見出しでは、それぞれ「|PK|、Ratio vs. ECDSA (x)」および「|Sig|、Ratio vs. ECDSA (x)」と表記されています）。
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 | ||
表2からわかるように、すべてのアルゴリズムにおいて、公開鍵および署名のサイズは、従来のECDSA（1列目）と比較して大きくなっています。一部のアルゴリズムでは、その増加の程度が顕著であり、多変量ベースのアルゴリズム（OVなど）では公開鍵のサイズが1万倍以上、CROSSでは署名サイズが千倍以上にもなっています。一方、SPHINCSやFAESTでは公開鍵の増加幅ははるかに小さく、MAYOやOVでは署名サイズの増加幅がはるかに小さくなっています。一般的に言って、ハッシュベースのアルゴリズム（SPHINCS等）では公開鍵は比較的に小さいが署名サイズが大きくなり、多変量ベースのアルゴリズム（OV等）では公開鍵は大きい割には署名サイズが小さめ、という特徴があります。
同様に、署名の生成および検証の処理時間も、ECDSAと比較して増加する（処理が遅くなる）傾向があります。ここでは図には示していませんが、シミュレーションの結果からこのことが分かっています。署名生成にかかる時間はアルゴリズムによって異なりますが、一般的なノートパソコンでは、一つの署名生成の処理に数秒をはるかに超えるものもあります。対照的に、署名の検証時間はすべての署名アルゴリズムでほぼ一貫しており、数ミリ秒程度となっています。
今回のブログは比較的短くなりましたが、次回のブログでは、こうした公開鍵や署名のサイズ増加、およびパフォーマンスの低下が意味するところについて解説します。
Leave a Reply