Reverse public key encryption

Abstract

This exposition paper suggests a new low-bandwidth publickey encryption paradigm. The construction turns a weak form of key privacy into message privacy as follows: let Ɛ be a public-key encryption algorithm. We observe that if the distributions Ɛ (pk0, \⦁ ) and Ɛ (pk1, \⦁ ) are indistinguishable for two public keys pk0, pk1, then a message bit b ∈ {0, 1} can be embedded in the choice of pkb. As the roles of the public-key and the plaintext are reversed, we refer to the new mode of operation as Reverse Public-Key Encryption (rpke). We present examples of and variations on the idea and explore RPKE's relationship with key privacy, and we also discuss how to employ it to enable a new implementation of deniable encryption.