International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Jooyoung Lee
John P. Steinberger
Download:
URL: http://eprint.iacr.org/2010/131
Search ePrint
Search Google
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 $H[f_1,f_2]$ is unforgeable up to $O(2^n/n)$ query complexity as long as $f_1$ and $f_2$ are unforgeable. \item $H[f_1,f_2]$ is pseudorandom up to $O(2^n/n)$ query complexity as long as $f_1$ is unforgeable and $f_2$ is pseudorandom. \item $H[f_1,f_2]$ is indifferentiable from a random oracle up to $O(2^{2n/3})$ query complexity as long as $f_1$ and $f_2$ are public random functions. \end{enumerate} To our knowledge, our result constitutes the first time $O(2^n/n)$ unforgeability has been achieved using only an unforgeable primitive of $n$-bit output length. (Yasuda showed unforgeability of $O(2^{5n/6})$ 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 $O(2^n)$.) 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 $f_1$ with a $2n$-bit key blockcipher in Davies-Meyer mode or by replacing $f_1$ with the cascade of two $2n$-bit to $n$-bit compression functions.
BibTeX
@misc{eprint-2010-23032,
  title={Multi-property-preserving Domain Extension Using Polynomial-based Modes of Operation},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography / hash functions, message authentication codes},
  url={http://eprint.iacr.org/2010/131},
  note={An extended abstract of this work was accepted for publication in Eurocrypt 2010. jlee05@ensec.re.kr 14679 received 8 Mar 2010, last revised 10 Mar 2010},
  author={Jooyoung Lee and John P. Steinberger},
  year=2010
}