Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
Consider the following encryption and decryption functions where $\mathbb{Z}_{N}^{*}$ is a cyclic multiplicative group, $g$ is a generator for the group and $F$ is a keyed PRF.
$E(m, i, k) = m \times g^{F_k(i)} \bmod N$
$D(c, i, k) = c \times g^{-F_k(i)} \bmod N$
Is the above scheme IND-CPA? How would I prove it?
My first thought is that I need to show that if $g$ is a generator then $m \times g^{F_k(i)} \bmod N$ is a bijection but I am not sure how to come up with a formal proof.
Here is how I would approach the proof (this is a sketch):
A proof with a similar approach can be found in the proof of Theorem 3.26 on p.89 of Introduction To Modern Cryptography.
Step 1) Prove that replacing $F_k$ with a uniform function $f$ only gives the adversary negligibly different advantage in the indistinguishability game. To do this, choose a distinguisher $D$ for the pseudorandom keyed function $F_{k}$. $D$ has access to an oracle that is either equal to $F_k$ or $f$. Have $D$ simulate a view of the indistinguishability game for $A$ by choosing random $i$ and having the oracle output either $f(i)$ or $F_k(i)$ ($D$ doesn't know which one). If $A$ is correct, $D$ outputs 1, otherwise $D$ outputs 0. Since $F_k$ is a pseudorandom function it follows that $A$ must win the game with the actual encryption scheme negligibly different amount than with the modified encryption scheme (where $F_k$ is replaced by $f$).
Step 2) Prove that the modified encryption scheme, where $F_k$ is replaced by $f$ is IND-CPA secure. This you can do via probability analysis. First by noticing that since $g$ is the generator of the group, every element in the group can be expressed via $g^{x}$ for an integer $x$. Therefore, since $f$ is uniform, $g^{f}$ is uniformly distributed in the multiplicative group $\mathbb{Z}_{N}^{*}$ . Next, since $g$ is the generator, and since $m\in\mathbb{Z}_{N}^{*}$, $m=g^{x}$ from some integer x. Therefore we can write $E(m, i, k) = m \times g^{f(i)} \bmod N = g^{x} \times g^{f(i)} \bmod N = g^{x+f(i)} \bmod N$. Since $f$ is uniform, $x+f(i)$ is also uniform and hence $g^{x+f(i)} \bmod N$ is uniform as well. Complete the proof by letting $q(n)$ be the upper bound of number of queries that $A$ can send to the Oracle of the indistinguishability game. The only way A has an advantage is if the same $i$ is used twice. if $i$ is uniformely chosen from ${\{0,1\}}^{n}$, then this probability is $q(n) \times 2^{-n}$ which is negligible.
