Attribute-based signatures from lattices: unbounded attributes and semi-adaptive security

We construct a lattice-based (key-policy) attribute-based signatures (ABS) scheme which supports attributes of unbounded polynomial length (the size of the public parameters is a fixed polynomial in the security parameter and a depth bound, with which one can generate signatures for attributes of arbitrary length). Our scheme does not rely on NIZKs, and we prove that our scheme is semi-adaptively unforgeable in the standard model; that is, the adversary can announce the challenge attribute after seeing the public parameters but before launching any query. Unlike our scheme, previous approaches either construct selectively unforgeable ABS schemes in the standard model that only support attributes of a-priori bounded polynomial length, or construct adaptively unforgeable ABS schemes that support attributes of unbounded polynomial length but relying on NIZKs. We adapt an existing technique developed by Brakerski and Vaikuntanathan for constructing lattice-based semi-adaptively secure (key-policy) attribute-based encryption (ABE) with unbounded attribute length. In particular, we use the adapted technique to generate an unbounded number of matrices out of a-priori bounded public matrices in the construction and program the challenge attribute into the public matrices in our semi-adaptive security proof. Moreover, to achieve adaptive signature query in our semi-adaptive security proof, we employ the traditional partitioning technique developed in identity-based systems to encode the message to be signed. Re-using and adapting lattice-based ABE technique and partitioning technique for lattice-based ABS should not be surprising since the three settings share many features, especially their security proof ideas.