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 0.9 milliseconds (for signatures of size 6.5 kilobytes) or 8.1 milliseconds (for signatures of size 5 kilobytes). When using AES in Even–Mansour mode, signature size can be further reduced to 4.6 kilobytes. Here are the benchmarks for our AVX2 implementation.
| Scheme
|
Runtimes in milliseconds | Sizes in bytes | ||||
|---|---|---|---|---|---|---|
| KeyGen | Sign | Verify | sk | pk | sig | |
| FAEST-128s | 0.000641 | 8.096220 | 8.096920 | 32 | 32 | 5006 |
| FAEST-128f | 0.000638 | 0.873933 | 0.868901 | 32 | 32 | 6336 |
| FAEST-192s | 0.002215 | 19.177500 | 19.310600 | 56 | 64 | 12744 |
| FAEST-192f | 0.002223 | 1.957010 | 1.961630 | 56 | 64 | 16792 |
| FAEST-256s | 0.003340 | 26.651500 | 26.763300 | 64 | 64 | 22100 |
| FAEST-256f | 0.003342 | 3.103970 | 3.103690 | 64 | 64 | 28400 |
| FAEST-EM-128s | 0.000535 | 8.085880 | 8.046230 | 32 | 32 | 4566 |
| FAEST-EM-128f | 0.000530 | 0.854931 | 0.856541 | 32 | 32 | 5696 |
| FAEST-EM-192s | 0.001225 | 18.460400 | 18.519800 | 48 | 48 | 10824 |
| FAEST-EM-192f | 0.001218 | 1.869360 | 1.868780 | 48 | 48 | 13912 |
| FAEST-EM-256s | 0.002581 | 25.645900 | 25.871500 | 64 | 64 | 20956 |
| FAEST-EM-256f | 0.002567 | 3.035020 | 3.028910 | 64 | 64 | 26736 |
Contact
If you want to contact us, please send an e-mail to team@faest.info