Efficient Instantiations of Tweakable Blockciphers and Refinements to Modes OCB and PMAC

Author: Phillip Rogaway

Reference: Advances in Cryptology — Asiacrypt 2004. Lecture Notes in Computer Science, Springer-Verlag, 2004

Abstract: We describe highly efficient constructions to turn a blockcipher E into a blockcipher E where the tweak set is T = {0,1}^n x S and S is a set of tuples of integers, such as S=[0..2^{n/2}] x [0..10] x [0..10]. The cost to compute E_K^{N,s}(M) having already computed some E _K^{N,s-1}(M') is one blockcipher call plus a small and constant number of shifts, xors, and conditionals. Here s-1 means s with any one of its coordinates decremented. Our constructions work by associating to each coordinate of S a small number a in GF(2^n) and multiplying by this number when one increments that component of the tweak. We use this "powering-up" approach to refine the authenticated-encryption scheme OCB and the message authentication code PMAC, yielding variants of these algorithms, OCB1 and PMAC1, that are simpler and faster than the original schemes, yet have much simpler proofs. Our results bolster the thesis of Liskov, Rivest, and Wagner that a desirable approach for designing modes of operation is to start from a tweakable blockcipher. We elaborate on their idea, suggesting the kind of tweak space and usage-discipline that will result in an efficient scheme once the tweakable blockcipher is built out of a standard blockcipher.

Note: I now refer refer to the authenticated-encryption mechanism described in this paper as “OCB2”.

Availability: pdf or ps

Rogaway's home page.