We can generalize the definition of CPA security for symmetric$-$key encryption to the multi$-$key setting.

In this setting, instead of only $1$ key, the challenger selects $Q>0$ keys. The adversary can query for

the encryption under any of the $Q$ keys. The adversary wins if it can attack any of the $Q$ keys. This is

defined as follows.

MULTI$-$IND$-$CPA ${?}_Q()$:

Chal picks a uniformly random bit blarr$\{0,1\}.$

Chal generates $Q$ secret symmetric keys, $k_j$larrKeyGen$(1^{})$ for each jin$\{1,$dots,$Q\}.$

Repeat:

Adv chooses widehat$(m)$ and $j$ and sends it to Chal.

Chal sends Enc$(1^{},k_j,(widehat(m)))$ backs.

Adv chooses messages $m_0,m_1$ and i and sends to Chal.

Chal sends Enc$(1^{},k_i,m_b)$ to Adv $($where bin$\{0,1\}$ is the random bit selected at the beginning$).$

Adv outputs the guess $b^{\text{'}},$ and wins if $b=b^{\text{'}}.$

An encryption scheme $($KeyGen$,$ Enc, Dec$)$ is $Q-$multi$-$key CPA$-$secure if$,$ for every PPT adversary $A,$

the probability of it winning the above game is at most $\frac{1}{2}+$

$u()$ for some negligible function

$u().$

Problem $3\mathrm{.}1(3$ points$).$ Prove that, for $Q$ bounded by a polynomial in $,$ an encryption scheme is

$Q-$multi$-$key CPA$-$secure if and only if it is CPA$-$secure$.$