Cryptology ePrint Archive: Report 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).

Category / Keywords: Attribute-based signatures, generic constructions, lattices, NIZK proof systems.

Original Publication (with major differences): IACR-PKC-2018

Date: received 6 Jan 2018, last revised 6 Jan 2018

Contact author: shuichi katsumata000 at gmail com, elkaafarani@maths ox ac uk

Available format(s): PDF | BibTeX Citation

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

Version: 20180107:004450 (All versions of this report)

Short URL: ia.cr/2018/022


[ Cryptology ePrint archive ]