2
$\begingroup$

The original CPA game:

  1. The adversary gives two arbitrary messages $m_0$ and $m_1$ to a challenger;
  2. The challenger encrypts an arbitrary message $m_u$, $u∈\{0,1\}$ , and sends the ciphertext to the adversary;
  3. The adversary outputs the guess $u$.

Now I give a revised version of the above CPA game:

  1. The adversary gives two arbitrary sets of messages $M_0$ and $M_1$ to a challenger, where $|M_0|=|M_1|$, and each pair of counterparts are of equal size;
  2. The challenger encrypts an arbitrary set of message $M_u$, $u∈\{0,1\}$, and sends the ciphertexts to the adversary;
  3. The adversary outputs the guess $u$.

If a public-key encryption scheme is CPA-secure is it also secure in this revised version of CPA game?

$\endgroup$
2
  • $\begingroup$ en.wikipedia.org/wiki/Hybrid_argument_(Cryptography) ​ ​ $\endgroup$
    – user991
    Apr 13, 2017 at 21:09
  • 1
    $\begingroup$ Hi Sunny and welcome. You can it the edit line above my name to see the formatting changes that I've made so you can use them in followup posts. $\endgroup$
    – Maarten Bodewes
    Apr 13, 2017 at 21:31

1 Answer 1

1
$\begingroup$

If a public-key encryption scheme is CPA-secure is it also secure in this revised version of CPA game?

Yes, because this is essentially a trimmed down version of Left-or-Right-CPA security (PDF) which is provably equivalent to the first definition you mentioned which is also known as Find-Then-Guess-CPA security.

If your scheme is LoR-CPA secure then you can query all message pairs from the two sets to the LoR oracle and answer any remaining queries $x$ by querying $(x,x)$.

The inverse direction (that the new definition implies LoR) probably requires a Hybrid Argument as indicated in the comments to "extend" the size of the set to all queries. This should go analogous to proving that FtG-CPA security implies LoR-CPA security.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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