Ingredients
Ingredients for the FAEST:

To build FAEST, we use a oneway function defined using a block cipher. A public verification key consists of a plaintextciphertext pair (x, y), while the private signing key is the corresponding key k (together with the plaintext x). In FAEST128, the ciphertext is defined as the AES encryption of the plaintext x using the key k. I.e., y = AES128(x, k). FAEST192 and FAEST256 are similar, except that two plaintext/ciphertext pairs are generated for the same key, since AES has a block size of 128 bits even when the key is larger. A signature is a zeroknowledge (ZK) proof, demonstrating knowledge of the key k.
Using AES as the OWF has been done in previous signature candidates such as BBQ, Banquet and Limbo. Similar to BBQ and followups, FAEST exploits that the only nonlinear operation of the AES cipher is the SBox, which is an inversion over a small field (and can be efficiently proven in ZK). To avoid dividing by zero, we require that the input of each Sbox during key scheduling and encryption is nonzero. This restricts us to a subset of all possible keys, but the analysis in BBQ showed that this has only a very minor impact on security.
FAEST can additionally use AES in EvenMansour (EM) mode, where AES is used as an ideal permutation, by revealing the AES key as part of the public key. FAESTEM proves that it knows a key k such that k, encrypted using AES with a fixed publicly known key x, yields output k ⊕ y. That is, y = k ⊕ AES128(k, x). The advantage of FAESTEM is that the key expansion need not be proven in ZK since the AES key x is public information. This reduces the proof and therefore signature size. Using EM requires the block size to match the key size, so for 192 and 256 bit security FAESTEM uses on Rijndael192 and Rijndael256, the 192 and 256 bit block size versions of Rijndael. (Only the 128 bit block size version of Rijndael was standardized as AES.)

QuickSilver ZeroKnowledge Proof
The concrete ZK proof system in FAEST is based on QuickSilver. QuickSilver requires a setup where a vector oblivious linear evaluation (VOLE) correlation has been distributed between the prover and the verifier, which allows the prover to homomorphically commit to its witness. After committing to the witness using VOLE, the prover in QuickSilver can prove arbitrary lowdegree constraints about the witness, with communication complexity independent of the number of constraints. Moreover, the computation needed to generate or verify the proof is very lightweight. FAEST relies on the observation that the proof remains sound if the prover learns the verifier’s portion of the VOLE correlation after the prover sent all QuickSilver proof messages.

QuickSilver (like other VOLEbased ZK proof systems) has the disadvantage of only supporting a single, designated verifier, since it requires an interactive protocol to generate the VOLE correlation, and the soundness of the proof requires the verifier’s VOLE output to be secret. With VOLEintheHead, a VOLElike correlation can instead be generated from a publiccoin protocol based on SoftSpokenVOLE, with its base oblivious transfers replaced by hashbased commitments. Using commitments instead of oblivious transfers requires the verifier’s part of the VOLE correlation to be revealed to the prover when the commitments are later opened. Since this is only done after the QuickSilver proof messages have been sent, this does not affect soundness of the proof. The resulting, publicly verifiable proof system bears a resemblance to MPCintheHead, so we call this approach VOLEintheHead.

A pinch of salt