2
$\begingroup$

in the context of another setting I was asked the following question.

Suppose the IND-CPA game is played with a symmetric encryption function $E$ that keeps a state of how many encryptions have already been requested by the adversary $A$ during the execution of the game. $E$ always outputs $E(m)=E'(m)$, where $E'$ is an IND-CPA secure encryption scheme, except for the $i$-th request, where $E(m)$ is insecure and trivially reveals the plaintext $m$ instead of invoking $E'$. $i$ is polynomially bounded in the security parameter and $A$ does not know how $i$ is determined (it could be probabilistic and depending on the previous executions of $E$).

Intuitively, I'd say that $E$ is not IND-CPA secure. An Adversary $A$ that just guesses the polynomially bounded $i$ and poses any challenge after $i-1$ encryption requests during the pre-challenge phase would always win the game if he correctly guessed $i$, which happens with non-negligible probability as $i$ is polynomially bounded. However, when trying to do a formal proof of this, I struggle to state an explicit $A$ with a non-negligible advantage, as this $A$ needs a precise specification of the upper-bound of $i$.

I'd be thankful for further discussion and tips about how one could solve my issue.

| improve this question | | | | |
$\endgroup$
  • $\begingroup$ Doesn't $p(\lambda)$ (or was it $p(1^\lambda)$?) suffice as the upper bound? $\endgroup$ – SEJPM♦ Jul 19 '18 at 11:26
  • $\begingroup$ I thought so, too, but I assume $A$ does not know the value of $p(\lambda)$. Just letting him guess $i$ with an upper bound of $n^c$, where c is constant, would be possible? Since in that case some Adversary $A_c$ exists with $p(\lambda) < n^c$, who then would have a non-negligible advantage. $\endgroup$ – Aares Jul 19 '18 at 11:40
  • $\begingroup$ As an unrelated side-note: such an encryption scheme is definitely not left-or-right CPA secure, because you can just encrypt the same two messages until you get one back and deduce the bit from that (however this doesn't imply the security break you want). $\endgroup$ – SEJPM♦ Jul 19 '18 at 11:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.