Trapdoor function

<h2 id="definition">Definition</h2>
A trapdoor function is a collection of <a href="/facts/One-way_function/rGtcumDW">one-way functions</a> { fk : Dk → Rk } (k ∈ K), in which all of K, Dk, Rk are subsets of binary strings {0, 1}*, satisfying the following conditions:

<ul><li>There exists a probabilistic polynomial time (PPT) sampling algorithm Gen s.t. Gen(1n) = (k, tk) with k ∈ K ∩ {0, 1}n and tk ∈ {0, 1}* satisfies | tk | < p (n), in which p is some polynomial. Each tk is called the trapdoor corresponding to k. Each trapdoor can be efficiently sampled.</li>
<li>Given input k, there also exists a PPT algorithm that outputs x ∈ Dk. That is, each Dk can be efficiently sampled.</li>
<li>For any k ∈ K, there exists a PPT algorithm that correctly computes fk.</li>
<li>For any k ∈ K, there exists a PPT algorithm A s.t. for any x ∈ Dk, let y = A ( k, fk(x), tk ), and then we have fk(y) = fk(x). That is, given trapdoor, it is easy to invert.</li>
<li>For any k ∈ K, without trapdoor tk, for any PPT algorithm, the probability to correctly invert fk (i.e., given fk(x), find a pre-image x' such that fk(x' ) = fk(x)) is negligible.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a><a class="footnote-ref" id="fnref:3" href="#fn:3">3</a><a class="footnote-ref" id="fnref:4" href="#fn:4">4</a></li></ul>
If each function in the collection above is a one-way permutation, then the collection is also called a trapdoor permutation.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>

<h2 id="examples">Examples</h2>
In the following two examples, we always assume that it is difficult to factorize a large composite number (see <a href="/facts/Integer_factorization/EjMCTz2t">Integer factorization</a>).

<h3>RSA assumption</h3>
In this example, the inverse 
 
 
 
 d
 
 
 {\displaystyle d}
 
 of 
 
 
 
 e
 
 
 {\displaystyle e}
 
 modulo 
 
 
 
 ϕ
 (
 n
 )
 
 
 {\displaystyle \phi (n)}
 
 (<a href="/facts/Euler%2527s_totient_function/mIQwXYzj">Euler's totient function</a> of 
 
 
 
 n
 
 
 {\displaystyle n}
 
) is the trapdoor:

f
        (
        x
        )
        =
        
          x
          
            e
          
        
        
        mod
        
        
        n
        .
      
    
    {\displaystyle f(x)=x^{e}\mod n.}

If the factorization of 
 
 
 
 n
 =
 p
 q
 
 
 {\displaystyle n=pq}
 
 is known, then 
 
 
 
 ϕ
 (
 n
 )
 =
 (
 p
 −
 1
 )
 (
 q
 −
 1
 )
 
 
 {\displaystyle \phi (n)=(p-1)(q-1)}
 
 can be computed. With this the inverse 
 
 
 
 d
 
 
 {\displaystyle d}
 
 of 
 
 
 
 e
 
 
 {\displaystyle e}
 
 can be computed 
 
 
 
 d
 =
 
 e
 
 −
 1
 
 
 
 mod
 
 
 ϕ
 (
 n
 )
 
 
 {\displaystyle d=e^{-1}\mod {\phi (n)}}
 
, and then given 
 
 
 
 y
 =
 f
 (
 x
 )
 
 
 {\displaystyle y=f(x)}
 
, we can find 
 
 
 
 x
 =
 
 y
 
 d
 
 
 
 mod
 
 
 n
 =
 
 x
 
 e
 d
 
 
 
 mod
 
 
 n
 =
 x
 
 mod
 
 
 n
 
 
 {\displaystyle x=y^{d}\mod n=x^{ed}\mod n=x\mod n}
 
.
Its hardness follows from the RSA assumption.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>

<h3>Rabin's quadratic residue assumption</h3>
Let 
 
 
 
 n
 
 
 {\displaystyle n}
 
 be a large composite number such that 
 
 
 
 n
 =
 p
 q
 
 
 {\displaystyle n=pq}
 
, where 
 
 
 
 p
 
 
 {\displaystyle p}
 
 and 
 
 
 
 q
 
 
 {\displaystyle q}
 
 are large primes such that 
 
 
 
 p
 ≡
 3
 
 
 (
 mod
 
 4
 )
 
 ,
 q
 ≡
 3
 
 
 (
 mod
 
 4
 )
 
 
 
 {\displaystyle p\equiv 3{\pmod {4}},q\equiv 3{\pmod {4}}}
 
, and kept confidential to the adversary. The problem is to compute 
 
 
 
 z
 
 
 {\displaystyle z}
 
 given 
 
 
 
 a
 
 
 {\displaystyle a}
 
 such that 
 
 
 
 a
 ≡
 
 z
 
 2
 
 
 
 
 (
 mod
 
 n
 )
 
 
 
 {\displaystyle a\equiv z^{2}{\pmod {n}}}
 
. The trapdoor is the factorization of 
 
 
 
 n
 
 
 {\displaystyle n}
 
