Please briefly explain why you feel this question should be reported.

Please briefly explain why you feel this user should be reported.

# Introduction to Cryptography Assignment

CS 3333 Introduction to Cryptography
Assignment 1
Q1 [5] Consider the shift cipher, where we have the following distribution over the message space M:
Pr[M = a] = 0.7 and Pr[M = z] = 0:3: Here M is the random variable denoting the plaintext. What
is the probability that the ciphertext is c? What is the probability that message z was encrypted,
given that we observe the ciphertext c ?
Q2 [6+6] For each of the following encryption schemes, state whether the scheme is perfectly secret.
(a) The message space is M = {0, . . . , 4}. Algorithm Gen chooses a uniform key from the key
space {0, . . . , 5}. Enck (m) returns [k + m mod 5], and Deck(c) returns [c – k mod 5].
(b) The message space is M = {m ∈ {0, 1}` : the last bit of m is 0}. Gen chooses a uniform key
from {0, 1}`−1 . Enck (m) returns ciphertext m ⊕ (kk0), and Deck (c) returns c ⊕ (kk0). Note: k
means concatenation.
Q3 [5+5+5 points]The shift, substitution, and Vigenère ciphers can also be defined over the
128-character ASCII alphabet (rather than the 26-character English alphabet).
(a) Provide a formal definition of each of these schemes in this case.
(b) Discuss how the attacks we have shown in this chapter can be modified to break each of these
modified schemes.
Q4 [8 points] Let |G(s)| = `(|s|) for some `. Consider the following experiment:
The PRG indistinguishability experiment PRGA,G(n):
(a) A uniform bit b ∈ {0, 1} is chosen. If b = 0 then choose a uniform r ∈ {0, 1}`(n) ; if b = 1 then
choose a uniform s ∈ {0, 1}n and set r := G(s).
(b) The adversary A is given r, and outputs a bit b’.
(c) The output of the experiment is defined to be 1 if b’ = b, and 0 otherwise.
Provide a definition of a pseudorandom generator based on this experiment, and prove that your
definition is equivalent to the definition discussed in class (See slide titled Pseudo Random Number
Generator: Definition ) (That is, show that G satisfies your definition if and only if it satisfies the
definition discussed in the class.)
1