1
$\begingroup$

I am reading the book An Introduction to Mathematical Cryptography. In its chapter 7, there is the following statement:

In real world scenarios, cryptosystems based on NP-hard or NP-complete problems tend to rely on particular subclass of problems either to achieve efficiency or to allow the creation of a trapdoor.

Questions:

Is is possible to explain what does it mean the phrase "to allow the creation of a trapdoor"?

Thanks for any help

$\endgroup$
1
  • 3
    $\begingroup$ It is explained in chapter 1, page 47, what a trapdoor is. Chapter 2, page 63, explains it in more detail. $\endgroup$ Commented Feb 16, 2021 at 11:05

1 Answer 1

1
$\begingroup$

A "trapdoor" function is a function which is hard to compute, but will become very easy (or a lot easier) to compute if you have some specific knowledge.

The classical example is solving y = x^3 (modulo n) where n is the product of two very large primes; it is the basis of RSA encryption and practically impossible to solve given x and n, unless you are given the two primes p, q such that n = pq.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.