*Scribed by Madhur Tulsian*

** Summary **

Today we show how to construct a pseudorandom function from a pseudorandom generator. Continue reading

2

*Scribed by Madhur Tulsian*

** Summary **

Today we show how to construct a pseudorandom function from a pseudorandom generator. Continue reading

*Scribed by Anupam Prakash *

** Summary **

Today we finish the analysis of a construction of a pseudorandom permutation (block cipher) given a pseudorandom function.

*Scribed by Siu-Man Chan *

** Summary **

Given one way permutations (of which discrete logarithm is a candidate), we know how to construct pseudorandom functions. Today, we are going to construct pseudorandom permutations (block ciphers) from pseudorandom functions.

Today we finish the analysis of a construction of a pseudorandom permutation (block cipher) given a pseudorandom function.

** Summary **

Today we give a construction of a pseudorandom permutation (block cipher) given a pseudorandom function, and we begin its analysis. Continue reading

** Summary **

Today we show how to construct a pseudorandom function from a pseudorandom generator. Continue reading

** Summary **

Today we complete the proof that it is possible to construct a pseudorandom generator from a one-way permutation Continue reading

*Scribed by Manohar Jonnalagedda *

** Summary **

Having introduced the notion of CPA security in the past lecture, we shall now see constructions that achieve it. Such constructions shall require either *pseudorandom functions* or *pseudorandom permutations*. We shall see later how to construct such objects.

**1. Pseudorandom Functions **

To understand the definition of a pseudorandom function, it’s good to think of it as a pseudorandom generator whose output is *exponentially long*, and such that each bit of the output is efficiently computable given the seed. The security is against efficient adversaries that are allowed to look at at any subset of the exponentially many output bits.

Definition 1 (Pseudorandom Function)A function is a -secure pseudorandom function if for every oracle algorithm that has complexity at most we have

Intuitively, this means that an adversary wouldn’t be able to distinguish outputs from a purely random function and a pseudorandom function (upto a certain additive error). Typical parameters are , in which case security as high as is conjectured to be possible.

As usual, it is possible to give an asymptotic definition, in which is required to be negligible, is allowed to be any polynomial, and is required to be computable in polynomial time.

**2. Encryption Using Pseudorandom Functions **

Suppose is a pseudorandom function. We define the following encryption scheme.

- : pick a random , output

This construction achieves CPA security.

Theorem 2Suppose is a secure pseudorandom function. Then the above scheme is -secure against CPA.

The proof of Theorem 2 will introduce another key idea that will often reappear in this course: to first pretend that our pseudorandom object is truly random, and perform our analysis accordingly. Then extend the analysis from the pseudorandom case to the truly random case.

Let us therefore consider a modified scheme , where instead of performing , we do , where is a truly random function. We need to look at how secure this scheme is. In fact, we will actually prove that

Lemma 3is CPA secure.

*Proof:*

In the computation of algorithm given oracle and input the ciphertext , let us define REP to be the event where gets the messages from the oracle, such that equals one of the .

Then we have

similarly,

so

Now the first difference is the difference between two numbers which are both between and , so it is at most , which is at most .

The second difference is zero, because with a purely random function there is a 1-1 mapping between every random choice (of ) which makes the first event happen and every random choice that makes the second event happen. ◻

We have shown that with a purely random function, the above encryption scheme is CPA-secure. We can now turn our eyes to the pseudorandom scheme , and prove Theorem 2.

*Proof:* Consider the following four probabilities, for messages , , and algorithm :

From the previous proof, we have . If we are able to show that , , then we have .

So, it remains to show that

Suppose, by contradiction, this is not the case. We will show that such a contradiction implies that is not secure, by constructing an oracle algorithm that distinguishes from a truly random function.

For an oracle , we define to be the following algorithm:

- pick a random and compute
- simulate ; every time makes an oracle query , pick a random and respond to the query with

Note that if is given the oracle , then the computation is exactly the same as the computation , and if is given the oracle , where is a random function, then the computation .

Thus, we have

which means that

The complexity of is at most the complexity of times (the time needed to translate between oracle queries of and oracle queries of ), and so if has complexity then has complexity . This means that (4) contradicts the assumption that is secure. ◻

*Scribed by Ian Haken*

** Summary **

The encryption scheme we saw last time, based on pseudorandom functions, works and is CPA-secure, but it is not used in practice. A disadvantage of the scheme is that the length of the encryption is twice the length of the message being sent.

Today we see the “counter mode” generalization of that scheme, which has considerably smaller overhead for long messages, and see that this preserves CPA-security.

We then give the definition of *pseudorandom permutation*, which is a rigorous formalization of the notion of *block cipher* from applied cryptography, and see two ways of using block ciphers to perform encryption. One is totally insecure (ECB), the other (CBC) achieves CPA security.

**1. The Randomized Counter Mode **

