PAE: Towards More Efficient and BBB-Secure AE from a Single Public Permutation

Four recent trends have emerged in the evolution of authenticated encryption schemes: (1) Regarding simplicity, the adoption of public permutations as primitives allows for sparing a key schedule and the need for storing round keys; (2) using the sums of permutation outputs, inputs, or outputs has been a well-studied means to achieve higher security beyond the birthday bound; (3) concerning robustness, schemes should provide graceful security degradation if a limited amount of nonces repeats during the lifetime of a key, and (4) Andreeva et al.'s ForkCipher approach can increase the efficiency of a scheme since they can use fewer rounds per output branch compared to full-round primitives. In this work, we improve on the state of the art by combining those aspects for efficient authenticated encryption. We propose PAE, an efficient nonce-based AE scheme that employs a public permutation and one call to an XOR-universal hash function. PAE provides O(2n/3)-bit security and high throughput by combining forked public-permutation-based variants of nEHtM and an Encrypted Davies-Meyer. Thus, it can use a single, in part round-reduced, public permutation for most operations, spare a key schedule, and guarantee security beyond the birthday bound even under limited nonce reuse.