Discussion 03 Guide
Question 2
a) Suppose you have access to function that takes a 128bit seed and integers , as input. outputs the th (inclusive) through th (exclusive) bits produced by the a pseudorandom generator when it is seeded with seeds.
Use to make a secure symmetrickey encryption scheme. That is, define the key generation algorithm, the encryption algorithm, and the decryption algorithm.
Our inspiration for this algorithm comes from the onetime pad. A onetime pad is secure, as long as the key is never reused in an encryption. We can source a key for the encryption of each message from with being our key (). Let be a 128bit padded message. Our scheme is as follows:
 Key Generation. Set (a random 128bit number).

Encryption. We can prevent reuse of onetime pad keys by keeping track of the random numbers we have consumed from with a variable .
Here, means concat, and we need to concat to our ciphertext for decryption. We also increment by after each encryption so our RNG gives us fresh random bits.

Decryption. Remember . Let be the ciphertext from .
First, unpack from .
b) Explain how using a block cipher in counter (CTR) mode is similar to the scenario described above.
Below is the algorithm for CTR mode: There is a nonce (random number, also known as the initialization vector) that gets encrypted by a block cipher, producing a key for a onetime pad. The reason we have this nonce is that it makes the encryption nondeterministic as long as the nonce is used once per encryption. This is similar to the scheme above because we never reuse bits from .
One advantage of CTR mode is that, unlike our scheme, its computation can be easily parallelized because each partitionâ€™s encryption can be computed independently, given a nonce and a counter. Our scheme requires keeping track of across all encryptions, and also needs one bit from the PRNG for every bit in the message.