Towards Optimally Secure Deterministic Authenticated Encryption Schemes

The public comments received for the review process for NIST (SP) 800-38A pointed out two important issues that most companies face: (1) the limited security that AES can provide due to its 128-bit block size and (2) the problem of nonce-misuse in practice. In this paper, we provide an alternative solution to these problems by introducing two optimally secure deterministic authenticated encryption (DAE) schemes, denoted as DENC1 and DENC2 respectively. We show that our proposed constructions improve the state-of-the-art in terms of security and efficiency. Specifically, DENC1 achieves a robust security level of $O(r^2\sigma^2\ell/2^{2n})$, while DENC2 attains a near-optimal security level of $O(r\sigma/2^{n})$, where $\sigma$ is the total number of blocks, $\ell$ is maximum number of blocks in each query, and $r$ is a user-defined parameter closely related to the rate of the construction. Our research centers on the development of two IV-based encryption schemes, referred to as IV1 and IV2, which respectively offer security levels of $O(r^2\sigma^2\ell/2^{2n})$ and $O(r\sigma/2^{n})$. Notably, both of our DAE proposals are nearly rate 1/2 constructions. In terms of efficiency, our proposals compare favorably with state-of-the-art AE modes on contemporary microprocessors.