# How do I prove that an encryption based on a multiplicative cyclic group is IND-CPA?

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.

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.