Farfalle: parallel permutation-based cryptography

Farfalle is a new construction for building a deck function. The deck function takes as input a key and a sequence of arbitrary-length data strings, and returns an arbitrary-length output. To an adversary not knowing the key, these output bits looks like independent uniformly-drawn random bits.

The Farfalle construction

Farfalle has a compression layer and an expansion layer, each involving the parallel application of a permutation. The construction also makes use of LFSR-like rolling functions for generating input and output masks and for updating the inner state during expansion. On top of the inherent parallelism, Farfalle instances can be very efficient because the construction imposes less requirements on the underlying primitive than, e.g., the duplex construction or typical block cipher modes. Farfalle has an incremental property: compression of common prefixes of inputs can be factored out.

Thanks to its input-output characteristics, Farfalle is really versatile. We specify simple modes on top of it for authentication, encryption and authenticated encryption, as well as a wide block cipher mode.

As a showcase, we present Kravatte and Xoofff, two very efficient instances of Farfalle based on the Keccak-p[1600] and Xoodoo permutations, respectively. We formulate concrete security claims against classical and quantum adversaries. The permutations in the compression and expansion layers of Kravatte and Xoofff have only 6 rounds apiece and the rolling functions are lightweight. In the paper, we provide a rationale for our choices and report on software performance.

For more information, please refer to: