## Cryptology ePrint Archive: Report 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.

Category / Keywords: foundations / Fiat-Shamir, random oracle model, witness extraction, knowledge extraction, proof of knowledge, soundness error, knowledge error, exact reduction

Contact author: dog at kth se

Available format(s): PDF | BibTeX Citation

Short URL: ia.cr/2021/1265

[ Cryptology ePrint archive ]