Multiproperty-Preserving Domain Extension Using Polynomial-Based Modes of Operation

Abstract

In this paper, we propose a new double-piped mode of operation for multiproperty-preserving domain extension of message authentication codes (MACs), pseudorandom functions (PRFs), and pseudorandom oracles (PROs). 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 f(1) 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. 1) 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. 2) 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. 3) H [f(1), f(2)] is indifferentiable from a random oracle up to O(2(n)/3) query complexity as long as and f(1) are f(2) public random functions. To our knowledge, our result constitutes the first time O(2(n)/n) unforgeability that 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, as noticed by us and others; in this paper, we also 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 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.