International Association for Cryptologic Research

International Association
for Cryptologic Research


Attribute-Based Signatures for Unbounded Languages from Standard Assumptions

Yusuke Sakai
Shuichi Katsumata
Nuttapong Attrapadung
Goichiro Hanaoka
DOI: 10.1007/978-3-030-03329-3_17
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2018
Abstract: Attribute-based signature (ABS) schemes are advanced signature schemes that simultaneously provide fine-grained authentication while protecting privacy of the signer. Previously known expressive ABS schemes support either the class of deterministic finite automata and circuits from standard assumptions or Turing machines from the existence of indistinguishability obfuscations.In this paper, we propose the first ABS scheme for a very general policy class, all deterministic Turing machines, from a standard assumption, namely, the Symmetric External Diffie-Hellman (SXDH) assumption. We also propose the first ABS scheme that allows nondeterministic finite automata (NFA) to be used as policies. Although the expressiveness of NFAs are more restricted than Turing machines, this is the first scheme that supports nondeterministic computations as policies.Our main idea lies in abstracting ABS constructions and presenting the concept of history of computations; this allows a signer to prove possession of a policy that accepts the string associated to a message in zero-knowledge while also hiding the policy, regardless of the computational model being used. With this abstraction in hand, we are able to construct ABS for Turing machines and NFAs using a surprisingly weak NIZK proof system. Essentially we only require a NIZK proof system for proving that a (normal) signature is valid. Such a NIZK proof system together with a base signature scheme are, in turn, possible from bilinear groups under the SXDH assumption, and hence so are our ABS schemes.
  title={Attribute-Based Signatures for Unbounded Languages from Standard Assumptions},
  booktitle={Advances in Cryptology – ASIACRYPT 2018},
  series={Lecture Notes in Computer Science},
  author={Yusuke Sakai and Shuichi Katsumata and Nuttapong Attrapadung and Goichiro Hanaoka},