This paper uses a variant of the notion of \emph{inaccessible entropy}(Haitner, Reingold, Vadhan and Wee, STOC 2009) to give an alternative construction and proof for the fundamental result, first proved by Rompel (STOC1990) that UOWHFs can be based on any one-way functions . We observe that a small tweak of any one way function$f$ is already a weak form of a UOWHC . We show (rather easily) that it is hard to sample $x’$ with almost full entropy among all the possible such values . The rest of our construction simply amplifies and exploits thisbasic property .Combined with other recent work, the construction of threefundamental cryptographic primitives (Pseudorandom Generators, StatisticallyHiding Commitments) out of one way functions is now to a largeextension unified. All three constructions rely on and manipulate notions of entropy in similar ways

Author(s) : Iftach Haitner, Thomas Holenstein, Omer Reingold, Salil Vadhan, Hoeteck Wee

Links : PDF - Abstract

Code :
Coursera

Keywords : entropy - construction - functions - inaccessible - stoc -

Leave a Reply

Your email address will not be published. Required fields are marked *