
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Efficient AttributeBased Signatures for Unbounded Arithmetic Branching Programs
Pratish DATTA Tatsuaki OKAMOTO Katsuyuki TAKASHIMA
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E104A
No.1
pp.2557 Publication Date: 2021/01/01 Online ISSN: 17451337
DOI: 10.1587/transfun.2020CIP0003 Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security) Category: Keyword: attributebased signatures, arithmetic branching programs, arithmetic span programs, concrete efficiency, unbounded multiuse of attributes, bilinear groups,
Full Text: FreePDF(1.6MB)
Summary:
This paper presents the first attributebased 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 signerprivate 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 multiuse 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 wellstudied 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 stateoftheart 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 multiuse of attributes inside ABP's, which themselves are of unbounded size and input length.


