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?

  • $\begingroup$ 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. $\;\;\;\;\;$ $\endgroup$ – user991 May 13 '14 at 3:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.