Efficient Proofs for Monotone Formulas on Attributes Excluding Restriction in Anonymous Credential System

摘要

An anonymous credential system on attributes allows a user to convince a service provider anonymously that he/she owns the certified attributes. Previously, we proposed an anonymous credential scheme to prove the satisfaction of a monotone formula when only one attribute is true for any OR relation. A monotone formula represents any combination of AND relations and OR relations. However, this system has a drawback that it cannot verify a user's certificate such that two or more attributes for an OR relation are true. In this paper, we propose an extended scheme for proofs of arbitrary monotone formula by adopting Linear Homonorphic (LH) signature scheme to generate a certificate that contains the minimum attribute set as required in the verification.