Reduction guesses

[mckaguem]

Eg. multi-party PKE. Reduction guesses a particular key. Fails if adversary selects a different key.

• Calculation of overall advantage when a step has a multiplicative advantage
• Examples of how to step from a game with a random guesses to games without a guess

[dstebila]

Game n
...
for i = 1 to numparties:
    (pk[i], sk[i]) = PKE.KeyGen()
...
(partynum, answer) = A(pkset)
...

Experiment 0
F()

Experiment 1 main
experiment_x = UniformlySample(supplied set)
F() up to and including when A sets a particular variable
if experiment_x != particular variable set by A:
    return random bit
// maybe can push the above statement to the end, but need to make sure that particular variable isn't changed and that no returns before the end allow to bypass
F() continues

Game n+1
partynumguess = UniformlySample(Z_numparties)
...
for i = 1 to numparties:
    (pk[i], sk[i]) = PKE.KeyGen()
...
(partynum, answer) = A(pkset)
if partynumguess != partynum:
    return random bit
...

Game n+2
partynumguess = UniformlySample(Z_numparties)
...
for i = 1 to partynumguess-1:
    (pk[i], sk[i]) = PKE.KeyGen()
(pk[partynumguess], sk[partynumguess]) = PKE.KeyGen() // this line comes from the reduction
for i = partynumguess+1 to numparties:
    (pk[i], sk[i]) = PKE.KeyGen()
...
(partynum, answer) = A(pkset)
if partynumguess != partynum:
    return random bit
...