International Association
for Cryptologic Research

This talk relates to two ongoing works where we introduce a new security notion that lies right in between pseudorandom permutations (PRPs) and strong pseudorandom permutations (SPRPs). We refer to this new security notion and any (tweakable) cipher that satisfies it, as a rugged pseudorandom permutation (RPRP). Rugged pseudorandom permutations lend themselves to some interesting applications, have practical benefits, and lead to novel cryptographic constructions. Analogous to the encode-then-encipher paradigm first proposed by Bellare and Rogaway and later extended by Shrimpton and Terashima, we can transform a variable-length tweakable RPRP into an AEAD scheme. However, we can construct RPRPs more efficiently as they are weaker primitives than SPRPs (the notion traditionally required by the encode-then-encipher paradigm). We can construct RPRPs using two-pass schemes, whereas SPRPs typically require three passes over the input data. We also identify new transformations that yield nonce-hiding AEAD schemes with more compact ciphertexts than previously known. Further extending this approach, we arrive at a new generalised notion of authenticated encryption and matching constructions, which we refer to as nonce-set AEAD. Nonce-set AEAD is particularly well-suited to realise modern secure channels, such as those used in QUIC and DTLS, which employ a windowing mechanism at the receiver end of the channel. Finally, we show how to use tweakable RPRPs to construct an efficient onion encryption scheme for Tor with significantly improved security and good performance.