MAC Precomputation with Applications to Secure Memory

In this paper we present ShMAC (Shallow MAC), a fixed-length message authentication code that allows to perform 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 PRPG or a universal hash function and can be implemented by a small shallow circuit, while ShMAC's pre-computation consists of one PRPG evaluation. An important application of this work is latency reduction in secure memory implementations. We also describe a novel architecture where a hardware-secured processor uses memory controlled by an adversary, and show the clear advantages of MAC precomputation in this context.