Paper 2021/1265

Special Soundness in the Random Oracle Model

Douglas Wikström

Abstract

We generalize the knowledge extractor for constant-round special sound protocols presented by Wikström (2018) to a knowledge extractor for the corresponding non-interactive Fiat-Shamir proofs in the random oracle model and give an exact analysis of the extraction error and running time. Relative the interactive case the extraction error is increased by a factor $\ell$ and the running time is increased by a factor $O(\ell)$, where $\ell$ is the number of oracle queries made by the prover. Through carefully chosen notation and concepts, and a technical lemma, we effectively recast the extraction problem of the notoriously complex non-interactive case to the interactive case. Thus, our approach may be of independent interest.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. Minor revision.
Keywords
Fiat-Shamirrandom oracle modelwitness extractionknowledge extractionproof of knowledgesoundness errorknowledge errorexact reduction
Contact author(s)
dog @ kth se
History
2021-09-22: received
Short URL
https://ia.cr/2021/1265
License
Creative Commons Attribution
CC BY

BibTeX

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