Paper 2018/1157

Special Soundness Revisited

Douglas Wikström

Abstract

We generalize and abstract the problem of extracting a witness from a prover of a special sound protocol into a combinatorial problem induced by a sequence of matroids and a predicate, and present a parametrized algorithm for solving this problem. The parametrization provides a tight tradeoff between the running time and the extraction error of the algorithm, which allows optimizing the parameters to minimize: the soundness error for interactive proofs, or the extraction time for proofs of knowledge. In contrast to previous work we bound the distribution of the running time and not only the expected running time. Tail bounds give a tighter analysis when applied recursively and concentrated running time.

Note: This is an excerpt of a larger body of work about electronic voting systems which should be readable for democratic reasons, so any suggestions (even about the exposition) are most welcome! I have been unable to follow the literature, so please do help me to give proper credit if I fail to cite relevant prior/independent work.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
proof of knowledgeknowledge extractionspecial soundness
Contact author(s)
dog @ kth se
History
2018-12-03: received
Short URL
https://ia.cr/2018/1157
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/1157,
      author = {Douglas Wikström},
      title = {Special Soundness Revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1157},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/1157}},
      url = {https://eprint.iacr.org/2018/1157}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.