Paper 2018/375

Witness Indistinguishability for any Single-Round Argument with Applications to Access Control

Zvika Brakerski and Yael Tauman Kalai


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 some monotone function $f:\{0,1\}^N \rightarrow \{0,1\}$, belonging to some class of function $F$ (e.g.\ conjunctions, space bounded computation), where $N$ is the number of possible attributes. In this work we show that any succinct single-round delegation scheme for the function class $F$ can be converted into 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. As a main tool of independent interest, we show that 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, DCR or LWE assumptions), we can convert any single-round protocol into a witness indistinguishable one, with similar communication complexity.

Note: Prior versions of this report contained an additional result about a new batch delegation scheme for monotone formulae (see ePrint history for this report). We removed that result from this work because we believe that it better fits into a different work.

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in PKC 2020
delegationwitness indistinguishabilityaccess control
Contact author(s)
zvika brakerski @ weizmann ac il
2020-02-02: last of 2 revisions
2018-04-30: received
See all versions
Short URL
Creative Commons Attribution


      author = {Zvika Brakerski and Yael Tauman Kalai},
      title = {Witness Indistinguishability for any Single-Round Argument with Applications to Access Control},
      howpublished = {Cryptology ePrint Archive, Paper 2018/375},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.