Constructing Confidential Channels from Authenticated Channels—Public-Key Encryption Revisited

The security of public-key encryption (PKE), a widely-used cryptographic primitive, has received much attention in the cryptology literature. Many security notions for PKE have been proposed, including several versions of CPA-security, CCA-security, and non-malleability. These security notions are usually defined via a game that no efficient adversary can win with non-negligible probability or advantage.

If a PKE scheme is used in a larger protocol, then the security of this protocol is proved by showing a reduction of breaking a certain security property of the PKE scheme to breaking the security of the protocol. A major problem is that each protocol requires in principle its own tailor-made security reduction. Moreover, which security notion of the PKE scheme should be used in a given context is a priori not evident; the employed games model the use of the scheme abstractly through oracle access to its algorithms, and the sufficiency for specific applications is neither explicitly stated nor proven.

In this paper we propose a new approach to investigating the application of PKE, based on the constructive cryptography framework [24,25]. The basic use of PKE is to enable confidential communication from a sender

A

to a receiver

B

, assuming

A

is in possession of

B

’s public key. One can distinguish two relevant cases: The (non-confidential) communication channel from

A

to

B

can be authenticated (e.g., because messages are signed) or non-authenticated. The application of PKE is shown to provide the construction of a secure channel from

A

to

B

from two (assumed) authenticated channels, one in each direction, or, alternatively, if the channel from

A

to

B

is completely insecure, the construction of a confidential channel without authenticity. Composition then means that the assumed channels can either be physically realized or can themselves be constructed cryptographically, and also that the resulting channels can directly be used in any applications that require such a channel. The composition theorem of constructive cryptography guarantees the soundness of this approach, which eliminates the need for separate reduction proofs.

We also revisit several popular game-based security notions (and variants thereof) and give them a constructive semantics by demonstrating which type of construction is achieved by a PKE scheme satisfying which notion. In particular, the necessary and sufficient security notions for the above two constructions to work are CPA-security and a variant of CCA-security, respectively.