Paper 2003/225

Masking Based Domain Extenders for UOWHFs: Bounds and Constructions

Palash Sarkar


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

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
UOWHFdomain extenderparallel algorithm
Contact author(s)
palash @ isical ac in
2004-02-16: revised
2003-10-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Palash Sarkar},
      title = {Masking Based Domain Extenders for UOWHFs: Bounds and Constructions},
      howpublished = {Cryptology ePrint Archive, Paper 2003/225},
      year = {2003},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.