Paper 2016/1188

Farfalle: parallel permutation-based cryptography

Guido Bertoni, Joan Daemen, Seth Hoffert, Michaël Peeters, Gilles Van Assche, and Ronny Van Keer

Abstract

In this paper, we introduce Farfalle, a new permutation-based construction for building a pseudorandom function (PRF). The PRF takes as input a key and a sequence of arbitrary-length data strings, and returns an arbitrary-length output. It 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, a very efficient instance of Farfalle based on Keccak-p[1600] permutations and formulate concrete security claims against classical and quantum adversaries. The permutations in the compression and expansion layers of Kravatte have only 6 rounds apiece and the rolling functions are lightweight. We provide a rationale for our choices and report on software performance.

Note: Updated Farfalle and Kravatte after third-party cryptanalysis

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
pseudorandom functionpermutation-based cryptoKeccak
Contact author(s)
farfalle @ noekeon org
History
2017-12-04: last of 3 revisions
2017-01-01: received
See all versions
Short URL
https://ia.cr/2016/1188
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/1188,
      author = {Guido Bertoni and Joan Daemen and Seth Hoffert and Michaël Peeters and Gilles Van Assche and Ronny Van Keer},
      title = {Farfalle: parallel permutation-based cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2016/1188},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/1188}},
      url = {https://eprint.iacr.org/2016/1188}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.