Modular Construction and Analysis of Multi-Round Straightline Extractability Compilers

252 / BBB

2026-04-21

Jannis Wunderlich

15:45

Zero-knowledge proof systems are a central tool in modern cryptography, allowing a prover to convince a verifier of a statement's validity without revealing the underlying secret. A central research question is how to make these proof systems non-interactive. While classical transformations such as those of Pass, Fischlin, and Kondi-Shelat successfully achieve that and guarantee straight-line extractability in the Random Oracle Model (ROM), they are inherently limited to three-move $\Sigma$-protocols. Recent works introducing transformations which extend straight-line extractability to multi-round protocols have relied on monolithic, non-generic designs. This thesis investigates the feasibility of a generic, modular compiler that treats an existing three-move straight-line extractability compiler as a black-box building block and extends it to multi-round public-coin protocols. We introduce a recursive compiler that compresses an interactive multi-round protocol layer by layer and analyze how its security and efficiency properties propagate through this recursion. The analysis demonstrates that while the framework successfully preserves completeness, zero-knowledge, and knowledge soundness, the modularity incurs a substantial cost. The repetition parameters required at each recursive level cause an exponential blowup in both runtime and communication complexity, restricting the compiler's efficiency to protocols with a strictly constant number of rounds. Furthermore, preserving the zero-knowledge property requires the input protocol to satisfy 2-Stage special Honest-Verifier Zero-Knowledge, a stronger form of special Honest-Verifier Zero-Knowledge introduced in this work. Ultimately, this thesis provides a clean theoretical framework for modular straight-line extractability, but exposes the asymptotic performance gap between our flexible black-box construction and specialized monolithic transformations.