. With the trapdoor, the solutions of z can be given as 
 
 
 
 c
 x
 +
 d
 y
 ,
 c
 x
 −
 d
 y
 ,
 −
 c
 x
 +
 d
 y
 ,
 −
 c
 x
 −
 d
 y
 
 
 {\displaystyle cx+dy,cx-dy,-cx+dy,-cx-dy}
 
, where 
 
 
 
 a
 ≡
 
 x
 
 2
 
 
 
 
 (
 mod
 
 p
 )
 
 ,
 a
 ≡
 
 y
 
 2
 
 
 
 
 (
 mod
 
 q
 )
 
 ,
 c
 ≡
 1
 
 
 (
 mod
 
 p
 )
 
 ,
 c
 ≡
 0
 
 
 (
 mod
 
 q
 )
 
 ,
 d
 ≡
 0
 
 
 (
 mod
 
 p
 )
 
 ,
 d
 ≡
 1
 
 
 (
 mod
 
 q
 )
 
 
 
 {\displaystyle a\equiv x^{2}{\pmod {p}},a\equiv y^{2}{\pmod {q}},c\equiv 1{\pmod {p}},c\equiv 0{\pmod {q}},d\equiv 0{\pmod {p}},d\equiv 1{\pmod {q}}}
 
. See <a href="/facts/Chinese_remainder_theorem/7wwFIkuV">Chinese remainder theorem</a> for more details. Note that given primes 
 
 
 
 p
 
 
 {\displaystyle p}
 
 and 
 
 
 
 q
 
 
 {\displaystyle q}
 
, we can find 
 
 
 
 x
 ≡
 
 a
 
 
 
 p
 +
 1
 
 4
 
 
 
 
 
 (
 mod
 
 p
 )
 
 
 
 {\displaystyle x\equiv a^{\frac {p+1}{4}}{\pmod {p}}}
 
 and 
 
 
 
 y
 ≡
 
 a
 
 
 
 q
 +
 1
 
 4
 
 
 
 
 
 (
 mod
 
 q
 )
 
 
 
 {\displaystyle y\equiv a^{\frac {q+1}{4}}{\pmod {q}}}
 
. Here the conditions 
 
 
 
 p
 ≡
 3
 
 
 (
 mod
 
 4
 )
 
 
 
 {\displaystyle p\equiv 3{\pmod {4}}}
 
 and 
 
 
 
 q
 ≡
 3
 
 
 (
 mod
 
 4
 )
 
 
 
 {\displaystyle q\equiv 3{\pmod {4}}}
 
 guarantee that the solutions 
 
 
 
 x
 
 
 {\displaystyle x}
 
 and 
 
 
 
 y
 
 
 {\displaystyle y}
 
 can be well defined.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/One-way_function/rGtcumDW">One-way function</a></li></ul>
<h2 id="notes">Notes</h2>

<ul><li><a href="/facts/Whitfield_Diffie/oDKz7ChA">Diffie, W.</a>; <a href="/facts/Martin_Hellman/QCxKCFgn">Hellman, M.</a> (1976), <a href="http://www-ee.stanford.edu/~hellman/publications/24.pdf">"New directions in cryptography"</a> (PDF), <a href="/facts/IEEE_Transactions_on_Information_Theory/NbsWT0E4">IEEE Transactions on Information Theory</a>, 22 (6): 644–654, <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.9720">10.1.1.37.9720</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1109%2FTIT.1976.1055638">10.1109/TIT.1976.1055638</a></li>
<li>Pass, Rafael, <a href="https://www.cs.cornell.edu/courses/cs4830/2010fa/lecnotes.pdf">A Course in Cryptography</a> (PDF), retrieved 27 November 2015</li>
<li>Goldwasser, Shafi, <a href="https://cseweb.ucsd.edu/~mihir/papers/gb.pdf">Lecture Notes on Cryptography</a> (PDF), retrieved 25 November 2015</li>
<li>Ostrovsky, Rafail, <a href="http://web.cs.ucla.edu/~rafail/PUBLIC/OstrovskyDraftLecNotes2010.pdf">Foundations of Cryptography</a> (PDF), retrieved 27 November 2015</li>
<li>Dodis, Yevgeniy, <a href="http://www.cs.nyu.edu/courses/fall08/G22.3210-001/index.html">Introduction to Cryptography Lecture Notes (Fall 2008)</a>, retrieved 17 December 2015</li>
<li>Lindell, Yehuda, <a href="http://u.cs.biu.ac.il/~lindell/89-856/complete-89-856.pdf">Foundations of Cryptography</a> (PDF), retrieved 17 December 2015</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Bellare, M (June 1998). "Many-to-one trapdoor functions and their relation to public-key cryptosystems". Advances in Cryptology — CRYPTO '98. Lecture Notes in Computer Science. Vol. 1462. pp. 283–298. doi:10.1007/bfb0055735. ISBN 978-3-540-64892-5. S2CID 215825522. <a href="978-3-540-64892-5" target="_blank">978-3-540-64892-5</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Pass's Notes, def. 56.1 <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Goldwasser's lecture notes, def. 2.16 <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Ostrovsky, pp. 6–10, def. 11 <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Pass's notes, def 56.1; Dodis's def 7, lecture 1. <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Goldwasser's lecture notes, 2.3.2; Lindell's notes, p. 17, Ex. 1. <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Goldwasser's lecture notes, 2.3.4. <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
</ol>

Trapdoor function open-in-new

Trapdoor function