# How does forking lemma work in regard to Digital signatures produced by GPV hash and sign algorithm based on lattices?

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.

• 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. Commented Oct 2, 2018 at 22:11

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 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.
• 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? Commented Jul 18, 2019 at 23:10