Universal One-Way Hash Functions and Efficiency Measures
The concept of Universal One-Way Hash Functions (UOWHFs) and their efficiency measures, including seed length and number of calls, are explored in this academic paper. It delves into the construction of UOWHFs from regular OWFs and the similarities between OWFs, Pseudo-Random Generators (PRGs), and UOWHFs. The efficiency gap between PRGs and UOWHFs is analyzed, highlighting the distinction between adaptive and non-adaptive constructions.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
1 Non-Adaptive Universal One-Way Hash Functions from Arbitrary One-Way Functions Xinyu Mao* Noam Mazor** Jiapeng Zhang* April 26, 2023 * University of Southern California ** Tel-Aviv University
One-Way Functions 2 A function ?: 0 ,1? 0,1? is one-way function if: Easy to compute: ? is computable in poly ? time. Hard to invert: PPT ? ? 0 ,1?? ?(?) ? 1? ? = negl(?). Pr OWF exists: minimal assumption for cryptography ? ? ? ? easy hard ? 1
Universal One-Way Hash Functions (UOWHFs) [Naor-Yung 89] 3 UOWHF (also known as target collision-resistant hash function) A keyed hash family ??: 0,1? 0,1 ,? 0 ,1? Shrinking: < ?. Target collision resistance: PPT ? = ?1,?2 Pr ?,?? ?1, ? 0,1??2?,?,?? = ? s.t. ??? = ??? is negligible. One-way function + UOWHF digital signature [Naor-Yung 89] One-way function UOWHF [Rompel 90] UOWHF can be easily constructed from a unkeyed function ? that is shrinking and collision-resistant on random inputs. Construction: ??? ?(? ?) Given random ? 0 ,1?, it is hard to find ? such that ? ? = ? ? .
The efficiency of OWF UOWHF constructions OWF ?: 0 ,1? 0 ,1? 4 UOWHF ??: 0,1? ? 0,1 ?,? 0 ,1? ? Efficiency Measures Seed length: ?(?) Number of calls to the underlying OWF Adaptivity: whether the invocations of the OWF are dependent of the output of previous calls Seed length ? ?5log? ? ?9log? Number of calls ? ?13 ? ?10 Non-adaptive? [HHRVW 10] Our Construction 1 The first non-adaptive construction It can be implemented in ???with ?-oracle gates Combined with [AIK 06] Assuming that OWFs exist in ???, there exists a UOWHF in ???. What does the right construction look like?
Similarity between OWF PRG and OWF UOWHFs 5 Regular OWF ?: 0 ,1? 0 ,1? ?,? Image ? , ? 1? = ? 1(? ) [MZ 22] ? ,?1, ,?? ?1,? ?2 , ?2,? ?3 , , ?? 1,? ?? : 0 ,12? 0 ,1?+ is a hash function from an appropriate hash family. Hashing out more bits: = log? ? is PRG. Hashing out fewer bits: = log? ? is collision-resistant on random inputs. ? ,?1, ,?? ? ?1,? ,?1, ,??,??
The efficiency gap between OWF PRG and OWF UOWHFs 6 Lower bound: ? calls [HS 12,16] OWF ?: 0 ,1? 0 ,1? Assumption Seed Length PRG Number of Calls PRG Remarks UOWHF UOWHF [HHR 06] [AGV 12] [MZ 22] [VZ 12][HRV 10][HHRVW 10] Our Construction 1 Our Almost-UOWHF Regular OWF Regular OWF Arbitrary OWF Arbitrary OWF Arbitrary OWF Adaptive Non-adaptive Efficiency gap Non-adaptive Non-adaptive Almost-UOWHF ? ? ? ?2 ?(?4) - - ? ? ? ?2 ? ?7 ? ?10 ? ?4 ? ? ? ? ?(?) ? ?3 ?(?) ? ?13 ? ?9 ? ?3 - - No efficiency gap between PRG and UOWHF if OWF is regular! Our Almost-UOWHF construction is very similar to HRV PRG construction.
7 Constructions
A Candidate UOWHF (the right Construction) 8 Similar to HRV PRG Framework: computational entropy Arbitrary OWF ?: 0,1? 0,1? Computational entropy generator ? PRG, UOWHF, Manipulating entropy and extraction HRV PRG: ? ? has next-bit pseudoentropy HRVVW UOWHF: ? ? has inaccessible entropy Write ? ? ? 0 ,1 . ? = ?1, ,? : ?: ?1, ,?? ???, ,?? 1,?? ?? [ ]? ?? | ?1, ,?? 1 (? : Shannon entropy) That is, on average, each bit exhibit ?extra pseudoentropy. Next-bit version? ? ? + ?. ?(?1,1) ?(?2,1) ?(?1,2) ?(?2,2) ?(?1,?) ?(?2,?) ? rows ?(??,1) ?(??,2) ?(??,?) HRV PRG : repetition + random shift, drop unpopulated columns, hash more bits hash : 0 ,1? 0 ,1? ? columns
A Candidate UOWHF (the right Construction) contd 9 Framework: computational entropy Arbitrary OWF ?: 0,1? 0,1? Computational entropy generator ? PRG, UOWHF, Manipulating entropy and extraction HRV PRG: ? ? has next-bit pseudoentropy HRVVW UOWHF: ? ? has inaccessible entropy Repetition + Random shift Drop unpopulated columns, hash more bits HRV PRG ?(?1,1) ?(?2,1) ?(?1,2) ?(?2,2) ?(?1,?) ?(?2,?) Output unpopulated columns, hash fewer bits UOWHF ?(??,1) ?(??,2) ?(??,?) We introduce next-bit unreachable entropy and show that: almost-UOWHF hash
Next-bit unreachable entropy 10 We say ?: 0,1? 0,1 has next-bit unreachable entropy if for every ? , there exists a set ?? 0 ,1? , such that: It is hard to flip the ?-th bit while staying inside ??: PPT ? Pr ? ?<?= ? ? <? ? ?? ? ? ? ? ?? = negl ? . ? is large: Pr ?? ?? ?+ ? 0,1?,? ,? ? ?,? . Hard to get inside ?: PPT ? Pr ? ?<?= ? ? <? ? ?? ? ?? = negl ? . HRV next bit pseudoentropy generator: ? ,? ? ? , ? , Our next bit unreachable entropy generator: ? 1, 2,? 1? ? , 2? , 1, 2 * , 1, 2are from proper hash families
Almost-UOWHF: Whats the point? 11 ?(?1,1) ?(?2,1) ?(?1,2) ?(?2,2) ?(?1,?) ?(?2,?) Almost-UOWHF: a negligible fraction of inputs such that any adversary can find collision ? only from . Input space ?(??,1) ?(??,2) ?(??,?) hash ? ? 1? ? , 2? , 1, 2 Our construction is very similar to the HRV PRG construction. The HRV PRG construction is actually an Almost-PRG . Almost-PRG: ? ?|? ?uniform random bits, where contains negligible fraction of inputs. Fortunately, Almost-PRG = PRG.
Non-adaptive UOWHF 12 ?(?1,1) ?(?2,1) ?(?1,2) ?(?2,2) ?(?1,?) ?(?2,?) ? ?4rows ?(??,1) ?(??,2) ?(??,?) hash : 0 ,1? 0 ,1? ? ?5copies Modifications towards a full-fledged UOWHF Use large ?,? Hash a ? block instead of hashing a single column Collision-resistant on random inputs* *In order to get a simpler proof by existing techniques, we actually prove that an equivalent construction is UOWHF.
Open Questions 13 Conjecture. Our Almost-UOWHF construction is a full-fledged UOWHF. Do we need to modify our next-bit unreachable entropy definition? Even with a more natural computational entropy generator: ? ? ? ? ,? This is used in [VZ 12] to construct PRG. Lower bounds on black-box constructions from OWF: seed length number of calls Both PRG and UOWHFs
Thank you! 14 ?(?1,1) ?(?2,1) ?(?1,2) ?(?2,2) ?(?1,?) ?(?2,?) ?(?1,1) ?(?2,1) ?(?1,2) ?(?2,2) ?(?1,?) ?(?2,?) ?(??,1) ?(??,2) ?(??,?) ?(??,1) ?(??,2) ?(??,?) hash ? ? 1? ? , 2? , 1, 2 Seed length ? ?5 ? ?10 ? ?4 Number of calls ? ?13 ? ?9 ? ?3 Non-adaptive? [HHRVW 10] Our UOWHF Our Almost-UOWHF
Non-adaptive UOWHF 15 Inaccessible entropy [HHRVW 15] ?: 0,1?5 0,1?5 Arbitrary OWF ?: 0,1? 0,1? ? ?(?) = ?(?) For any ?-collision-finder ?, with overwhelming probability over ? 0 ,1?5: ? 1? ? 2 +? log ? The output of ? ? have at most 2 possibilities. The proof is non-trivial since ? is not completely like regular. is similar to the regular parameter Apply [MZ22] Difficulty: is unknown Non-adaptive UOWHF ? 1, , ? 1,?1 ,?? ? ?1, 1?1,? ?2 , , ? 1?? 1,? ?? ,??, 1, , ? 1
Non-adaptive UOWHF: proof idea 16 Inaccessible entropy [HHRVW 15] ?: 0,1?5 0,1?5 Arbitrary OWF ?: 0,1? 0,1? For any ?-collision-finder ?, with overwhelming probability over ? 0 ,1?5: ? 1? ? 2 +? log ? The output of ? ? have at most 2 possibilities. There exists a negligible fraction of bad inputs . is small, but ?( ) could be large. Adversary can find collisions from . Construction 1 ? 1, , ? 1,?1 ,?? ? ?1, 1?1,? ?2 , , ? 1?? 1,? ?? ,??, 1, , ? 1 Key lemma: w.h.p. over 1, , ? 1, for any valid collision ?1 ,?? , ?? ??is in the output and ?? w.h.p. ??+1 ?.
