Paper 2010/131
Multipropertypreserving Domain Extension Using Polynomialbased Modes of Operation
Jooyoung Lee and John Steinberger
Abstract
In this paper, we propose a new doublepiped mode of operation for multipropertypreserving 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 doublepiped mode of operation of Lucks while providing comparable security. Our construction, which uses a class of polynomialbased 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 suboptimal; 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 polynomialbased 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 DaviesMeyer mode or by replacing $f_1$ with the cascade of two $2n$bit to $n$bit compression functions.
Metadata
 Available format(s)
 Category
 Secretkey cryptography
 Publication info
 Published elsewhere. An extended abstract of this work was accepted for publication in Eurocrypt 2010.
 Keywords
 hash functionsmessage authentication codes
 Contact author(s)
 jlee05 @ ensec re kr
 History
 20100311: revised
 20100309: received
 See all versions
 Short URL
 https://ia.cr/2010/131
 License

CC BY
BibTeX
@misc{cryptoeprint:2010/131, author = {Jooyoung Lee and John Steinberger}, title = {Multipropertypreserving Domain Extension Using Polynomialbased Modes of Operation}, howpublished = {Cryptology ePrint Archive, Paper 2010/131}, year = {2010}, note = {\url{https://eprint.iacr.org/2010/131}}, url = {https://eprint.iacr.org/2010/131} }