Bellare, Boldyreva, Desai, and Pointcheval proposed a new security
requirement of encryption schemes called ``key-privacy''. It asks that the
encryption provide privacy of the key under which the encryption was
performed. They proposed a variant of RSA-OAEP that provides key-privacy in
the random oracle model assuming RSA is one-way. After giving a more
efficient scheme with respect to the number of exponentiations for
encryption, we propose a new security requirement of undeniable signature
scheme corresponding to key-privacy in encryption scheme. We prove that the
discrete-log based scheme proposed by Michels and Stadler provides anonymity
and existential unforgeability in the random oracle model assuming the
Decision Diffie-Hellman problem is hard. We also propose a variant of an
RSA-based scheme proposed by Gennaro, Krawczyk, and Rabin that provides
anonymity and existential unforgeability in the random oracle model assuming
RSA is one-way and the EDL problem is hard.