I'm working through Boneh and Shoup's "Graduate Course in Applied Cryptography", and have just finished reading the chapter on stream ciphers and PRGs.

The first exercise for this chapter introduces the notion of semantic security of a cipher for random plaintext messages. Formally, for a cipher $\mathcal{E}=(E, D)$ defined over $(\mathcal{K}, \mathcal{M}, \mathcal{C})$, we define an attack game where the challenger (instead of the adversary $\mathcal{A}$) chooses two messages $(m_0, m_1) \xleftarrow{R} \mathcal{M}$ uniformly at random from the message space, and encrypts $m_b$ in Experiment $b \in \{0, 1\}$, sending the adversary the resulting ciphertext $c$. $\mathcal{A}$ then sends back a single bit $\hat{b} \in \{0, 1\}$ to end the game. $\mathcal{A}$'s advantage in this game is then defined as

$$ SSRadv[\mathcal{A}, \mathcal{E}] = \left|Pr[\hat{b}=1|b=0] - Pr[\hat{b}=1|b=1]\right| $$

and $\mathcal{E}$ is said to be semantically secure for random plaintexts if $SSRadv[\mathcal{A}, \mathcal{E}]$ is negligible for any efficient adversary $\mathcal{A}$.

The main body of the question asks about how one would build a cipher $\mathcal{E}'=(E', D')$ defined over $(\mathcal{K}', \mathcal{M}', \mathcal{C}')$ that is semantically secure in the "normal sense" (i.e. in an attack game where the adversary chooses $m_0$ and $m_1$), using an SSR-secure (as defined above) cipher $\mathcal{E}$ as a starting point. For complete context, the problem also states that $\mathcal{K}=\mathcal{K}', \mathcal{M}=\mathcal{M}'$.

Given the topic of the preceding chapter, it feels like a natural solution here is to use a secure PRG $G$. Specifically, let $G$ be a secure PRG defined over $(\mathcal{M}, \mathcal{M})$, and then for a given key $k \in \mathcal{K}$ and message $m \in \mathcal{M}$, define $E'(k, m) = E(k, G(m))$. Intuitively, G transforms any chosen plaintext $m$ into an essentially random element of $\mathcal{M}$, and then the random semantic security of $\mathcal{E}$ implies the semantic security of $\mathcal{E}'$. For brevity, I won't try to spell out the actual security proof here.

My main concern here arises when trying to define what the decryption algorithm $D'$ would look like here. In order to undo the application of $G$, we'd need $G$ to have an inverse, and since $G$ is defined over $(\mathcal{M}, \mathcal{M})$, this implies that $G$ is a bijection. This seems like it would contradict the assumed security of $G$; if we can readily define an inverse for $G$, then we could retrieve any seed from its corresponding image in $G$.

  1. Is it possible to have a secure PRG $G$ that is also a bijection, and if so are there restrictions on $\mathcal{M}$ (e.g. $\mathcal{M}$ is super-poly in the security parameter, etc.)?

  2. Is there a different approach to building $\mathcal{E}'$ that gets around this potential security flaw?


1 Answer 1


There are a few fundamental problems with your approach:

  • When you use the construction $m \mapsto E(k,G(m))$ in the context of the standard CPA game, you are feeding adversarially chosen values into the PRG $G$. PRG security does not guarantee anything about PRG outputs in this setting. PRG security can only be applied when the PRG input is uniformly chosen, and used nowhere else in the system (in particular, it can't be known to / chosen by the adversary).

  • As you mention, decryption requires $G$ to have an efficiently computable inverse, which is incompatible with PRG security. The alternative is that $G$ has no stretch, which basically defeats the purpose of a PRG. If you relax the stretch requirement of a PRG, then even the identity function is a secure PRG in the sense of its outputs looking random. Clearly when you use the identity function in your construction, you haven't actually done anything to $\mathcal{E}$.

Is there a different approach to building $\mathcal E′$ that gets around this potential security flaw?

Yes, but I don't know how to give a reasonable hint without trivializing the problem. You don't need to introduce any additional crypto primitives beyond the original scheme $\mathcal{E}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.