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