International Association for Cryptologic Research

International Association
for Cryptologic Research


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

Emilia Käsper
Sven Laur
Helger Lipmaa
Search ePrint
Search Google
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.
  title={Black-Box Knowledge Extraction Revisited: Universal Approach with Precise Bounds},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / Coin flipping, forking lemma, generic signature schemes, matrix algorithms, proofs of knowledge, special soundness},
  note={First public draft 13441 received 20 Oct 2006},
  author={Emilia Käsper and Sven Laur and Helger Lipmaa},