Paper 2020/602

CENCPP* - Beyond-birthday-secure Encryption from Public Permutations

Arghya Bhattacharjee, Avijit Dutta, Eik List, and Mridul Nandi


Public permutations have been established as important primitives for the purpose of designing cryptographic schemes. While many such schemes for authentication and encryption have been proposed in the past decade, the birthday bound in terms of the primitive's block length $n$ has been mostly accepted as the standard security goal. Thus, remarkably little research has been conducted yet on permutation-based modes with higher security guarantees. At CRYPTO'19, Chen et al. showed two constructions with higher security based on the sum of two public permutations. Their work has sparked increased interest in this direction by the community. However, since their proposals were domain-preserving, the question of encryption schemes with beyond-birthday-bound security was left open. This work tries to address this gap by proposing $\textsf{CENCPP}^*$, a nonce-based encryption scheme from public permutations. Our proposal is a variant of Iwata's block-cipher-based mode \textsf{CENC} that we adapt for public permutations, thereby generalizing Chen et al.'s Sum-of-Even-Mansour construction to a mode with variable output lengths. Like \textsf{CENC}, our proposal enjoys a comfortable rate-security trade-off that needs $w + 1$ calls to the primitive for $w$ primitive outputs. We show a tight security level for up to $O(2^{2n/3}/w^2)$ primitive calls. While the term of $w \geq 1$ can be arbitrary, two independent keys suffice. Beyond our proposal of $\textsf{CENCPP}^*$ in a generic setting with $w + 1$ independent permutations, we show that only $\log_2(w + 1)$ bits of the input for domain separation suffice to obtain a single-permutation variant with a security level of up to $O(2^{2n/3}/w^4)$ queries.

Note: Fixed two typos in Table 1

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. Design Codes and Cryptography (to appear)
permutationprovable security
Contact author(s)
bhattacharjeearghya29 @ gmail com
avirocks dutta13 @ gmail com
eik list @ uni-weimar de
mridul nandi @ gmail com
2022-04-19: last of 5 revisions
2020-05-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Arghya Bhattacharjee and Avijit Dutta and Eik List and Mridul Nandi},
      title = {CENCPP* - Beyond-birthday-secure Encryption from Public Permutations},
      howpublished = {Cryptology ePrint Archive, Paper 2020/602},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.