Efficient Zero Knowledge Proofs for Committed Symmetric Boolean Functions from VOLE-in-the-Head

Zero-knowledge (ZK) proofs are a fundamental technique in modern cryptography, enabling verification of statements without revealing additional information. Most of the existing ZK proofs consider the general statement: given a public function \(f:\{0,1\}^n \rightarrow \{0,1\}\) , one’s goal is to prove knowledge of \(\textbf{x}\in \{0,1\}^n\) such that \(f(\textbf{x})=1\) . However, numerous privacy-preserving applications require keeping both the function f and input \(\textbf{x}\) concealed from verifiers. Several works have addressed this issue by designing ZK protocols for proving the correct evaluation of a committed function on a committed input. However, all of them utilized Stern’s framework, resulting in large proof sizes due to the high soundness error of Stern’s protocols. To address this efficiency limitation, we design efficient zero-knowledge proofs for committed functions on committed inputs using a recent VOLE-in-the-Head (VOLEitH) paradigm (Baum et al., Crypto 2023), specialized for symmetric Boolean functions. Our contributions are fourfold. First, we propose a variant of the commitment scheme by Jain et al. (Asiacrypt 2012), together with an efficient ZK protocol of correct opening within the VOLEitH framework. Next, we provide two strategies to convert the statement of \(f(\textbf{x})=1\) , where both f and \(\textbf{x}\) are hidden, into polynomial constraints. We then provide an efficient ZK protocol for proving the correct evaluation of a committed symmetric Boolean function on a committed input. Finally, we implement our new ZK protocol and analyze its concrete efficiency. We achieve a proof size of \(\le 10\) KB and a proving time of \(\le 40\) ms for \(n\le 512\) on a virtual machine running on a standard laptop when targeting 128-bit security level.