Cryptology ePrint Archive: Report 2018/842

Attribute-Based Signatures for Unbounded Languages from Standard Assumptions

Yusuke Sakai and Shuichi Katsumata and Nuttapong Attrapadung and Goichiro Hanaoka

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

Category / Keywords: attribute-based signatures, Groth-Sahai proofs, structure-preserving signatures, Turing machines, nondeterministic finite automata

Original Publication (in the same form): IACR-ASIACRYPT-2018

Date: received 7 Sep 2018, last revised 19 Sep 2018

Contact author: yusuke sakai at aist go jp, shuichi katsumata000@gmail com, n attrapadung@aist go jp, hanaoka-goichiro@aist go jp

Available format(s): PDF | BibTeX Citation

Version: 20180920:054524 (All versions of this report)

Short URL: ia.cr/2018/842


[ Cryptology ePrint archive ]