International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Masking Based Domain Extenders for UOWHFs: Bounds and Constructions

Authors:
Palash Sarkar
Download:
URL: http://eprint.iacr.org/2003/225
Search ePrint
Search Google
Abstract: We study the class of masking based domain extenders for UOWHFs. Our first contribution is to show that any correct masking based domain extender for UOWHF which invokes the compression UOWHF $s$ times must use at least $\lceil\log s\rceil$ masks. As a consequence we obtain the optimality of Shoup's algorithm among the class of masking based domain extenders. Our second contribution is to present a new parallel domain extender for UOWHF. The new algorithm obtains an asymptotically optimal speed-up over the sequential algorithm and the key expansion is almost everywhere optimal, i.e., it is optimal for almost all possible number of invocations of the compression UOWHF.
BibTeX
@misc{eprint-2003-11938,
  title={Masking Based Domain Extenders for UOWHFs: Bounds and Constructions},
  booktitle={IACR Eprint archive},
  keywords={UOWHF, domain extender, parallel algorithm},
  url={http://eprint.iacr.org/2003/225},
  note={ palash@isical.ac.in 12464 received 27 Oct 2003, last revised 16 Feb 2004},
  author={Palash Sarkar},
  year=2003
}