Score:2

Crypto

Does Enc and Dec need to be a pseudo-random function for a scheme to be CPA secure?

paul lacher

4/18/23, 4:10 PM

I am currently going through past finals' questions as exercises for my exam and there are no solutions provided.

The question I am currently doing is:

Let ∏ = (Enc, Dec, Gen) be a CPA-secure Encryption Scheme. Prove or disprove the following two statements: a) Enc must be a pseudo-random function. b) Dec must be a pseudo-random function.

For a), intuitively I know it must be pseudorandom but I am not sure how to go about proving it in a formal way. Since the adversary has access to an encryption oracle, we want to make sure they can't distinguish between the different messages and does not learn any useful information about the scheme. And since pseudorandom is indistinguishable from random, then it is necessary?

For b), I don't think it is true, just because on the basis of CPA attacks, they dont really involve decryption, so there's no use for it to be a pseudorandom function. However, if Enc is pseudorandom, wouldn't it need a pseudorandom function to decrypt?

Can anyone let me know if this thinking is on the right track , if not could you please provide an explanation?

Thank you.

0 + 0

encryption

randomness

chosen-plaintext-attack

pseudo-random-function

Morrolan

4/18/23, 4:45 PM

Your intuition for a) is pretty much correct. I assume you have formalized IND-CPA-security by means of a 'game' which is played by the adversary? If so - consider your scheme's encryption function was fully deterministic, that is $Enc_{k}(m)$ (by means of the encryption oracle) would always yield the same result for a fixed key $k$ and message $m$. Can you then define an adversary $A$ which has a non-negligible advantage in winning the game?

Morrolan

4/18/23, 4:55 PM

For b), consider what would happen if the scheme's decryption function was non-deterministic. That is, $Dec_k(c)$ would not always yield the same result for a fixed key $k$ and ciphertext $c$. Would such a scheme be useful? Specifically, how would it affect e.g. the correctness property of the scheme?

paul lacher

4/18/23, 5:00 PM

@Morrolan We defined it as P(success)<= 1/2 + negl(n). If it was deterministic then the Adversary would just always receive same ciphertext for same message from the oracle, then there is more than 1/2 chance for adversary to distinguish the different plaintexts. In class, we didn't really model it as a game, so I'm not too sure about that part.

paul lacher

4/18/23, 5:01 PM

@Morrolan Ohh, makes sense for b), thank you!

paul lacher

4/18/23, 5:09 PM

@Morrolan Would the same apply for IND-CCA security? I'm not sure since for CCA, adversary has access to a decryption oracle, would Dec need to be PRF but that doesn't really make sense since we dont want to get a mishmashed message. So Enc would still need to PRF since in the context of CCA security, we saw it in a Public key setting and if there no randomness, then it becomes deterministic.

Morrolan

4/18/23, 5:22 PM

"If it was deterministic then [...] there is more than 1/2 chance for adversary to distinguish the different plaintexts." Yea, pretty much. :) For the exam you might want to precisely describe the steps the adversary $A$ takes, e.g. in what way $A$ calls the encryption oracle, and how they use that output to distinguish whether the ciphertext $c$ they got is an encryption of either $m_0$ or $m_1$ they provided. Having done that you can then also easily determine the exact chance $A$ has in correctly distinguishing this.

Morrolan

4/18/23, 5:32 PM

For IND-CCA security, you can argue the exact same way as you did for IND-CPA.

paul lacher

4/19/23, 3:25 PM

@Morrolan Thank you! It really helped clear things up for me.

Score:1

Crypto

Chris Peikert

4/19/23, 3:36 PM

Some hints:

A pseudorandom function must be a deterministic function from its key and input to its output. Moreover, the outputs should “appear random and independent” when the key is chosen randomly (and fixed) and the inputs are chosen by the attacker.

For (a): in a CPA-secure encryption scheme, can Enc be deterministic in this way? Why or why not?

For (b): in a CPA-secure encryption scheme with a random $sk$, must the outputs of $\text{Dec}_{sk}(\cdot)$ appear random and independent as the attacker varies the input? Why or why not?

0 + 0

paul lacher

4/20/23, 9:06 PM

ohhh, ok thank you!

Elon Musk

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

EN: Does Enc and Dec need to be a pseudo-random function for a scheme to be CPA secure?

TH: Enc และ Dec จำเป็นต้องเป็นฟังก์ชันสุ่มหลอกเพื่อให้โครงร่างมีความปลอดภัย CPA หรือไม่

RO: Enc și Dec trebuie să fie o funcție pseudo-aleatorie pentru ca o schemă să fie sigură CPA?

RU: Должны ли Enc и Dec быть псевдослучайными функциями, чтобы схема была безопасной CPA?

VI: Enc và Dec có cần phải là hàm giả ngẫu nhiên để lược đồ được bảo mật CPA không?

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.