Zero-knowledge (ZK) proofs have emerged as powerful tools for enabling secure and privacy-preserving computations. While practical ZK systems have achieved remarkable efficiency for problems in NP, their applicability beyond NP remains largely unexplored. In this talk, I will address that question by focusing on Quantified Boolean Formulas (QBFs)—a canonical PSPACE-complete problem that captures the complexity of many verification and strategic reasoning tasks. Existing ZK methods struggle to handle such problems efficiently. I will present two new protocols that make zero-knowledge proofs for PSPACE practical: the first efficiently verifies the falsity of a QBF via quantified resolution, and the second enables proofs of knowledge of a winning strategy. Together, these protocols make it possible to construct zero-knowledge proofs for PSPACE-complete statements that were previously out of reach. This talk is based on work that will appear at IEEE Security & Privacy 2026.