Come and join the FAEST

FAEST is a digital signature algorithm designed to be secure against quantum computers. The security of FAEST is based on standard cryptographic hashes and ciphers, specifically SHA3 and AES, which are believed to remain secure against quantum adversaries.

Design

In FAEST, the secret signing key is an AES key, while the public verification key is a plaintext-ciphertext pair, obtained by encrypting a random message under the signing key. A signature consists of a non-interactive zero-knowledge proof of knowledge of an AES key which maps the message to the ciphertext. This follows the design principle of the Picnic signature scheme, except using the well-analyzed AES cipher as a one-way function instead of LowMC. FAEST also uses a new zero-knowledge proof technique called VOLE-in-the-head, which improves upon the established MPC-in-the-head paradigm.

Variants

There are several parameters controlling the instantiation of FAEST, giving differing tradoffs between security, speed, and compactness. First there’s the security parameter, which determines the overall security level of the scheme, and also affects performance. FAEST offers 3 different security levels, corresponding roughly to AES-128, AES-192 or AES-256.

Second, we have an Even-Mansour variant, where a block cipher is used as an ideal permutation by publishing its key, run on a secret input. This simplifies proving the key schedule in zero-knowledge, since it is public, but when the security parameter is 192 or 256 it requires using Rijndael with larger block sizes, as only the 128-bit block size was standardized as AES.

Third, our zero-knoweldge proof admits a communication–computation tradeoff, since it is built using SoftSpokenVOLE. This is controlled by a parameter 𝜏, with communication being roughly proportional to 𝜏. FAEST has two settings for 𝜏 for each security level: a “slow and short” setting, and a “fast but long” setting.

Performance

For 128-bit security, our optimized implementation of FAEST can sign or verify in 1.7M cycles (for signatures of size 5.9 kilobytes) or 12.8M cycles (for signatures of size 4.5 kilobytes). When using AES in Even–Mansour mode, signature size can be further reduced to 3.9 kilobytes. Here are the benchmarks for our AVX2 implementation.

FAEST Variant	Runtimes						Sizes in Bytes
	KeyGen		Sign		Verify		sk	pk	sig
	ms	Mcyc	ms	Mcyc	ms	Mcyc
128s	0.002	0.005	3.761	12.787	2.877	9.783	32	32	4506
128f	0.002	0.005	0.507	1.722	0.415	1.413	32	32	5924
192s	0.003	0.011	16.084	54.687	12.438	42.290	40	48	11260
192f	0.003	0.011	2.072	7.045	1.788	6.079	40	48	14948
256s	0.004	0.013	22.450	76.330	21.925	74.546	48	48	20696
256f	0.004	0.013	3.256	11.071	3.012	10.241	48	48	26548
EM-128s	0.002	0.005	2.766	9.403	2.176	7.398	32	32	3906
EM-128f	0.002	0.005	0.413	1.404	0.327	1.113	32	32	5060
EM-192s	0.003	0.009	11.553	39.282	10.659	36.239	48	48	9340
EM-192f	0.003	0.009	1.523	5.177	1.372	4.665	48	48	12380
EM-256s	0.004	0.013	18.372	62.465	17.570	59.738	64	64	17984
EM-256f	0.004	0.013	2.775	9.436	2.566	8.725	64	64	23476

Contact

If you want to contact us, please send an email to team@faest.info.