International Association
for Cryptologic Research

Public permutations have been established as valuable primitives since the absence of a key schedule compared to block ciphers alleviates cryptanalysis. While many permutation-based authentication and encryption schemes 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. Only recently at CRYPTO'19, Chen et al showed two constructions with higher security based on the sum of two public permutation. 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 CENCPP, a nonce-based encryption scheme from public permutations. Our proposal is a variant of Iwata's block-cipher-based mode 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 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 w can be arbitrary, two independent keys suffice; moreover, although we propose CENCPP first 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 that still maintains a security level of up to O(2^(2n/3)/w^4) queries.