A Sufficient Condition and Optimal Domain Extension of UOWHF.
Mridul Nandi · 2003
In this paper we will provide a non-trivial sufficient condition for UOWHF-preserving domain extension which will be very easy to verify. Using this result we can prove very easily that all known domain extension algorithms are valid. This will be a nice technique to prove a domain extension is valid. We also propose an optimal (w.r.t. both time complexity and key size) domain extension algorithm based on an incomplete binary tree. In Asiacrypt'03 [6] (also in [5]) author proposed a binary tree based domain extension of UOWHF. We will show that the binary tree based construction [5] is optimal in a subclass of full binary tree based domain extension. A full binary tree based...