Paper 2006/356

Black-Box Knowledge Extraction Revisited: Universal Approach with Precise Bounds

Emilia Käsper, Sven Laur, and Helger Lipmaa

Abstract

Rewinding techniques form the essence of many security reductions including proofs for identification and signature schemes. We propose a simple and modular approach for the construction of such proofs. Straightforward applications of our central result include, but are not limited to, the security of identification schemes, generic signatures and ring signatures. These results are well known, however, we generalise them in such a way that our technique can be used off-the-shelf for future applications. We note that less is more: as a side-effect of our less complex analysis, all our proofs are more precise; for example, we get a new proof of the forking lemma that is $2^{15}$ times more precise than the original result by Pointcheval and Stern. Finally, we give the first precise security analysis of Blum's coin flipping protocol with $k$-bit strings, as yet another example of the strength of our results.