Zero-Knowledge Proofs for Committed Symmetric Boolean Functions

Zero-knowledge proofs (ZKP) are a fundamental notion in modern cryptography and an essential building block for countless privacy-preserving constructions. Recent years have witnessed a rapid development in the designs of ZKP for general statements, in which, for a publicly given Boolean function f: { 0, 1 }ⁿ→ { 0, 1 }, one’s goal is to prove knowledge of a secret input x∈ { 0, 1 }ⁿ satisfying f(x) = b, for a given bit b. Nevertheless, in many interesting application scenarios, not only the input x but also the underlying function f should be kept private. The problem of designing ZKP for the setting where both x and f are hidden, however, has not received much attention. This work addresses the above-mentioned problem for the class of symmetric Boolean functions, namely, Boolean functions f whose output value is determined solely by the Hamming weight of the n-bit input x. Although this class might sound restrictive, it has exponential cardinality 2^{n + 1} and captures a number of well-known Boolean functions, such as threshold, sorting and counting functions. Specifically, with respect to a commitment scheme secure under the Learning-Parity-with-Noise (LPN) assumption, we show how to prove in zero-knowledge that f(x) = b, for a committed symmetric function f, a committed input x and a bit b. The security of our protocol relies on that of an auxiliary commitment scheme which can be instantiated under quantum-resistant assumptions (including LPN). The protocol also achieves reasonable communication cost: the variant with soundness error 2^{- λ} has proof size c· λ· n, where c is a relatively small constant. The protocol can potentially find appealing privacy-preserving applications in the area of post-quantum cryptography, and particularly in code-based cryptography.