Recall that a pseudorandom function is a function which looks approximately like a random function . With the encryption method from the previous lecture (in which the ciphertext is a random followed by ) the encryption of a message is twice as long as the original message. We now define an encryption method which continues to use a pseudorandom function, but whose ciphertext overhead is marginal.

Suppose we have a pseudorandom function . We describe an encryption scheme that works for messages of variable length. We assume without loss of generality that the length of the message is a multiple of , and we write a plaintext of length as , a sequence of blocks of length .

- :
- pick a random
- output

(When is a binary string in and is an integer, means the binary representation of the sum mod of (seen as an integer) and .)

Observe that the ciphertext length is which is a negligable overhead when .

Theorem 1Suppose is a -secure pseudorandom function; then, when used to encrypt messages of length , the above scheme is -CPA secure.

Example 1Consider the values which these variables might take in the transmission of a large (e.g. 4GB) file. If we let , , , , then we end up with an approximately -CPA secure transmission.

*Proof:* Recall the proof from last time in which we defined , where is a truly random function. Given messages and a cryptanalytic algorithm , we considered:

- (a)
- (b)
- (c)
- (d)

We were able to show in the previous proof that , , and , thus showing that . Our proof will follow similarly.

We will first show that for any

hence showing and . Suppose for a contradiction that this is not the case, i.e. and where is of complexity such that

Define as a program which simulates . (Note that has complexity ). Noting that and , this program would be a counterexample to being -secure.

Now we want to show that , , and such that the complexity of is ,

As in the previous proof, we consider the requests may make to the oracle . The returned values from the oracle would be , where ranges between and the number of requests to the oracle. Since has complexity limited by , we can assume . As before, if none of the overlap with (for ) then only sees a random stream of bits from the oracle. Otherwise, if for some , then can recover, and hence distinguish, and . Hence the probability of distinguishing is plus the probability of a collision.

Note that the th oracle request will have a collision with some iff . If we have then obviously there is a collision, and otherwise so so there is a collision with . If is outside this range, then there is no way a collision can occur. Since is chosen randomly from the space of , there is a probability that the th oracle request has a collision. Hence is an upper bound on the probability that there is a collision in at least one the oracle requests.

Combining these results, we see that , i.e.

◻

**2. Pseudorandom Permutations **

** 2.1. Some Motivation **

Suppose the message stream has known messages, such as a protocol which always has a common header. For example, suppose Eve knows that Bob is sending an email to Alice, and that the first block of the message is the sender’s email. That is, suppose Eve knows that “bob@cs.berkeley.edu”. If Eve can insert or modify messages on the channel, then upon seeing the ciphertext she could then send to Alice the stream “bob@cs.berkeley.edu” “eve@cs.berkeley.edu” . The result is that the message received by Alice would appear to be sent from “eve@cs.berkeley.edu”, but remain otherwise unchanged.

** 2.2. Definition **

Denote by the set of permutations .

Definition 2A pair of functions , is a -secure pseudorandom permutation if:

- For every , the functions and are permutations (i.e. bijections) and are inverses of each other.
- For every oracle algorithm that has complexity at most

That is, to any algorithm that doesn’t know , the functions look like a random permutation and its inverse.

In applied cryptography literature, pseudorandom permutations are called *block ciphers*.

How do we construct pseudorandom permutations? There are a number of block cipher proposals, including the AES standard, that have been studied extensively and are considered safe for the time being. We shall prove later that any construction of pseudorandom functions can be turned into a construction of pseudorandom permutations; also, every construction of pseudorandom generators can be turned into a pseudorandom function, and every one-way function can be used to construct a pseudorandom generator. Ultimately, this will mean that it is possible to construct a block cipher whose security relies, for example, on the hardness of factoring random integers. Such a construction, however, would not be practical.

**3. Encryption Using Pseudorandom Permutations **

Here are two ways of using Pseudorandom Functions and Permutations to perform encryption. Both are used in practice.

** 3.1. ECB Mode **

The Electronic Code-Book mode of encryption works as follows

Exercise 1Show that ECB is message-indistinguishable for one-time encryption but not for two encryptions.

** 3.2. CBC Mode **

In its simplest instantiation the Cipher Block-Chaining mode works as follows:

- : pick a random string , output

Note that this similar to (but a bit different from) the scheme based on pseudorandom functions that we saw last time. In CBC, we take advantage of the fact that is now a permutation that is efficiently invertible given the secret key, and so we are allowed to put the inside the computation of .

There is a generalization in which one can use the same random string to send several messages. (It requires synchronization and state information.)

- :
- pick a random string
- output where

- where

Exercise 2This mode achieves CPA security.

Note that CBC overcomes the above problem in which Eve knows a particular block of the message being sent, for if Eve modified in the encryption that Bob was sending to Alice (as in the example above) then the change would be noticeable because would not decrypt correctly.