Lune

CRYPTO2022Top-tier venue

Overloading the Nonce: Rugged PRPs, Nonce-Set AEAD, and Order-Resilient Channels

Jean Paul Degabriele, Vukasin Karadzic

Abstract

We introduce a new security notion that lies right in between pseudorandom permutations (PRPs) and strong pseudorandom permutations (SPRPs). We call this new security notion and any (tweakable) cipher that satisfies it a rugged pseudorandom permutation (RPRP). Rugged pseudorandom permutations lend themselves to some interesting applications, have practical benefits, and lead to novel cryptographic constructions. Our focus is on variable-length tweakable RPRPs, and analogous to the encode-then-encipher paradigm of Bellare and Rogaway, we can generically transform any such cipher into different AEAD schemes with varying security properties. However, the benefit of RPRPs is that they can be constructed more efficiently as they are weaker primitives than SPRPs (the notion traditionally required by the encode-thenencipher paradigm). We can construct RPRPs using only two layers of processing, whereas SPRPs typically require three layers of processing over the input data. We also identify a new transformation that yields RUP-secure AEAD schemes with more compact ciphertexts than previously known. Further extending this approach, we arrive at a new generalized notion of authenticated encryption and a matching construction, which we refer to as nonce-set AEAD. Nonce-set AEAD is particularly well-suited in the context of secure channels, like QUIC and DTLS, that operate over unreliable transports and employ a window mechanism at the receiver's end of the channel. We conclude by presenting a generic construction for transforming a nonce-set AEAD scheme into an orderresilient secure channel. Our channel construction sheds new light on order-resilient channels and additionally leads to more compact ciphertexts when instantiated from RPRPs.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Builds on1

  1. A Security Model and Fully Verified Implementation for the IETF QUIC Record LayerAntoine Delignat-Lavaud, Cédric Fournet, Bryan Parno, Jonathan Protzenko et al.S&P 2021 · 30 citations

Related papers

  1. Efficient Instances of Docked Double Decker with AES, and Application to Authenticated EncryptionChristoph Dobraunig, Krystian Matusiewicz, Bart Mennink, Alexander TereschenkoEUROCRYPT 2025 · 4 citations
  2. Identity-Concealed Authenticated Encryption and Key ExchangeYunlei ZhaoCCS 2016 · 27 citations
  3. Succinctly-Committing Authenticated EncryptionMihir Bellare, Viet Tung HoangCRYPTO 2024 · 11 citations
  4. The Security of ChaCha20-Poly1305 in the Multi-User SettingJean Paul Degabriele, Jérôme Govinden, Felix Günther, Kenneth G. PatersonCCS 2021 · 23 citations
  5. UCX is All You Need: A Universal Transform for Committing Authenticated EncryptionMihir Bellare, Rishabh Ranjan, Nujud Senan, Basel AlomairCRYPTO 2026
Dusk over the sea between two cliffs drawn in fine vertical lines