Cryptology ePrint Archive: Report 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.

Category / Keywords: UOWHF, domain extender, parallel algorithm

Date: received 27 Oct 2003, last revised 16 Feb 2004

Contact author: palash at isical ac in

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

Note: Substantial revised version

Version: 20040216:102337 (All versions of this report)

Short URL: ia.cr/2003/225

Discussion forum: Show discussion | Start new discussion