Be this the Experiment for multiple COA-security:

  • $PrivK_{\mathcal{A},\Pi}^{mult}(n)$:

  • $(m_0^1 , ... , m_0^t,m_1^1 , ... , m_1^t) \leftarrow \mathcal{A}(1^n), |m_0^i|=|m_1^i| \forall i \in [1,t]$

  • $k\leftarrow Gen(1^n)$

  • $b \leftarrow \{0,1\}$

  • $C = (c_b^1 , ... , c_b^t) \leftarrow (Enc_k(m_b^1) , ... , Enc_k(m_b^t))$

  • $b' \leftarrow \mathcal{A}(C)$

  • if $b' = b$ return 1 else return 0

If $PrivK_{\mathcal{A},\Pi}^{mult}(n) = 1$ $\mathcal{A}$ wins. For a cryptosystem to have that security, there should not exist an adversary that wins that experiment better than $1/2 + negl(n)$, where $negl(n)$ is a negigible function.

Now I want to construct a cryptosystem that has this security but not KPA- or CPA- or CCA-security. My idea:

  • $Gen(1^n)$: Creates a uniform random key $k \leftarrow \{0,1\}^n$
  • $Enc_k(m)$: Create a uniform random number $r \leftarrow \{0,1\}^n$ and create $c = m \oplus PRG(k \oplus r) $. Output $(c,r)$
  • $Dec_k((c,r))$: Create $m = c \oplus PRG(k \oplus r)$ and output $m$

Assume that PRG is a secure pseudo random generator, then this cryptosystem should be multiple COA-secure (or mult-EAV-IND-secure from Katz & Lindell's textbook (2nd edition))

Is that right or did I overlook something?


I think that your design will pass the experiment provided that $t$ is small enough that collisions in $r$ occur with negligible probability.

However, I also think that your design is KPA, CPA and CCA secure unless I have misunderstood.

  • $\begingroup$ I just rethought that idea, and it resulted in a question: Is the given construction the idea behind the pseudorandom functions? $\endgroup$
    – Titanlord
    Nov 24 '21 at 15:27

Your Answer

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

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