数学代写|CS346 Cryptography

Problem 1: Encryption and Compression 8 points. You are designing a new web service and would like to take advantage of both encryption and compression when responding to client requests. You are deciding between the following two proposals: (1) encrypt the data first, then compress the result before sending; or (2) compress the data first, then encrypt the result before sending.
(a) If you are optimizing for performance, which option do you prefer? Briefly explain your choice.
(b) Are there any security implications for the option you selected above? Briefly explain.

Problem 2: Pseudorandom Generators 18 points. Let $G:{0,1}^\lambda \rightarrow{0,1}^n$ be a secure PRG. For each of the following functions $G^{\prime}$, indicate whether it is a secure PRG or not. If it is secure, give a formal proof; if not, describe an explicit attack.
(a) $G^{\prime}(s):=G(s) |\left(G(s) \oplus 1^n\right)$, where $1^n$ denotes the all-ones string of length $n$.
(b) $G^{\prime}\left(s_1 | s_2\right):=G\left(s_1\right) \oplus G\left(s_2\right)$.
(c) $G^{\prime}\left(s_1 | s_2\right):=s_1 | G\left(s_2\right)$
Please refer to this handout for examples of how to formally show whether a construction is secure or not.

Problem 3: Encrypting Twice?12 points. Intuitively, encrypting a message twice should not harm security. It turns out that this is not always true. Let (Encrypt, Decrypt) be a cipher and define the “encrypttwice” cipher (Encrypt , Decrypt $_2$ ) where $\operatorname{Encrypt}_2(k, m):=\operatorname{Encrypt}(k$, $\operatorname{Encrypt}(k, m))$.
(a) Give an example of a cipher (Encrypt, Decrypt) that is semantically secure, but (Encrypt ${ }_2$, Decrypt ${ }_2$ ) is not semantically secure.
(b) Suppose (Encrypt, Decrypt) is CPA-secure. Prove that (Encrypt ${ }_2$, Decrypt ) $_2$ ) is also CPA-secure.

Problem 4: Key Leakage in PRFs 25 points. Let $F:{0,1}^n \times{0,1}^n \rightarrow{0,1}$ be a secure PRF. Use $F$ to construct a function $F^{\prime}:{0,1}^{n+1} \times{0,1}^n \rightarrow{0,1}$ with the following two properties:

$F^{\prime}$ is a secure PRF.

If the adversary learns the last bit of the key, then $F^{\prime}$ is no longer secure.
(a) Describe your construction $F^{\prime}:{0,1}^{n+1} \times{0,1}^n \rightarrow{0,1}$. Hint: Consider changing the value of $F$ at a single point.
(b) Show that if $F$ is a secure PRF, then your construction $F^{\prime}$ is a secure PRF.
(c) Show that your construction $F^{\prime}$ is insecure against an adversary that learns the last bit of the key (i.e., at the beginning of the PRF security game, the challenger gives the last bit of the PRF key to the adversary). Specifically, give a complete description of your adversary and compute its advantage. This problem shows that leaking even a single bit of the secret key can break PRF security.
(d) Show how to use $F$ to construct a PRF that remains secure against an adversary who learns any single bit of the secret key. Your solution should not assume any property about $F$ (e.g., $F$ may be completely insecure against adversaries that learn one bit of the key). Prove the security of your construction. To model this security property, consider a variant of the PRF security game where the adversary starts by specifying an index $i$ and the challenger replies with the $i^{\text {th }}$ bit of the PRF key. The rest of the security game proceeds as in the standard PRF security game. Hint: Consider using a larger key-space.