A Witness Encryption for Quadratic Arithmetic Programs
摘要
Witness Encryption (WE) enables encryption under computational problems where decryption requires knowledge of a valid witness to a nondeterministic polynomial-time (NP) statement. While theoretical constructions exist for all NP languages using complex assumptions like multilinear maps, practical schemes remain limited to specialized relations. We present the first extractable Witness Key Encapsulation Mechanism (WKEM) for Quadratic Arithmetic Programs (QAPs), the mathematical foundation underlying modern zkSNARKs including Groth16. Our construction transforms Groth16’s verification equations into an encryption mechanism, enabling practical witness encryption for rich algebraic relations expressible as arithmetic circuits. We prove extractability in the Algebraic Group Model combined with the Random Oracle Model, providing a clean reduction to Groth16’s computational knowledge soundness without requiring novel assumptions. Our WKEM composes generically with symmetric encryption to yield a complete extractable WE scheme for QAP relations. We validate our construction through a complete implementation with practical performance: circuits with 162–150K constraints achieve encryption/decryption in \({\sim }20\) ms to \({\sim }1.7\) s. Our approach bridges the gap between WE theory and practice by building on the mature zkSNARK ecosystem while maintaining strong extractability guarantees.