Motivating examples
Identity authentication
Consider the scenario that Alice and Bob shared a short key before but now, instead of sending a secret message to Bob, Alice wants to prove her identity to Bob. What make this challenging is that Alice wants to it multiple times, and the communication channel is now controlled by an active adversary Mallory, who can read whatever Alice and Bob send to the channel.
The simple way is to use a password. E.g., Alice can use the shared key as a password and send it to Bob whenever she needs to prove her identity. But this is a very bad idea since Mallory can learn the password from the channel in the first interaction of Alice and Bob, and use it to impersonate Alice in future interactions. This is known as the replay attack. Can encryption with a PRG help? It can not, since PRG is a deterministic function and Mallory does not need to learn what is the password but only its valid encryption. We will see how pseudorandom function generator can help in this scenario.
Chosen plaintext attack
In this kind of attack, the adversary can choose any plaintext and view the corresponding ciphertext to gain information about the encryption scheme. Consider the security game between a PPT-adversary (Adv) and a PPT-challenger (Cha) on an encryption scheme as follows.
IND-CPA():
Cha chooses a random bit and key
For (with ):
Adv chooses and sends it to Cha
Cha sends back
Adv chooses and sends to Cha
Cha sends back
Adv guesses a bit
Adv wins if .
Since the key is reused multiple time to encrypt , a PRG is insufficient for CPA-security.
Pseudorandom function
PRF is a mathematical object that behaves like an indexable (or locally computable) PRG.
Let be a function family defined by where where and are polynomials, the sampling of and the computation of are all efficient.
Let be the set of all functions . This means that sampling a random function from will give a truly random function.
Consider the following security game:
FN-IND():
Cha chooses a random bit
If : sample a random from (truly random)
If : sample a random from (pseudorandom)
For (with ):
Adv sends to Cha
Cha sends to Adv
Adv guesses a bit
Adv wins if .
Alternative definition (Boaz Barak):
Similar to previous definition, we can think of as a family or an ensemble of functions:
Intuitively, the adversary is given access to a function and is asked to specify whether the function is sampled from (a truly random function) or is sampled from . The adversary can run as many queries as he wants. The function family is said to be a PRF if the adversary can not do significantly better than random guessing.
Encryption using PRFs
An encryption is scheme with PRFs is defined as follows:
: Sample a function (shared among parties)
:
Pick
Output
:
Output .
Proof. Assume for contradiction that the encryption scheme is not CPA-secure. Specifically, there is a PPT adversary that wins IND-CPA() with a probability noticeably more than half: for some polynomial . Under this assumption, we show that there is a PPT distinguisher that distinguishes a PRF and a truly random function with non-negligible advantage.
Specifically, is given access to a function and is to conclude is a truly random function sampled from or a pseudorandom function sampled from . The adversary will use while internally simulating and the game IND-CPA as follows:
Whenever A queries its challenger for the encryption of (in the IND-CPA game):
samples
outputs to the string
In the last encryption step when gives two messages and :
samples and
outputs to the string
outputs 1 if guesses the bit correctly. Otherwise, outputs 0.
With the above , we now have:
If is a pseudorandom function, then the probability that gives a correct conclusion (outputting 1) equals the probability that guesses the bit correctly (winning the IND-CPA game), which is due to the assumption of .
On the other hand, if is a truly random function, then the probability that gives a correct conclusion (outputting 0) is negligibly more than half since this is the probability that winning the game IND-CPA. This is because there are possible values of and only observes poly() values of . Therefore, it is extremely unlikely (with probability of only ) that in the last interaction, the string has already been used before. The winning probability of is thus at most , where the first term is the winning probability of random guessing and the second term is the probability that an is reused.
This implies that which is non-negligible. Here in the inequality, we have used the fact that the loosing probability of is at least . This contradicts the fact that is a PRF. ◻
Solution to Identity authentication: One time passwords
Suppose Alice and Bob have already shared a key . Then the authentication protocol is as follows:
Alice requests Bob for authentication
Bob picks a random and sends to Alice
Alice sends to Bob
Bob checks and accepts the session if the message sent by Alice is exactly , otherwise rejects.
Note: it is not crucial that is random. What is crucial is that each is used at most once to avoid the replay attack. Often in practice, is computed as a function of time. This is what known as the one-time password.
Proof. Assume for contradiction that Mallory succeeds with non-negligible probability. We construct a PPT distinguisher that distinguishes a PRF and a truly random function with non-negligible advantage.
Specifically, is given an oracle and is to conclude is a truly random function or a pseudorandom function. Let be as follows: simulates the interactions of Alice, Bob and Mallory, and whenever is called, replaces by the given oracle . Then, outputs 1 (i.e., is a PRF) if Bob accepts Mallory, and outputs 0 (i.e., is a truly random function) otherwise.
With the above , we now have:
If is a pseudorandom function, then the probability that gives a correct conclusion is non-negligible due to assumption regarding the success probability of Mallory.
On the other hand, if is a truly random function, then the probability that gives a correct conclusion is negligible since the success probability of Mallory is negligible. This is because there are possible values of and Mallory only observes poly() interactions. Therefore, it is extremely unlikely that in the interaction with Mallory, Bob sends an that has already been used before. Therefore, the success probability of Mallory is thus at most , where the first term is the probability that an is reused and the second term is the probability that Mallory guesses correctly.
This implies that the advantage of in distinguishing a truly random function and a pseudorandom function is non-negative. ◻
Existence of PRFs
Proof idea. The idea is to use a length-doubling PRG to construct , and then use the hybrid argument to show that if there is a PPT adversary that breaks the security of then we can construct a PPT distinguisher that breaks the security of . ◻