Accumulator for monotone formulas and its application to anonymous credential system

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.