Succinct Attribute-Based Signatures for Bounded-Size Circuits by Combining Algebraic and Arithmetic Proofs
Succinct Attribute-Based Signatures for Bounded-Size Circuits by Combining Algebraic and Arithmetic Proofs
复制标题
结合代数和算术证明的有界尺寸电路的简洁的基于属性的签名
DOI：
10.1007/978-3-031-14791-3_31
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Sakai Yusuke
中科院分区：
文献类型：
--
作者：
Shweta Agrawal;Fuyuki Kitagawa;Anuja Modi;Ryo Nishimaki;Shota Yamada;Takashi Yamakawa;Sakai Yusuke
基于属性的签名允许细粒度的基于属性的认证，同时尽可能地保持签名者的隐私。虽然有基于属性的签名的构造允许任意电路或图灵机作为认证策略，但它们实际上都不是非常有效的。一些方案具有长签名或长用户密钥，其随着策略或属性的大小而增长。一些方案依赖于一个巨大的卡普约简，它将公钥和私钥操作转化为一个算术电路。我们提出了一个基于属性的签名方案，用于有界大小的任意算术电路，具有恒定大小的签名和用户密钥，而不依赖于这样的卡普约简。该方案基于双线性群，在一般双线性群模型下被证明是安全的。为了实现这一目标，我们开发了一个新的扩展SNARKs（简洁的非交互式知识参数）。我们将这种扩展形式化为受约束的SNARKs，它可以被看作是提交-证明SNARKs在语法和技术上的简化。在一个约束SNARK中，通过声明一个对见证人进行约束编码的succintconstraint字符串，可以强制证明者使用满足某个约束的见证人。如果证明在某个约束字符串下是有效的，则确保证明背后的证明满足约束字符串背后的约束。通过简洁，我们的意思是约束字符串具有独立于约束的简单描述的长度的恒定长度，并且值得注意的是，验证者不需要知道用于验证证明的约束的（可能很长的）简单描述。我们在一般的双线性群模型中构造了一个有约束的SNARK。
Attribute-based signatures allow fine-grained attribute-based authentication and at the same time keep a signer’s privacy as much as possible. While there are constructions of attribute-based signatures allowing arbitrary circuits or Turing machines as an authentication policy, none of them is practically very efficient. Some schemes have long signatures or long user secret keys which grow as the sizes of a policy or attributes grow. Some scheme relies on a vast Karp reduction which transforms public-key and secret-key operations into an arithmetic circuit. We propose an attribute-based signature scheme for bounded-size arbitrary arithmetic circuits with constant-size signatures and user secret keys without relying on such a Karp reduction. The scheme is based on bilinear groups and is proven secure in the generic bilinear group model. To achieve this we develop a new extension of SNARKs (succinct non-interactive arguments of knowledge). We formalize this extension asconstrained SNARKs, which can be seen as a simplification of commit-and-prove SNARKs both in syntax and technique. In a constrained SNARK, one can force a prover to use a witness satisfying some constraint by announcing asuccinctconstraint string which encodes a constraint on a witness. If a proof is valid under some constraint string, it is ensured that the witness behind the proof satisfies the constraint that is behind the constraint string. By succinct, we mean that a constraint string has a constant length independent of the length of the plain description of the constraint, and notably a verifier need not know the (potentially long) plain description of the constraint for verifying a proof. We construct a constrained SNARK in the generic bilinear group model.