Adaptive Special Soundness: Improved Knowledge Extraction by Adaptive Useful Challenge Sampling

본문 미리보기

The knowledge soundness of an interactive proof is often proven via various ``special soundness (SS)'' frameworks which separate knowledge extraction into: (1) extracting accepting transcripts conforming to some structure; (2) recovering a witness from structure-conforming transcripts. However, even access-structure SS [TCC'23], one of the most general, does not handle proof systems employing probabilistic tests, a protocol design technique common in more advanced and especially succinct proo