Paper 2010/131

Multi-property-preserving Domain Extension Using Polynomial-based Modes of Operation

Jooyoung Lee and John Steinberger

Abstract

In this paper, we propose a new double-piped mode of operation for multi-property-preserving domain extension of MACs~(message authentication codes), PRFs~(pseudorandom functions) and PROs~(pseudorandom oracles). Our mode of operation performs twice as fast as the original double-piped mode of operation of Lucks while providing comparable security. Our construction, which uses a class of polynomial-based compression functions proposed by Stam, makes a single call to a $3n$-bit to $n$-bit primitive at each iteration and uses a finalization function $f_2$ at the last iteration, producing an $n$-bit hash function $H[f_1,f_2]$ satisfying the following properties. \begin{enumerate} \item $$ is unforgeable up to $$ query complexity as long as $$ and $$ are unforgeable. \item $$ is pseudorandom up to $$ query complexity as long as $$ is unforgeable and $$ is pseudorandom. \item $$ is indifferentiable from a random oracle up to $$ query complexity as long as $$ and $$ are public random functions. \end{enumerate} To our knowledge, our result constitutes the first time $$ unforgeability has been achieved using only an unforgeable primitive of $$-bit output length. (Yasuda showed unforgeability of $$ for Lucks' construction assuming an unforgeable primitive, but the analysis is sub-optimal; in this paper, we show how Yasuda's bound can be improved to $$.) In related work, we strengthen Stam's collision resistance analysis of polynomial-based compression functions (showing that unforgeability of the primitive suffices) and discuss how to implement our mode by replacing $$ with a $$-bit key blockcipher in Davies-Meyer mode or by replacing $$ with the cascade of two $$-bit to $$-bit compression functions.