Scribed by Steve Hanna
Summary
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 since
and the absolute value in (1) may be removed without loss of generality (at the cost of increasing the complextiy parameter by one).
- 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.
This would not be a concern if the encryption mechanism were separate from the transport mechanism. For instance, if the application of this scheme occurred in such a way they two parties are securely communicating over an instant messaging client which exists in the application layer and encryption were occurring layers below in the transport layer. This abstraction of layers and separation of the encryption mechanism from the application abstracts away the notion that the public key could be encrypted with the public key. The messaging client is aware of the interface, but it never exposes the actual public or private key to the user, which prevents incorrectly using the cryptographic primitives.
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. A random bit
is chosen and then the ciphertext of
is computed and given to the adversary. The adversary continues to have access to the Encryption function with the given public key. When the adversary is done, it outputs a guess called
The output of this procedure is 1 when
. A cryptosystem in which
can be distinguished from other ciphertexts violates this definition of security.
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
A hybrid approach to public key cryptography is often desired due to the fact that public key operations are computationally expensive (i.e modular exponentiation), while symmetric key cryptosystem are usually more efficient. The basic idea behind the hybrid approach that if we encrypt the symmetric private key with the public key and encrypt the message with the symmetric private key, only the small symmetric private key needs to be encrypted with the public key and symmetric key encryption/decryption can take place on the actual message. This allows for efficient computation of the message encryption and decryption while only using asymmetric key cryptography for transmitting the symmetric shared secret. This construction makes encryption and decryption much more efficient while still ensuring the construction has message indistinguishability and CPA security.
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.
We begin by assuming the conclusion of the theorem is false, that is is not
-secure. Suppose there is an adversary A, that runs in time
and there are two messages
and
such that:
Then the definition of is applied, so
We then apply a hybrid argument in which the hybrid distributions have instead of
. (
denotes a string of zeroes; any other fixed string could be used in the proof.) Producing:
This means that at least one of the following cases must happen:
If or
are true, then it means that there is a message
such that:
Then there must exist one fixed such that
and then we define an algorithm of complexity at most
such that:
which contradicts the security of .
If is true, then we define an algorithm
of complexity at most
such that:
which contradicts the security of .
3. RSA
The RSA function has the same “syntax” of a public-key encryption scheme:
- Key generation: Pick two distinct prime numbers
,
, compute
, and find integers
such that
Set the public key to
and the private key to
- “Encryption:” given
and public key
, output
- “Decryption:” given
and secret key
, output
It is a standard calculation using the Chinese remainder theorem and Fermat’s little theorem that and
are permutations over
, and they are one the inverse of the other.
This is, however, not a secure encryption scheme because it is deterministic, and it suffers from several weaknesses that can exploited in practice.
A conjectural way to turn RSA into a CPA-secure encryption scheme is to employ it to encrypt plaintexts whose length is only about , and then pad the plaintext with
random bits before applying
. (Other choices for the length of the plaintext and the amount of randomness are possible, half-half is just an example.)
The assumption that this padded-RSA is CPA secure is a very strong one. In the next lecture we will see how to turn RSA into a CPA secure encryption scheme under the minimal assumption that is hard to invert on a random input for an adversary that knows the public key but not the secret key.