Efficient Proofs for CNF Formulas on Attributes in Pairing-Based Anonymous Credential System

摘要

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 the relations on his/her attributes certified by the certificate. Previously, a pairing-based anonymous credential system with constant-size proofs in the number of attributes of the user has been proposed. This system supports the proofs of the inner product relations on attributes, and thus can handle any CNF (or DNF) formula on attributes. However, in this system, 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, where the proof generation needs only multiplications depending on the number of literals, and thus it is more efficient. 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.%匿名クレデンシャルシステムでは，証明書発行機開からユーザに証明書が発行され，ユーザは検証者へその証明書の保持を匿名で証明できる.それに加えて，ユーザは，証明書により保証された自身の属性における関係式も証明可能である.従来，証明サイズが属性数に依存せず固定長となる利点をもつペアリングベース方式が提案されている.この方式では，属性の内積述語を証明でき，このため任意のCNF式（もしくはDNF式）を証明可能である.しかしながら，証明生成においてCNF式に含まれるリテラルの数に依存した回数のべき乗演算が必要となる問題がある.そこで本研究では，従来システムよりも効率的に固定長サイズのCNF式証明を生成可能な方式を提案する.提案方式では,証明生成において，リテラル数に依存した乗算のみが必要であり，従来方式より効率的になっている.この方式では，アキュームレータを拡張して利用することにより効率化を実現している.拡張したアキュームレータでは，複数の属性情報が複数の集合に所属することを乗算を用いて効率的に証明可能であり，これにより効率的にCNF式を証明できる.