Cryptology ePrint Archive: Report 2006/356

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

Emilia K\"{a}sper and 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.

Category / Keywords: public-key cryptography / Coin flipping, forking lemma, generic signature schemes, matrix algorithms, proofs of knowledge, special soundness

Publication Info: First public draft

Date: received 20 Oct 2006

Contact author: h lipmaa at cs ucl ac uk

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20061020:102812 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]