Efficient proofs for CNF formulas on attributes in pairing-based anonymous credential system

Nasima Begum, Toru Nakanishi, Nobuo Funabiki

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)


To enhance user privacy, anonymous credential systems allow the user to convince a verifier of the possession of a certificate issued by the issuing authority anonymously. In the systems, the user can prove relations on his/her attributes embedded into the certificate. Previously, a pairing-based anonymous credential system with constant-size proofs in the number of attributes of the user was proposed. This system supports the proofs of the inner product relations on attributes, and thus can handle the complex logical relations on attributes as the CNF and DNF formulas. However this system suffers from the computational cost: The proof generation needs exponentiations depending on the number of the literals in OR relations. In this paper, we propose a pairing-based anonymous credential system with the constant-size proofs for CNF formulas and the more efficient proof generation. In the proposed system, the proof generation needs only multiplications depending on the number of literals, and thus it is more efficient than the previously proposed system. The key of our construction is to use an extended accumulator, by which we can verify that multiple attributes are included in multiple sets, all at once. This leads to the verification of CNF formulas on attributes. Since the accumulator is mainly calculated by multiplications, we achieve the better computational costs.

Original languageEnglish
Pages (from-to)2422-2433
Number of pages12
JournalIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Issue number12
Publication statusPublished - Dec 2013


  • Anonymity
  • Anonymous credentials
  • Attributes
  • CNF formulas

ASJC Scopus subject areas

  • Signal Processing
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering
  • Applied Mathematics


Dive into the research topics of 'Efficient proofs for CNF formulas on attributes in pairing-based anonymous credential system'. Together they form a unique fingerprint.

Cite this