Editing Trapdoor function (section)

==Definition==

A '''trapdoor function''' is a collection of [[one-way function]]s { ''f''<sub>''k''</sub> : ''D''<sub>''k''</sub> → ''R''<sub>''k''</sub> } (''k'' ∈ ''K''), in which all of ''K'', ''D''<sub>''k''</sub>, ''R''<sub>''k''</sub> are subsets of binary strings {0, 1}<sup>*</sup>, satisfying the following conditions:
* There exists a probabilistic polynomial time (PPT) ''sampling'' algorithm Gen s.t. Gen(1<sup>''n''</sup>) = (''k'', ''t''<sub>''k''</sub>) with ''k'' ∈ ''K'' ∩ {0, 1}<sup>''n''</sup> and ''t''<sub>''k''</sub> ∈ {0, 1}<sup>*</sup> satisfies | ''t''<sub>''k''</sub> | < ''p'' (''n''), in which ''p'' is some polynomial. Each ''t''<sub>''k''</sub> is called the ''trapdoor'' corresponding to ''k''. Each trapdoor can be efficiently sampled.
* Given input ''k'', there also exists a PPT algorithm that outputs ''x'' ∈ ''D''<sub>''k''</sub>. That is, each ''D''<sub>''k''</sub> can be efficiently sampled.
* For any ''k'' ∈ ''K'', there exists a PPT algorithm that correctly computes ''f''<sub>''k''</sub>.
* For any ''k'' ∈ ''K'', there exists a PPT algorithm ''A'' s.t. for any ''x'' ∈ ''D''<sub>''k''</sub>, let ''y'' = ''A'' ( ''k'', ''f''<sub>''k''</sub>(''x''), ''t''<sub>''k''</sub> ), and then we have ''f''<sub>''k''</sub>(''y'') = ''f''<sub>''k''</sub>(''x''). That is, given trapdoor, it is easy to invert.
* For any ''k'' ∈ ''K'', without trapdoor ''t''<sub>''k''</sub>, for any PPT algorithm, the probability to correctly invert ''f''<sub>''k''</sub> (i.e., given ''f''<sub>''k''</sub>(''x''), find a pre-image ''x' '' such that ''f''<sub>''k''</sub>(''x' '') = ''f''<sub>''k''</sub>(''x'')) is negligible.<ref>Pass's Notes, def. 56.1</ref><ref>Goldwasser's lecture notes, def. 2.16</ref><ref>Ostrovsky, pp. 6–10, def. 11</ref>

If each function in the collection above is a one-way permutation, then the collection is also called a '''trapdoor permutation'''.<ref>Pass's notes, def 56.1; Dodis's def 7, lecture 1.</ref>