New Techniques for Public Key Encryption with Sender Recovery

Abstract

In this paper, we consider a situation where a sender transmits a ciphertext to a receiver using a public-key encryption scheme, and at a later point of time, wants to retrieve the plaintext, without having to request the receiver’s help in decrypting the ciphertext, and without having to store a set of plaintext/ciphertext pairs for every receiver the sender interacts with. This problem, known as public key encryption with sender recovery has intuitive solutions based on KEM/DEM schemes. We propose a KEM/DEM-based solution that is CCA-secure, and only requires the receiver to be equipped with a public/secret key pair (the sender needs only a symmetric recovery key), and has much simplified proofs compared to prior work in this area. We prove our protocols secure in the single receiver and multi-receiver setting. To achieve our goals, we use an analysis technique called plaintext randomization that results in greatly simplified and intuitive proofs for protocols that use a PKE internally as a component and compose the PKE with other primitives. We instantiate our protocol for public key encryption with sender recovery with the well-known KEM/DEM scheme due to Cramer and Shoup.