Hybrid cryptosystem

From Wikipedia, the free encyclopedia

In cryptography, public-key cryptosystems are convenient in that they do not require the sender and receiver to share a common secret in order to communicate securely (among other useful properties). However, they often rely on complicated mathematical computations and are thus generally much more inefficient than comparable private-key cryptosystems. In many applications, the high cost of encrypting long messages in a public-key cryptosystem can be prohibitive. A hybrid cryptosystem is one which combines the convenience of a public-key cryptosystem with the efficiency of a private-key cryptosystem.

A hybrid cryptosystem can be constructed using any two separate cryptosystems:

  • a key encapsulation scheme, which is a public-key cryptosystem, and
  • a data encapsulation scheme, which is a private-key cryptosystem.

The hybrid cryptosystem is itself a public-key system, whose public and private keys are the same as in the key encapsulation scheme.

To encrypt a message m addressed to Alice in a hybrid scheme, Bob does the following:

  • Generates a random (private) key for the data encapsulation scheme (say, s).
  • Encrypt the message m under the data encapsulation scheme, using the key s just generated.
  • Encrypt the key s under the key encapsulation scheme, using Alice's public key.
  • Send both of these encryptions to Alice.

Alice can use her private key to decrypt s, and then use s to decrypt the message m.

Note that for very long messages m, the bulk of the work in encryption/decryption is done by the more efficient private-key scheme, while the inefficient public-key scheme is used only to encrypt/decrypt a short key value.

[edit] Security

If both the key encapsulation and data encapsulation schemes are secure against adaptive chosen ciphertext attack, then the hybrid scheme inherits that property as well.[1] However, it is possible to construct a hybrid scheme secure against adaptive chosen ciphertext attack even if the key encapsulation has a slightly weakened security definition (though the security of the data encapsulation must be slightly stronger).[2]

[edit] References

  1. ^ Cramer, Ronald; Shoup, Victor (2004). "Design and Analysis of Practical Public-Key Encryption Schemes Secure against Adaptive Chosen Ciphertext Attack". SIAM Journal on Computing 33 (1): 167–226. doi:10.1137/S0097539702403773. 
  2. ^ Dennis, Hofheinz; Kiltz, Eike (2007). "Secure Hybrid Encryption from Weakened Key Encapsulation". Advances in Cryptology -- CRYPTO 2007: 553-571, Springer.