Paper 2018/022

Attribute-based Signatures for Unbounded Circuits in the ROM and Efficient Instantiations from Lattices

Ali El Kaafarani and Shuichi Katsumata

Abstract

Attribute-based signature (ABS), originally introduced by Maji et al. (CT-RSA'11), represents an essential mechanism to allow for fine-grained authentication. A user associated with an attribute $x$ can sign w.r.t. a given public policy $C$ only if his attribute satisfies $C$, i.e., $C(x)=1$. So far, much effort on constructing bilinear map-based ABS schemes have been made, where the state-of-the-art scheme of Sakai et al. (PKC'16) supports the very wide class of unbounded circuits as policies. However, construction of ABS schemes without bilinear maps are less investigated, where it was not until recently that Tsabary (TCC'17) showed a lattice-based ABS scheme supporting bounded circuits as policies, at the cost of weakening the security requirement. In this work, we affirmatively close the gap between ABS schemes based on bilinear maps and lattices by constructing the first lattice-based ABS scheme for unbounded circuits in the random oracle model. We start our work by providing a generic construction of ABS schemes for unbounded-circuits in the random oracle model, which in turn implies that one-way functions are sufficient to construct ABS schemes. To prove security, we formalize and prove a generalization of the Forking Lemma, which we call "general multi-forking lemma with oracle access", capturing the situation where the simulator is interacting with some algorithms he cannot rewind, and also covering many features of the recent lattice-based ZKPs. This, in fact, was a formalization lacking in many existing anonymous signatures from lattices so far (e.g., group signatures). Therefore, this formalization is believed to be of independent interest. Finally, we provide a concrete instantiation of our generic ABS construction from lattices by introducing a new $\Sigma$-protocol, that highly departs from the previously known techniques, for proving possession of a valid signature of the lattice-based signature scheme of Boyen (PKC'10).

Note: This is the full version of the paper appearing in PKC 2018.

Metadata
Available format(s)
PDF
Publication info
A major revision of an IACR publication in PKC 2018
Keywords
Attribute-based signaturesgeneric constructionslatticesNIZK proof systems.
Contact author(s)
shuichi katsumata000 @ gmail com
elkaafarani @ maths ox ac uk
History
2018-01-07: revised
2018-01-06: received
See all versions
Short URL
https://ia.cr/2018/022
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/022,
      author = {Ali El Kaafarani and Shuichi Katsumata},
      title = {Attribute-based Signatures for Unbounded Circuits in the ROM and Efficient Instantiations from Lattices},
      howpublished = {Cryptology ePrint Archive, Paper 2018/022},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/022}},
      url = {https://eprint.iacr.org/2018/022}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.