Cryptology ePrint Archive: Report 2019/363
Efficient Attribute-Based Signatures for Unbounded Arithmetic Branching Programs
Pratish Datta and Tatsuaki Okamoto and Katsuyuki Takashima
Abstract: This paper presents the first attribute-based signature (ABS) scheme in which the correspondence between
signers and signatures is captured in an arithmetic model of computation. Specifically, we design a fully
secure, i.e., adaptively unforgeable and perfectly signer-private ABS scheme for signing policies realizable
by arithmetic branching programs (ABP), which are a quite expressive model of arithmetic computations.
On a more positive note, the proposed scheme places no bound on the size and input length of the
supported signing policy ABP’s, and at the same time, supports the use of an input attribute for an
arbitrary number of times inside a signing policy ABP, i.e., the so called unbounded multi-use of attributes.
The size of our public parameters is constant with respect to the sizes of the signing attribute vectors
and signing policies available in the system. The construction is built in (asymmetric) bilinear groups
of prime order, and its unforgeability is derived in the standard model under (asymmetric version of)
the well-studied decisional linear (DLIN) assumption coupled with the existence of standard collision
resistant hash functions. Due to the use of the arithmetic model as opposed to the boolean one, our ABS
scheme not only excels significantly over the existing state-of-the-art constructions in terms of concrete
efficiency, but also achieves improved applicability in various practical scenarios. Our principal technical
contributions are (a) extending the techniques of Okamoto and Takashima [PKC 2011, PKC 2013], which
were originally developed in the context of boolean span programs, to the arithmetic setting; and (b)
innovating new ideas to allow unbounded multi-use of attributes inside ABP’s, which themselves are of
unbounded size and input length.
Category / Keywords: public-key cryptography / attribute-based signatures, arithmetic branching programs, arithmetic span programs, concrete efficiency, unbounded multi-use of attributes, bilinear groups
Original Publication (with major differences): PKC 2019
Date: received 3 Apr 2019
Contact author: pratish datta yg at hco ntt co jp
Available format(s): PDF | BibTeX Citation
Note: This is the full version of the paper.
Version: 20190410:002048 (All versions of this report)
Short URL: ia.cr/2019/363
[ Cryptology ePrint archive ]