How to give a hybrid proof that IND CPA secure implies multiple query IND CPA secure and vice versa?

user108520

3/24/24, 10:57 PM

For a public-key encryption scheme (Gen,Enc,Dec), the textbook definition of IND-CPA security is the following:

The challenger runs (pk,sk)←Gen and sends pk to the adversary.
The adversary performs some computation, chooses (m0,m1) and sends them to the challenger.
The challenger runs ct←$Enc(pk,mb) , b←${0,1}, and sends ct to the adversary.
The adversary performs some computation and outputs a bit b′.

For a secret-key encryption scheme (G,E,D), the definition must allow multiple encryptions. A usual version is:

The challenger runs k←$G , b←${0,1}.
The adversary can adaptively present many challenges (mi0,mi1) and get back E(k,mib).
The adversary outputs a bit b′.

Can we provide a hybrid argument to prove that an adversary that wins the second game with say, Q queries, can also win the first game? How would that argument be structured?

0 + 1

chosen-plaintext-attack

Mikero

3/25/24, 4:25 PM

The first game is about public-key encryption and the second one is about symmetric-key encryption. It sounds like you are asking whether a public-key encryption is also a symmetric-key encryption?

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: How to give a hybrid proof that IND CPA secure implies multiple query IND CPA secure and vice versa?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.