Paper 2018/842

Attribute-Based Signatures for Unbounded Languages from Standard Assumptions

Yusuke Sakai, Shuichi Katsumata, Nuttapong Attrapadung, and Goichiro Hanaoka


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 Turin 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.

Available format(s)
Publication info
Published by the IACR in ASIACRYPT 2018
attribute-based signaturesGroth-Sahai proofsstructure-preserving signaturesTuring machinesnondeterministic finite automata
Contact author(s)
yusuke sakai @ aist go jp
shuichi katsumata000 @ gmail com
n attrapadung @ aist go jp
hanaoka-goichiro @ aist go jp
2018-09-20: revised
2018-09-14: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yusuke Sakai and Shuichi Katsumata and Nuttapong Attrapadung and Goichiro Hanaoka},
      title = {Attribute-Based Signatures for Unbounded Languages from Standard Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2018/842},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.