Reversible public key scheme
For a public key encryption scheme with message space
$D_d\left(E_e\left(m\right)\right) = E_e\left(D_d\left(m\right)\right) = m$for all $m \in M$
Then we have a reversible PK scheme. (the notes seem to imply that the second property follows from the first; I am unsure)
We can use reversible PK schemes for digital signatures by reversing the encryption and decryption processes. In the case of RSA this means we encrypt a message we send with our private key and the recipient decrypts it with our public key.
$=_p$ and $\leq_p$
$A \leq_p B$means there is a polynomial time (efficient) reduction from problem $A$to problem $B$
$A =_p B$means $A \leq_p B$and $B \leq_p A$