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
UOWHFdomain extenderparallel 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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2003/225}},
      url = {https://eprint.iacr.org/2003/225}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.