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.
Rogaway's home page.