Paper 2020/602

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

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

Abstract

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

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

BibTeX

@misc{cryptoeprint:2020/602,
      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{https://eprint.iacr.org/2020/602}},
      url = {https://eprint.iacr.org/2020/602}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.