0
$\begingroup$

enter image description here

It seems like c2 and c3 kinda reveal something but I cannot put my finger on how exactly we can get it.

Edit:

I was confused about whether I can extract r from c3, but it seems like these Hash functions are invertible! (I missed that condition given in the task). Thanks for all comments.

Improve this question
$\endgroup$
2
  • $\begingroup$ What are $H_1$ and $H_2$? $\endgroup$ Commented Nov 11, 2024 at 20:00
  • $\begingroup$ We can assume $H_1$ and $H_2$ are public hashes with output in $\mathbb Z_n^*$. The exercise is about finding an adversary that wins the CPA experiment with non-vanishing advantage. Write down what that adversary must do. Hints: Your adversary can win with near certainty. You don't need to be much creative in how your adversary chooses it's messages, as any two distinct valid messages will do. Your adversary can make use of the public key. It can invoke $H_1$ and/or $H_2$. and one of the two is indispensable. $\endgroup$ Commented Nov 11, 2024 at 20:48

1 Answer 1

Reset to default
1
$\begingroup$

An adversary $\mathcal{A}$ can try to extract $m$ from $c_2$ letting him always win as long as his challenge uses two different $m, m'$. To this end, he must get rid of $H_1(r)$.

Since $H_1, H_2$ and $n$ are public, knowing $r$ enables him to do so (as long as $\gcd(H_1(r), n) = 1$).

Can $\mathcal{A}$ extract $r$? The answer should be apparent given the ciphertext $(c_1, c_2, c_3)$.

Hint:

Extract $r$ from $c_3$ in a similar fashion by eliminating $H_2(m)$.

Improve this answer
$\endgroup$
6
  • $\begingroup$ There's an alternate, equally valid way to win the CPA experiment that does not use $c_2$. $\endgroup$ Commented Nov 12, 2024 at 9:34
  • $\begingroup$ what if gcd(H1(r),n) is not equal to 1). Then H1 or H2 woulnd't be invertible? Therefore, we won't able to extract r from c3? $\endgroup$ Commented Nov 12, 2024 at 11:45
  • $\begingroup$ @fgrieu is his explanation even true? And what other way is there? What would be the best/clearest proof $\endgroup$ Commented Nov 12, 2024 at 11:47
  • $\begingroup$ @fgrieu You're right. That's why $c_1$ is part of the ciphertext although it's not used anywhere. $\endgroup$ Commented Nov 12, 2024 at 13:05
  • $\begingroup$ @AyeLedder Yes, then $H_1(r)$ not invertible. But this cannot happen if we assume that the codomain of $H_1$ is $\mathbb{Z}_n^*$. $\endgroup$ Commented Nov 12, 2024 at 13:15

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.