Date Added: Jul 2009
The authors present ShMAC (Shallow MAC), a fixed input length message authentication code that performs most of the computation prior to the availability of the message. Specifically, ShMAC's message-dependent computation is much faster and smaller in hardware than the evaluation of a PseudoRandom Permutation (PRP), and can be implemented by a small shallow circuit, while its precomputation consists of one PRP evaluation. A main building block for ShMAC is the notion of Strong Differential Uniformity (SDU), which they introduce, and which may be of independent interest. They present an efficient SDU construction built from previously considered differentially uniform functions.