0
$\begingroup$

Here is the Scheme:

enter image description here

enter image description here

Here is the HIDE game:

enter image description here

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!

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

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.