Faster Than Dilithium And Much Smaller Keys: Meet FAEST

NIST approved Dilithium, Falcon and SPHINCS+ for PQC digital signatures and is now looking at other alternative signatures. One of these is the FAEST digital signature algorithm [1], and which uses symmetric key primitives:

This links directly to the security of AES128 (Level 1), AES192 (Level 3) and AES256 (Level 5).

A key pair (pk,sk) is defined as:

pk=(x,y)

and

sk=k

and where:

E_k(x)=y

Overall, E is the block cipher to use, k is the private key, and x is a plaintext block. The signature then becomes a non-interactive argument of knowledge of sk. This is similar to the Picnic method, but rather than using the MPC-in-the-Head (MPCitH) framework, it uses the VOLE-in-the-Head method [2].

The key sizes of Dilithium, Falcon and SPHINCS+ compared with a range of additional Round 1 signatures:

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

FAEST-128f                               32                 32              6,336         1 (128-bit) Symmetric
FAEST-192f                               64                 56             16,792         3 (192-bit) Symmetric
FAEST-256f                               64                 64             28,400         5 (256-bit) Symmetric

We can see that the key sizes for FAEST is much smaller than Dilithium, but where we have a larger signature. The performance for the number of cycles per operation is:

Keygen            Sign         Verify
------------------------------------------------------------
Dilithium 2           97,621          281,078       108,711 
Falcon-512        19,189,801          792,360       103,281 

FAEST-128f              92,800     27,836,800    27,836,800     
FAEST-192f             422,400     70,800,000    70,800,000  
FAEST-256f             700,800    123,648,000   123,648,000

We can see that FATEST is faster for key generation than Dilitium and much faster than Facon. The signing and verification processors, though, are much slower.

The coding is here:

FAEST Signature

A sample run for FAEST-128f is:

NAME: faest_128f
Private key size: 32
Public key size: 32
Signature size: 6336

Message: d9ec612ac5be69d8a793b6c3ab777b6631d9b6d3d184574a9cd1a40aa51adc67c1711a1d8a927de4aa17864556ebc1ab1801a8bdd246c4eb00d415473d68b4970916b7a8c93b55e50fb44b271c4d7dcfa37ce113d050999589a45f3af49826393942fe7289a039025fd1cc140585f8f95bb3297cd48a1e6fc1a94a8ad2927a76d95cb924d2a9706321d8d2b21a7c7752c60c47a0e4dc9aa22f4b9ee0df3ef87572ceae65ac3e4431dd3025a9621845026ef005280b2e57555bf322e32485e85f8bffa6de2047fb941b418da2e542a930dbc829bc4e689bb1ce079f3ca84d915bad57683735acdeb36473d245ace3ea0593fa7c03b772afde0ff1dd9273803c92
Alice Public key: d9ec612ac5be69d8a793b6c3ab777b662fe105f8dcc91d4f0fe2c5d59cf9bba1
Alice Secret key: d9ec612ac5be69d8a793b6c3ab777b6631d9b6d3d184574a9cd1a40aa51adc67
Signature (128th of signature): d9ec612ac5be69d8a793b6c3ab777b6631d9b6d3d184574a9cd1a40aa51adc67c1711a1d8a927de4aa17864556ebc1ab18
Signature verified

Conclusions

Symmetric-key-based methods have an important advantage in that they have a security base of our existing symmetric key method.

If you are interested, the other Round 2 Additional Signatures are here:

• Multivariate Signatures (4): MAYO, QR-UOV, SNOVA, and UOV (Unbalanced Oil and Vinegar)
• MPC-in-the-Head Signatures (5): MiRitH (MinRank in the Head), MQOM (MQ on my Mind), PERK, RYDE, and SDitH (Syndrome Decoding in the Head).
• Lattice-based Signatures (1): HAWK.
• Code-based Signatures (2): CROSS (Codes and Restricted Objects Signature), and LESS (Linear Equivalence).
• Symmetric-based Signatures (1): FAEST.
• Isogeny Signatures (1): SQIsign.

References

[1] Baum, C., Braun, L., de Saint Guilhem, C. D., Klooß, M., Majenz, C., Mukherjee, S., … & Scholl, P. (2023). FAEST: algorithm specifications. Technical report, National Institute of Standards and Technology.

[2] Baum, C., Braun, L., de Saint Guilhem, C. D., Klooß, M., Orsini, E., Roy, L., & Scholl, P. (2023, August). Publicly verifiable zero-knowledge and post-quantum signatures from vole-in-the-head. In Annual International Cryptology Conference (pp. 581–615). Cham: Springer Nature Switzerland.