If $Hash(x)$ is indistinguishable from $Hash(x,a)$, where $x$ is variable and $a$ is a given number?

Huanhuan Chen

3/12/23, 9:57 AM

I try to use a sequence of games to prove a scheme is CCA secure. In the final two games, the ciphertexts are $(c_1^*, Hash(x)\oplus m_b, Hash(x,a))$ and $(c_1^*, random, Hash(x,a))$ respectively, where $c_1 ^*$ and $a$ can be viewed as given numbers, $x$ is a variable and $m_b$ is the challenge message.

The advantage of the adversary in the latter game obviously is 1/2, so if the two games are indistinguishable, then the advantage of the adversary in the original CCA game is also 1/2. Therefore, my question is if $(c_1^*, Hash(x)\oplus m_b, Hash(x,a))$ and $(c_1^*, random, Hash(x,a))$ are indistinguishable.

Or simpler, if $Hash(x)$ is indistinguishable from $Hash(x,a)$, where $x$ is a variable and $a$ is a given number? Thank you for your help.

0 + 0

hash

Manish Adhikari

3/12/23, 12:01 PM

I have deleted my answer because it might be homework. Anyway, do you know any way a cryptographic hash function (that is pre-image and collision resistant) might help you distinguish

Guut Boy

3/12/23, 1:06 PM

It seems what you need to prove is that $Hash(x) \oplus m_b$ (or really just $Hash(x)$) is indistinguishable from random given $c^*_1$ and $Hash(x,a)$. So it really depends on your assumptions on $Hash$ which are not stated in the question.

Huanhuan Chen

3/12/23, 7:36 PM

Thanks. If $Hash$ is (strong) collision resistant here, is it true that $Hash(x)$ is indistinguishable from $Hash(x,a)$ for a given $a$.

Manish Adhikari

3/13/23, 9:27 AM

Like Guut Boy said it looks like you need to see whether $Hash(x) \oplus m_b$ is distinguishable from random or maybe between $Hash(x) \oplus m_1$ and $Hash(x) \oplus m_2$ given $c^*$ and $Hash(x,a)$ since it is IND- game

Manish Adhikari

3/13/23, 9:32 AM

And to answer your question check difference between plain model and random oracle models of hash function. Also if the adversary can influence $a$, there is something you can do even with widely used hash functions based on MD constructions like SHA2 whose collision resistant property is intact (think about it) not just in theoretical constructions of hash functions in plain model.

Elon Musk

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

EN: If $Hash(x)$ is indistinguishable from $Hash(x,a)$, where $x$ is variable and $a$ is a given number?

TH: ถ้า $Hash(x)$ แยกไม่ออกจาก $Hash(x,a)$ โดยที่ $x$ เป็นตัวแปรและ $a$ เป็นตัวเลขที่กำหนด?

RO: Dacă $Hash(x)$ nu se distinge de $Hash(x,a)$, unde $x$ este variabil și $a$ este un număr dat?

RU: Если $Hash(x)$ неотличим от $Hash(x,a)$, где $x$ — переменная, а $a$ — заданное число?

VI: Nếu $Hash(x)$ không thể phân biệt được với $Hash(x,a)$, trong đó $x$ là biến và $a$ là một số đã cho?

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.