Efficient Attributes Proof on CNF Relation for eID System

Abstract

Electronic identity system is a user-centric identity management system which emphasizes the balance
between security and privacy during authentication and authorization. Users can selectively
disclose any combination of attributes and prove relations over them instead of being identified.
Several attributes proof protocols are proposed to prove simple and complex logic over multiple attributes.
However, the cryptographic building blocks to construct these protocols generally of large
size of public parameter and signature, and also the complexity w.r.t. the concrete number of pairing
and exponentiation operation is too large to be practical in source-limited devices. In this paper, we
focus on reducing the complexity and the signature size in attributes proof procedure. We firstly
demonstrate the application scenario, and then give an extended Boneh-Lynn-Shacham short signature
scheme to construct an efficient pairing-based credential. We also describe the protocol of
attributes proof on CNF relation, where the complexity is linear with the number of clauses instead
of the attributes embedded in the credential or specified in the security policy.