Don't know how to approach this problem, or where to start. Finding an adversary to a hiding and binding game

I have this problem: I also have the python version of this problem here:

import json
import sys, os, itertools

sys.path.append(os.path.abspath(os.path.join('..')))
from playcrypt.tools import *
from playcrypt.new_tools import *
from playcrypt.primitives import *

from playcrypt.games.game_bind import GameBIND
from playcrypt.simulator.bind_sim import BINDSim

from playcrypt.games.game_hide import GameHIDE
from playcrypt.simulator.hide_sim import HIDESim

return a+b
def MULT(a,b):
return a*b
def INT_DIV(a,N):
return (a//N, a%N)
def MOD(a,N):
return a%N
def EXT_GCD(a,N):
return egcd(a,N)
def MOD_INV(a,N):
res = modinv(a,N)
if res == None:
raise ValueError("Inverse does not exist.")
return res
def MOD_EXP(a,n,N):
return exp(a,n,N)

"""
Let p be a prime of bit length k >= 8 such that (p - 1)/2 is also prime. Let g,
h be two different generators of the group G = Z_p^*. Let CS= (P, C, V) be the
commitment scheme whose consituent algorithms are as follows, where the message
M is in Z_{p-1}:
"""

def P():
pi = (g, h)
return pi

def C(pi, M):
"""
:param pi: Public parameters
:param M: The message to be commited, element of Z_{p-1}
:return: return the commital and decommital key
"""
(g, h) = pi
K = random_Z_N(p-1)
A = MOD_EXP(g, K, p)
B = MOD_EXP(h, M, p)
C_1 = MOD(A*B, p)
C_2 = MOD(M+K, p-1)
return ((C_1, C_2), K)

def V(pi, C, M, K):
"""
:param pi: Public parameters
:param C: The commital
:param M: The message to be verified
:param K: The decommital key
:return: return 1 if the opening is valid and 0 otherwise
"""
(g, h) = pi
(C_1, C_2) = C
if not 0 <= K < p-1 or not 0 <= M < p-1:
return 0
A = MOD_EXP(g, K, p)
B = MOD_EXP(h, M, p)
C_1_prime = MOD(A*B, p)
C_2_prime = MOD(M+K, p-1)
if (C_1 == C_1_prime) and (C_2 == C_2_prime):
return 1
else:
return 0

"""
1. Specify an O(k^3)-time adversary A1 making one query to its LR oracle and
"""

def A1(lr, pi):
"""
This is the adversary that the problem is
asking for. It should return 0 or 1.

:param lr: The oracle supplied by game HIDE
:param pi: The public parameter pi
"""
pass

"""
(Hint: What is the value of g^{(p-1)/2} mod p, and why?)
"""

def A2(pi):
"""
This is the adversary that the problem is
asking for. It should return tuple (C, M_0, M_1, K_0, K_1).

:param pi: The public parameter pi
"""
return ((0, 0), 0, 0, 0, 0)

if __name__ == '__main__':

# Sample random parameters
k = 12
print('Sampling random parameters of bit length k = %d' % k)
p = random.randint(2**(k - 1), 2**k)
while not is_prime(p) or not is_prime((p-1)//2):
p = random.randint(2**(k - 1), 2**k)
g = random_Z_N_star(p)
while (MOD_EXP(g, (p-1)//2, p) == 1) or (MOD_EXP(g, 2, p) == 1):
g = random_Z_N_star(p)
h = random_Z_N_star(p)
while (h == g) or (MOD_EXP(h, (p-1)//2, p) == 1) or (MOD_EXP(h, 2, p) == 1):
h = random_Z_N_star(p)
print('p = %d, g = %d, h = %d' % (p, g, h))

game_hide = GameHIDE(P, C)
sim_hide = HIDESim(game_hide, A1)

game_bind = GameBIND(P, V)
sim_bind = BINDSim(game_bind, A2)

• Try starting with a numerical example. For instance, let $p=563$, $g=2$, $h=5$. Now for the first part, suppose that we have messages $M_0=123$ and $M_1=345$. We query the LR oracle and get (335,306). Can you tell whether this corresponds to $M_0$ or $M_1$? How? Nov 29 '21 at 9:13