Improved Masking for Tweakable Blockciphers with Applications to Authenticated Encryption

A popular approach to tweakable blockcipher design is via masking, where a certain primitive (a blockcipher or a permutation) is preceded and followed by an easy-to-compute tweak-dependent mask. In this work, we revisit the principle of masking. We do so alongside the introduction of the tweakable Even-Mansour construction \(\mathsf {MEM}\). Its masking function combines the advantages of word-oriented LFSR- and powering-up-based methods. We show in particular how recent advancements in computing discrete logarithms over finite fields of characteristic 2 can be exploited in a constructive way to realize highly efficient, constant-time masking functions. If the masking satisfies a set of simple conditions, then \(\mathsf {MEM}\) is a secure tweakable blockcipher up to the birthday bound. The strengths of \(\mathsf {MEM}\) are exhibited by the design of fully parallelizable authenticated encryption schemes \(\mathsf {OPP}\) (nonce-respecting) and \(\mathsf {MRO}\) (misuse-resistant). If instantiated with a reduced-round BLAKE2b permutation, \(\mathsf {OPP}\) and \(\mathsf {MRO}\) achieve speeds up to 0.55 and 1.06 cycles per byte on the Intel Haswell microarchitecture, and are able to significantly outperform their closest competitors.