Masking Based Domain Extenders for UOWHFs: Bounds and Constructions

Palash Sarkar

Paper 2003/225

Masking Based Domain Extenders for UOWHFs: Bounds and Constructions

Palash Sarkar

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.

Note: Substantial revised version

Metadata

Available format(s): PS
Publication info: Published elsewhere. Unknown where it was published
Keywords: UOWHF domain extender parallel algorithm
Contact author(s): palash @ isical ac in
History: 2004-02-16: revised; 2003-10-28: received; See all versions
Short URL: https://ia.cr/2003/225
License: CC BY

BibTeX

@misc{cryptoeprint:2003/225,
      author = {Palash Sarkar},
      title = {Masking Based Domain Extenders for {UOWHFs}: Bounds and Constructions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2003/225},
      year = {2003},
      url = {https://eprint.iacr.org/2003/225}
}