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.

Metadata
Available format(s)
PDF PS
Category
Public-key cryptography
Publication info
Published elsewhere. First public draft
Keywords
Coin flippingforking lemmageneric signature schemesmatrix algorithmsproofs of knowledgespecial soundness
Contact author(s)
h lipmaa @ cs ucl ac uk
History
2006-10-20: received
Short URL
https://ia.cr/2006/356
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2006/356,
      author = {Emilia Käsper and Sven Laur and Helger Lipmaa},
      title = {Black-Box Knowledge Extraction Revisited: Universal Approach with Precise Bounds},
      howpublished = {Cryptology ePrint Archive, Paper 2006/356},
      year = {2006},
      note = {\url{https://eprint.iacr.org/2006/356}},
      url = {https://eprint.iacr.org/2006/356}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.