Trapdoor Function

Only a few algorithms could satisfy all the PKC requirements and have received widespread acceptance in the several decades
• This is because, all of them require a trapdoor one-way function as the
underlying primitive for their working
• Difficult to design a trapdoor one-way function
• One way function: Function that is easy to compute but computationally hard to reverse
• Easy to calculate f (x) from x
• Hard to invert: to calculate x from f (x)

Trapdoor One way function: One way function with additional propertyTrapdoor One way function: One way function with additional property • Easy to calculate f (x) from x
• Hard to invert: to calculate x from f (x)
• With certain knowledge, it is easy to invert: calculate x from f (x)
• Trapdoor One way Function Candidate: Modular Exponentiation
• Easy to calculate (xe mod n) from x
• Hard to invert: to calculate x from (xe mod n)
• The trapdoor is that with another exponent d it is easy to invert, i.e., calculate x = (xe mod n)d mod n
• Easy to calculate f (x) from x
• Hard to invert: to calculate x from f (x)
• With certain knowledge, it is easy to invert: calculate x from f (x)
• Trapdoor One way Function Candidate: Modular Exponentiation
• Easy to calculate (xe mod n) from x
• Hard to invert: to calculate x from (xe mod n)
• The trapdoor is that with another exponent d it is easy to invert, i.e., calculate x = (xe mod n)d mod n