Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

On page 21 of the Rivest's Cryptology chapter, he defines a trapdoor predicate as a boolean function for which it is easy to choose an x such that B(x) = v, but hard for an adversary to compute B(x) given x, without the trapdoor information.

He goes on to say that Alice's public key contains a description of B.

What exactly goes into this description, to enable the trapdoor predicate property, without giving away the secret key?

share|improve this question
For his definition, what goes into that description is either a circuit, an algorithm in some model (such as Turing machines or word RAM, or a clocked algorithm in some model that's not restricted to just yes/no answers). $\;\;$ It's better define those to consist of specific algorithms that take a key as input. $\;\;\;\;\;$ – Ricky Demer May 13 '14 at 3:54

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.