Paper 2016/823

Post-Quantum Attribute-Based Signatures from Lattice Assumptions

Rachid El Bansarkhani and Ali El Kaafarani

Abstract

Attribute based signature schemes (ABS) constitute important and powerful primitives when it comes to protecting the privacy of the user's identity and signing information. More specifically, ABS schemes provide the advantage of anonymously signing a message once a given policy is satisfied. As opposed to other related privacy preserving signatures, the verifier is not able to deduce from the signature, which attributes have been used to satisfy the (public) signing policy. In this work we give new and efficient constructions of lattice-based ABS signature schemes, that are not based on the traditional approach of using span programs or secret sharing schemes as for classical schemes. In fact, our approach is less involved and does not require such complex subroutines. In particular, we first construct a new $(t,B)$-threshold ABS scheme that allows to anonymously generate signatures, if $t$ out of $p=|B|$ attributes are covered by valid credentials. Based on this scheme, we propose a lattice-based ABS scheme for expressive $(\wedge,\vee)$-policies, by use of a new credential aggregation system that is built on top of a modified variant of Boyen's signature scheme. The signature size of the so obtained ABS scheme is linear in the number of disjunctive terms rather than the number of attributes.