Miscellaneous definitions

Reversible public key scheme

For a public key encryption scheme with message space $M$, cipher space $C$, and key-pair $(d, e)$:

If

1. $M=C$ and
2. $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$

Back to Computer Security