Today we discuss the three ways in which definitions of security given in class differ from the way they are given in the Katz-Lindell textbook,.
Then we study the security of hybrid encryption schemes, in which a public-key scheme is used to encode the key for a private-key scheme, and the private-key scheme is used to encode the plaintext.
We also define RSA and note that in order to turn RSA into an encryption scheme we need a mechanism to introduce randomness.
1. Definitions of Security
There are three ways in which the definitions of security given in class differ from the way they are given in the textbook. The first one applies to all definitions, the second to definitions of encryption, and the third to CPA and CCA notions of security for encryption:
- Our definitions usually refer to schemes of fixed key length and involve parameters , while the textbook definitions are asymptotic and parameter-free.
Generally, one obtains the textbook definition by considering a family of constructions with arbitrary key length (or, more abstractly “security parameter”) , and allowing to grow like any polynomial in and requiring to be negligible. (Recall that a non-negative function is negligible if for every polynomial we have .)
The advantage of the asymptotic definitions is that they are more compact and make it easier to state the result of a security analysis. (Compare “if one-way permutations exist, then length-increasing pseudorandom generators exist” with “if is a one-way permutation computable in time , then there is a generator computable in time that is pseudorandom”)
The advantage of the parametric definitions is that they make sense for fixed-key constructions, and that they make security proofs a bit shorter.
(Every asymptotic security proof starts from “There is a polynomial time adversary , an infinite set of input lengths, and a polynomial , such that for every .)
- Definitions of security for an encryption algorithm , after the proper quantifications, involve an adversary (who possibly has oracles, etc.) and messages , ; we require
while the textbook usually has a condition of the form
The two conditions are equivalent.
- Definitions of CPA and CCA security, as well as all definitions in the public-key setting, have a different structure in the book. The difference is best explained by an example. Suppose we have a public-key scheme such that, for every valid public key , has some distinctive pattern that makes it easy to distinguish it from other ciphertexts. This could be considered a security weakness because an eavesdropper is able to see if a party is sending a message that concerns the public key.
You can show as an exercise that if a secure public-key encryption scheme exists, then there is a public-key encryption scheme that is secure according to our definition from last lecture but that has a fault of the above kind.
The textbook adopts a two-phase definition of security, in which the adversary is allowed to choose the two messages that it is going to try and distinguish, and the choice is done after having seen the public key.
2. Hybrid Encryption
Let be a public-key encryption scheme and a private-key encryption scheme. Consider the following hybrid scheme :
- : same as
- : pick a random key for , output
- : output
Theorem 1 Suppose is -secure for one encryption and is -secure for one encryption. Suppse also that have running time . Then is -secure for one encryption.