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 propose the first lattice-based ABS signature scheme for expressive policies. More precisely, the scheme that we propose doesn't follow the traditional approach to build ABS schemes for expressive policies, i.e. using span programs or secret sharing schemes as for classical schemes. In fact, our approach is simpler and does not require such complex subroutines. We first construct a new (t,B)-threshold ABS scheme that allows to anonymously generate signatures, only 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 (And,Or)-policies. For this, we construct a new credential aggregation system that is built on top of a modified variant of Boyen's signature scheme, which could be of independent interest. Our ABS scheme for expressive policies yields signature sizes that are linear in the number of attributes similar to state-of-the-art classical ABS schemes.