One-way function: Difference between revisions

Revision as of 12:02, 22 April 2021

Revision as of 19:51, 19 May 2021

Line 23:

A [[trapdoor one-way function]] or trapdoor permutation is a special kind of one-way function. Such a function is hard to invert unless some secret information, called the ''trapdoor'', is known.

A '''collision-free hash function''' ''f'' is a one-way function that is also ''collision-resistant''; that is, no [[randomized polynomial time]] algorithm can find a [[hash collision (computer science)|collision]]—distinct values ''x'', ''y'' such that ''f''(''x'') = ''f''(''y'')—with non-negligible probability.<ref>{{cite journal |last=Russell |first=A. |title=Necessary and Sufficient Conditions for Collision-Free Hashing |journal=[[Journal of Cryptology]] |volume=8 |issue=2 |pages=87–99 |year=1995 |doi=10.1007/BF00190757 |s2cid=26046704 }}</ref>

==Theoretical implications of one-way functions==