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.


1 Answer 1


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.


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.