On Monotone Formula Composition of Perfect Zero-Knowledge Languages
Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano, Moti M. Yung · SIAM Journal on Computing · 2008
We investigate structural properties of interactive perfect zero-knowledge (PZK) proofs. Specifically, we look into the closure properties of PZK languages under monotone boolean formula composition. This gives rise to new protocol techniques. We show that interactive PZK for random self-reducible (RSR) (and for co-RSR) languages is closed under monotone boolean formula composition. Namely, we present PZK proofs for monotone boolean formulae whose atoms are statements about membership in a PZK language which is RSR (or whose complement is RSR). We also discuss extensions, recent applications, and generalizations of the techniques.