Discussion 03 Guide

Question 2

a) Suppose you have access to function that takes a 128-bit 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 symmetric-key encryption scheme. That is, define the key generation algorithm, the encryption algorithm, and the decryption algorithm.


Our inspiration for this algorithm comes from the one-time pad. A one-time 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 128-bit padded message. Our scheme is as follows:

  1. Key Generation. Set (a random 128-bit number).
  2. Encryption. We can prevent reuse of one-time 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.

  3. 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 one-time pad. The reason we have this nonce is that it makes the encryption non-deterministic 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.

back up