Privacy-preserving and efficient attributes proof based on selective aggregate CL-signature scheme

We propose efficient attributes proof protocols in an anonymous and unlinkable fashion. The core idea is issuing anonymous credentials for each single attribute and proving relations over attributes by selectively aggregating individual anonymous credentials. A selective aggregate Camenisch-Lysyanskaya (CL)-signature scheme is presented to construct anonymous credentials. It is existentially unforgeable against adaptively chosen-message attack under CL-signature scheme on the Lysyanskaya-Rivest-Sahai-Wolf assumption. It has constant complexity in verification of multiple signatures. Users can select which attributes and the corresponding individual anonymous credentials are involved in the proof. They can prove the possession of attributes over logic relations including AND and OR, and the possession of a single attribute over comparison relations including inequality to a given value and belonging to a given interval. The efficiency analysis shows that the resulting protocols have advantages in computation cost; the AND relation proof and comparison relation proofs have constant complexity w.r.t. the number of attributes, and the OR relation proof has linear complexity only w.r.t. the number of attributes as required.