1
$\begingroup$

I am working on understanding the concepts and approach behind digital signatures that are based on lattices specifically the GPV algorithm.

During the security reduction of this method, the forking lemma is used to show that the attacker can generate a correct forged message.

I read about the forking lemme and I am not able to understand it completely and its application here. This is mainly because I am not predominantly from a math background.

I am looking for a simple explanation of how forking lemma works to forge a signature in this scheme.

$\endgroup$
1
  • 1
    $\begingroup$ The GPV security reduction does /not/ use the forking lemma. Indeed, it “programs” the random oracle “consistently” and does not use any “rewinding” techniques. So it’s unclear what you’re asking about, at least in the context of GPV. $\endgroup$ Commented Oct 2, 2018 at 22:11

1 Answer 1

3
$\begingroup$

While, as Chris said, GPV does not rely on the forking lemma, here is a cute metaphore for it.

Imagine a video game, with n level. The game is tough, and at each level, you have a probability 1/2 to die. If you die you have to restart from scratch. It's running on a very old game console, and you can not save your game. So, you'll need an average of $2^n$ trials before you win the whole game.

The game remains fully deterministic though, and the only source of randomness is your limited skill to reproduce exactly the same sequence of keystrokes on your gamepad.

The forking lemma can been thought as a small device in between your gamepad and the console, that can record your keystroke and replay them. So, if you were lucky enough to succeed level 1, but fail level 2, you can replay exactly the winning sequence of keystrokes for level 1, and therefore directly replay level 2, to try a sequence of keystroke there. With such a strategy, you can win the game playing on average $2n$ levels.

Back to the crypto-world, the deterministic console is the attacker, and the sequence of keystrokes of each level are the responses of the random oracle to each hash queries. Using the forking lemma strategy, you can try several response for a given request, without having to rerandomize all the previous responses. This way, you can somehow trick your attacker to get to a particular situation much more efficiently than hoping a random set of $n$ response will get him there.

$\endgroup$
2
  • $\begingroup$ The algorithm A is said to have input (x, h_1, h_2, h_3, .... , h_q, r) where x is some input, h are the queries and r is a random tape. If A was to fail as in return (0,0) do the queries h_i then get re-sampled? If not, what if A fails q times? $\endgroup$ Commented Jul 18, 2019 at 23:10
  • $\begingroup$ What if there are multiple hash queries in a single execution, how is this played out? $\endgroup$ Commented Jul 18, 2019 at 23:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.