Monotone Batch NP-Delegation with Applications to Access Control
Monotone Batch NP-Delegation with Applications to Access Control
复制标题
单调批量 NP 委托与访问控制应用程序
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Y. Kalai
中科院分区：
文献类型：
--
作者：
Zvika Brakerski;Y. Kalai
考虑对某些资源的访问策略，该策略仅允许拥有特定属性集的系统用户访问。具体地，我们考虑这样的访问结构由单调公式(或对数深度电路)F：{0，1}→{0，1}定义的情况，其中N是可能属性的数目。在这项工作中，我们提出了两个结果，我们认为这两个结果是个人感兴趣的，即使不考虑上述应用，并展示了如何结合它们来实现一个简洁的单边界私有访问控制协议。也就是说，验证者可以确信经批准的用户(即，持有经批准的一组属性的用户)正在访问该系统，而无需学习关于该用户或该组属性的任何附加信息。首先，假设一个计算性的PIR方案(例如，它可以基于LWE假设的多项式难度)，我们为任何NP语言构造了一个简洁的单轮(2-消息)协议，用于委托单调批量L计算。明确地说，对于每N个∈N，每个x1，.。。，xN∈{0，1}和每个单调公式F：{0，1}→{0，1}，一个证明者可以简洁地证明F(1x1∈L，.。。，1xN∈L)=1，其中1xi∈L=1当且仅当xi∈L，并且其中通信复杂性为m·PolyLog(N)，其中m是单个见证的长度。其次，假设一个具有统计发送者私密性的准多项式安全的双消息不经意传输方案(可以基于DDH、QR或DCR假设的准多项式硬性)，我们展示了如何将任何单轮协议转换为见证不可区分协议，并且具有相似的通信复杂度。
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.