How can we prove that the advantage for this hide game for any adversary is equal 0?

Diego Starr

4/9/23, 4:17 AM

Here is the Scheme:

Here is the HIDE game:

Here is my idea but I am not quite sure. I would appreciate some input.

We want to bring advantage = 0 for all adversaries. We can show that advantage = 0 if we can prove that all of the C values are uniformly random and independent of the Message we give. If we prove that then we can argue that the adversary won't be able to tell which game its in.

So L is a n-bit string chose uniformly at random. C is also random as well since it uses L? I am not sure about this but it seems like the algorithm is basically doing a One-time Pad. We know that OTP is perfectly secure.

Is this correct? What else can I argue to prove advantage=0 for any adversary? Thanks in advance!

0 + 0

encryption

commitments

game

Manish Adhikari

4/9/23, 6:39 AM

You are correct but it's not $C$ is random because it uses $L$, if $L \sim U$ then $L \oplus M \sim U$, regardless of how $M$ is chosen. Thus only $C$ would be perfectly hiding to the adversary but $C$ by itself without $K$ would obviously be a terrible commitment which provides no binding

Manish Adhikari

4/9/23, 6:44 AM

This only happens if $L$ is truly random, if $L$ is say a pesudo random, them while $L \oplus M$ would still be pseudo random, it won't necessarily have same distribution as $L$

Diego Starr

4/9/23, 6:47 AM

@ManishAdhikari what do you mean by L ~ U? Does that mean if L is uniformly random. Sorry still learning the syntax.

Manish Adhikari

4/9/23, 6:59 AM

Yes, it means $L$ is distributed over a uniform distribution, Really it should be $L \sim U[0,2^{n}-1]$ but I ommited the domain.

Diego Starr

4/9/23, 7:03 AM

Thank you so much for your time! @ManishAdhikari

Elon Musk

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

EN: How can we prove that the advantage for this hide game for any adversary is equal 0?

TH: เราจะพิสูจน์ได้อย่างไรว่าข้อได้เปรียบของเกมซ่อนนี้สำหรับฝ่ายตรงข้ามเท่ากับ 0?

RO: Cum putem demonstra că avantajul acestui joc de ascuns pentru orice adversar este egal cu 0?

RU: Как доказать, что преимущество этой игры в прятки для любого противника равно 0?

VI: Làm thế nào chúng ta có thể chứng minh rằng lợi thế của trò chơi trốn tìm này đối với bất kỳ đối thủ nào đều bằng 0?

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.