Accumulator for monotone formulas and its application to anonymous credential system

Shahidatul Sadiah, Toru Nakanishi, Nasima Begum, Nobuo Funabiki

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


An anonymous credential system allows a user to convince a service provider anonymously that he/she owns certified attributes. Previously, a system to prove AND and OR relations simultaneously by CNF formulas was proposed. To achieve a constant-size proof of the formula, this system adopts an accumulator that compresses multiple attributes into a single value. However, this system has a problem: the proof generation requires a large amount of computational time in the case of lots of OR literals in the formula. Therefore, we convert the attribute relation from the CNF formula to a monotone formula to decrease the number of OR literals. The monotone formula is a logic formula that contains any combination of AND and OR relations. In this paper, we propose an extended accumulator to prove the monotone formula, and apply it to the anonymous credential system. Our approach to prove the monotone formula is that the tag assignment in the accumulator is extended to be adapted to the tree expressing the monotone formula. Using this type of formula, the number of public parameters multiplied in the accumulator is decreased, which greatly impacts the reduction of authentication time.

Original languageEnglish
Pages (from-to)949-961
Number of pages13
JournalJournal of Information Processing
Publication statusPublished - Dec 2017


  • Accumulator
  • Anonymity
  • Anonymous credentials
  • CNF formulas
  • Monotone formulas

ASJC Scopus subject areas

  • Computer Science(all)


Dive into the research topics of 'Accumulator for monotone formulas and its application to anonymous credential system'. Together they form a unique fingerprint.

Cite this