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…