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

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!

• 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 Dec 9, 2021 at 6:39
• 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$ Dec 9, 2021 at 6:44
• @ManishAdhikari what do you mean by L ~ U? Does that mean if L is uniformly random. Sorry still learning the syntax. Dec 9, 2021 at 6:47
• 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. Dec 9, 2021 at 6:59
• Thank you so much for your time! @ManishAdhikari Dec 9, 2021 at 7:03