International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Special Soundness Revisited

Authors:
Douglas Wikström , KTH Royal Institute of Technology
Download:
DOI: 10.62056/aep2c3w9p
URL: https://cic.iacr.org//p/1/3/25
Search ePrint
Search Google
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 a concentrated running time.

BibTeX
@article{cic-2024-34836,
  title={Special Soundness Revisited},
  journal={cic},
  publisher={International Association for Cryptologic Research},
  volume={1, Issue 3},
  url={https://cic.iacr.org//p/1/3/25},
  doi={10.62056/aep2c3w9p},
  author={Douglas Wikström},
  year=2024
}