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
	ns	cyc	ms	Mcyc	ms	Mcyc
128f	77	389	0.352	1.7	0.239	1.2	32	32	5170
128s	77	388	2.172	10.6	1.679	8.1	32	32	4066
192f	138	696	1.817	9.1	1.422	7.3	40	48	11738
192s	137	695	10.824	53.9	8.428	42.6	40	48	9410
256f	165	839	1.981	9.7	1.603	7.9	48	48	20856
256s	165	837	12.860	62.6	12.417	60.6	48	48	16626
EM-128f	83	420	0.307	1.5	0.190	0.9	32	32	4170
EM-128s	83	421	1.532	7.5	1.176	5.7	32	32	3466
EM-192f	143	726	1.136	5.7	0.845	4.3	48	48	9818
EM-192s	143	723	6.374	31.9	5.793	29.1	48	48	7874
EM-256f	190	964	1.702	8.5	1.416	6.9	64	64	18084
EM-256s	190	965	10.761	51.4	9.980	49.4	64	64	14554

Contact

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