$\sharp \textsf {Pencil}$: A Domain-Extended Committing BBB PRF for Strengthening GCM

We consider the problem of constructing efficient committing pseudorandom functions with Beyond-Birthday-Bound (BBB) security from blockciphers. More specifically, we are interested in expanding pseudorandom functions (PRF) whose domain is roughly twice that of the underlying blockcipher. The main motivation behind our work is to construct an AES-based key derivation function (KDF) that can be combined with GCM in order to improve its security bound, accommodate larger nonces that can be generated randomly without risking collisions, and make it a committing AEAD scheme. NIST has recently announced a pre-draft call for comments to standardise AEAD schemes that can encrypt larger amounts of data and admit larger nonces. The call lists two approaches. The first is to define an analogue of GCM using a 256-bit blockcipher, and the second is based on a recent proposal by Gueron, to extend GCM with a key derivation function (KDF) called $\mathsf{DNDK}$ to increase its security. The latter has clear benefits in terms of backwards compatibility and is likely to be the preferred interim solution. Moreover, $\mathsf{DNDK}$-$\mathsf{GCM}$ is already deployed in production at Meta. $\mathsf{DNDK}$ is essentially a BBB-secure expanding weak pseudorandom function with a domain size of 192 bits realised from AES. We here propose an alternative AES-based KDF called $\mathsf{♯Pencil}$ with comparable efficiency but stronger provable security guarantees. Specifically, $\mathsf{♯Pencil}$ is a full PRF, whereas $\mathsf{DNDK}$ is only a weak PRF, which allows us to prove the $\mathsf{♯Pencil}$-$\mathsf{GCM}$ composition secure as an AEAD scheme. Our most technically challenging result is to show that $\mathsf{♯Pencil}$ is committing, whereas $\mathsf{DNDK}$ claims this property without proof. Finally, in contrast to $\mathsf{DNDK}$ and other alternatives, $\mathsf{♯Pencil}$ can be safely used with arbitrary (non-random) nonces and remains committing even when the nonce is not included as part of the ciphertext.