Paper 2018/375

Monotone Batch NP-Delegation with Applications to Access Control

Zvika Brakerski and Yael Tauman Kalai

Abstract

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\}^N\rightarrow\{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 single-round 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\in \mathbb{N}$, every $x_1,\ldots,x_N\in \{0,1\}^n$, and every monotone formula $F:\{0,1\}^N\rightarrow \{0,1\}$, a prover can succinctly prove that $F(1_{x_1\in L},\ldots,1_{x_N\in L})=1$, where $1_{x_i\in L}=1$ if and only if $x_i\in L$, and where the communication complexity is $m \cdot 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.