Monotone Batch NP-Delegation with Applications to Access Control
Consider an access policy for some resource which only allows access to users of the system who own a certain set of attributes. Specifically, we consider the case where such an access structure is defined by a monotone formula (or logarithmic depth circuit) F : {0, 1} → {0, 1}, where N is the number of possible attributes. In this work we present two results, which we believe to be of individual interest even regardless of the above application, and show how to combine them to achieve a succinct singleround private access control protocol. That is, a verifier can be convinced that an approved user (i.e. one which holds an approved set of attributes) is accessing the system, without learning any additional information about the user or the set of attributes. First, assuming a computational PIR scheme (which can be based, for example, on the polynomial hardness of the LWE assumption), we construct for any NP language L, a succinct single-round (2-message) protocol for delegating monotone batch L computations. Explicitly, for every N ∈ N, every x1, . . . , xN ∈ {0, 1}, and every monotone formula F : {0, 1} → {0, 1}, a prover can succinctly prove that F(1x1∈L, . . . ,1xN∈L) = 1, where 1xi∈L = 1 if and only if xi ∈ L, and where the communication complexity is m · polylog(N) where m is the length of a single witness. Second, assuming a quasi-polynomially secure two-message oblivious transfer scheme with statistical sender privacy (which can be based on quasi-polynomial hardness of the DDH, QR or DCR assumptions), we show how to convert any single-round protocol into a witness indistinguishable one, with similar communication complexity.