USign Queries. E can request an undeniable signature for input (XI, m) where XI ∈ X , and m ∈ M. If XI XJ then B runs USign(xI, m) to produce a signature σ ∈ S. If XI = XJ then B queries m on the H1 oracle and receives some response gri . If the tuple on LH1 containing m is the kth tuple, then B aborts. Otherwise B retrieves the value ri from the tuple containing m on LH1 outputs σ. and computes σ = Xri mod p. B Conf/Deny Queries: E can request a confirmation or denial proof for input (XP , XV , m, σ) where XP , XV ∈ X , XV =ƒ XP , m ∈ M and σ ∈ S. B keeps a list LCD of all distinct Conf/Deny queries that E makes. Case 1 If XP ƒ= XJ then C takes the private key xP corresponding to XP and proceeds as follows. C runs ConfGen(XP , XV , xP , m, σ) to produce an NIDV proof πC ∈ PC. If ConfVerify(XP , XV , m, σ, πC) returns accept, then C outputs πC. Other- wise C runs DenyGen(XP , XV , xP , m, σ) to produce an NIDV proof πD ∈ PD which it outputs. Case 2 If XP = XJ then B queries m on the H1 oracle. If the tuple (m, ri) on LH1 containing m is not the kth tuple, B retrieves the value ri from the tuple on LH1 and computes σj = Xri mod p. Case 2a If σj = σ then B simulates ConfGen by simulating an NIDV EDL proof as follows. B picks random w, r, t, h ∈ Zq and computes: c = gwXr mod p G = gdX(h+w) mod p D = H1(m)dσ(h+w) mod p If the H2 oracle has previously been queried on input c, G, D, m, σ, XP , XV , then B starts again by picking new w, r, t, h. Otherwise B sets str = c, G, D, m, σ, XP , XV , adds the tuple (str, h) to LH2 , and outputs πC = (w, r, h, d). Case 2b If XP = XJ , and σj =ƒ σ or (m, ri) is the kth tuple on LH1 , then B proceeds as follows. If (m, ri) is the kth tuple on LH1 , then B selects some random value y ∈ Zq∗ and computes σj = gbriy = H1(m)y mod p. If σj = σ, then B starts again by picking a new y. Now B has some value σj ƒ= σ (generated at the beginning of Case 2 or in Case 2b) and B simulates DenyGen by simulating an NIDV IDL proof as follows. B picks random t, w, r, h, d1, d2 ∈ Zq and computes: C = ( σj )t mod p σ c = gwXr mod p G = gd1 X−d2 mod p D = Ch+wH1(m)d1 σ−d2 mod p If the H2 oracle has previously been queried on input C, c, G, D, m, σ, XP , XV , then B starts the DenyGen simulation again by picking new t, w, r, h, d1, d2. Otherwise B sets str = C, c, G, D, m, σ, XP , XV , adds the tuple (str, h) to LH2 , and outputs πD = (C, w, r, h, d1, d2).
