1. One-Time Pad, Stream Ciphers and PRGs
Assumptions and Notations
An encryption scheme is defined by
- A (probabilistic) key generation algorithm
. and which are encryption, decryption algorithms respectively.
We assume perfect correctness.
Assumption.
, , if then with probability .
This assumption allows us to assume that the decryption algorithm
Some random variables:
for the distribution over the key space .- The output from
. We denote this as .
- The output from
for the message being encrypted, and for the ciphertext.- We will write
.
- We will write
and are required to be independent.
Perfect Secrecy
For a scheme to be perfectly secret, the ciphertext should not reveal any information about the underlying plaintext, so that the adversary learns absolutely nothing about the plaintext.
Definition. An encryption scheme is perfectly secret if for any distribution of
and any ciphertext such that , for every
.
For example, the shift cipher with
The above definition is equivalent to the following.
Definition. An encryption scheme is perfectly secret if for any
and , we have where the probability is taken over the random choice
.
Proposition. The above two definitions are equivalent.
Proof. Suppose we are given any distribution on
where
by the definition of conditional probability.
(
(
Thus equation
One-Time Pad (OTP)
This is an encryption scheme patented by Vernam in 1917.
- Set
. chooses a key from according to the uniform distribution.- Each key is chosen with probability
.
- Each key is chosen with probability
and .
From the above definition, the correctness of the scheme is easily checked.
Intuitively,
Perfect Secrecy of OTP
Theorem. The one-time pad encryption scheme is perfectly secret.
Proof. For any
since
Therefore
Here is another proof using the second definition.
Proof. For any
Thus OTP satisfies the definition of perfect secrecy.
Drawbacks of OTP
The OTP is perfectly secure, but there are some drawbacks to using the OTP in practice.
First of all, OTP is perfectly secure only for one message. Suppose that we reuse the key
Since the adversary can see the ciphertext, this kind of relation leaks some information about
Also, the key is (at least) as long as the message. This is why OTP is rarely used today. When sending a long message, two parties must communicate a very long key that is as long as the message, every single time! This makes it hard to manage the key.
Shannon’s Theorem
So is there a way to reduce the key size without losing perfect secrecy? Sadly, no. In fact, the key space must be as least as large as the message space. This is a requirement for perfectly secret schemes.
Theorem. If
is a perfectly secret encryption scheme, then .
Proof. Assume
which is the set of all possible decryptions of
so the scheme cannot be perfectly secret.
In words, if
Pseudorandom Generators (PRG)
The problem with one-time pad is that we must use very long keys. So the idea of stream ciphers is to replace the random key by a pseudorandom key. The pseudorandom generator (PRG) will compute a pseudorandom key from a seed chosen from a smaller space.
Definition. A pseudorandom generator is an efficient deterministic algorithm
such that given an input seed from , it outputs an element of . Typically, .
Stream Ciphers
Then the stream cipher is defined as follows. Note that we have reduced the key size.
, with . . and .
Since
Security of PRGs
Negligible Functions
A negligible function is a function that tends to
Definition. A function
is negligible if for all , there exists such that for all , we have .
The following is evident from the definition.
Lemma. A function
is negligible if and only if for all ,
In practice, about
Unpredictability of PRGs
The adversary will want to distinguish if some bit string is an output of a PRG or truly random. So PRGs must satisfy the notion of unpredictability, which says that no efficient algorithm can predict the next bit of PRGs.
Definition. A PRG is predictable if there exists an efficient adversary
and such that for non-negligible
.
The probability here is taken over
A PRG is unpredictable if it is not predictable, meaning that no efficient adversary
Indistinguishability
Statistical Test
Since the stream cipher is not perfectly secret, we need a weaker notion of security. That is, indistinguishability to the adversary.
Let
To formally define what it means to be indistinguishable, we consider a statistical test.
Definition. A statistical test on
is an algorithm such that outputs for not random or for random.
For example, an algorithm
if and only if the difference in the number of occurrences of and is less than .
would be a statistical test.
Advantage
Let
Definition. The PRG advantage is defined as
Intuitively, the advantage calculates how well
- If the advantage is close to
, the probabilities are almost the same, meaning that cannot distinguish from a random bit string. - If the advantage is close to
, one of the probabilities is close to , meaning that can distinguish from a random bit string.2
Secure PRG
Now we can define the security of PRGs.
Definition.
is a secure PRG if for any efficient statistical test , is negligible.
There are no provably secure PRGs, but we have heuristic candidates, meaning that no such efficient
Predictability and Security of PRGs
We can deduce that if a PRG is predictable, then it is insecure.
Theorem. Let
be a PRG. If is predictable, then it is insecure.
Proof. Let
- The challenger PRG will send a bit string
to .- In experiment
, PRG gives pseudorandom string . - In experiment
, PRG gives truly random string .
- In experiment
gives to , then will do some calculation and return . compares with , and returns if , otherwise.
Let
and the advantage is non-negligible.
Surprisingly, the other way around is also true.
Theorem. (Yao’82) If a PRG
is unpredictable, then is secure.
The theorem implies that if next bit predictors cannot distinguish
Security Game Framework
To motivate the definition of semantic security, we consider a security game framework (attack game) between a challenger (ex. the creator of some cryptographic scheme) and an adversary
Definition. Let
be a cipher defined over . For a given adversary , we define two experiments and . For , define experiment as follows: Experiment
.
- The adversary computes
and sends them to the challenger. - The challenger computes
, and sends to the adversary. - The adversary outputs a bit
. Let
be the event that outputs in experiment . i.e, the event that . Now define the semantic security advantage of with respect to as
As we understood the advantage of PRG, semantic security advantage can be understood the same way. If the advantage is closer to
Distinguishing Distributions
In the same way, we can define a security game for distinguishing two distributions.
Definition. Let
, be two distributions over a set . For any given efficient adversary , define experiments and . Experiment
.
- The challenger computes
and sends to the adversary. - The adversary computes and outputs a bit
. Let
the event that outputs in experiment . Then the advantage is defined as If the advantage is negligible, we say that
and are computationally indistinguishable, and write .
As an example, a PRG
Semantic Security
So now we can define a semantically secure encryption scheme.
Definition. An encryption scheme
is semantically secure if for any efficient adversary , its advantage is negligible.
It means that the adversary cannot distinguish whether the received message is an encryption of
Using the notion of computational indistinguishability,
Semantic Security of the Stream Cipher
Theorem. If
is a secure PRG, then the stream cipher constructed from is semantically secure.
Proof. Let
Since
Define two new experiments as follows:
- The adversary
gives two messages . - The challenger draws a random string
. - In experiment
, return . will return .
Let
The last equality holds since OTP is perfectly secure and thus
Without loss of generality, assume that
- Challenger PRG gives a bit string
.- In experiment
, challenger gives pseudorandom string . - In experiment
, challenger gives truly random string .
- In experiment
- Invoke
, then will send two messages . - Compute
and return to . will return , and return directly to challenger PRG.
Let
Therefore, the PRG advantage of
which is non-negligible, so it breaks the security of the PRG.
Corollary. For any adversary
for the stream cipher , there exists an adversary for a PRG such that
Proof. Use equation
This theorem tells use that the (semantic) security of the stream cipher relies on the security of the PRGs.3 Thus we conclude that it is important to construct a secure PRG.