Welcome to the resource topic for 2010/131
Title:
Multi-property-preserving Domain Extension Using Polynomial-based Modes of Operation
Authors: Jooyoung Lee, 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 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.
ePrint: https://eprint.iacr.org/2010/131
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .