Short attribute-based signatures for arbitrary Turing machines from standard assumptions

Abstract

This paper presents the first attribute-based signature (ABS) scheme supporting signing policies representable by Turing machines (TM), based on well-studied computational assumptions. Our work supports arbitrary TMs as signing policies in the sense that the TMs can accept signing attribute strings of unbounded polynomial length and there is no limit on their running time, description size, or space complexity. Moreover, we are able to achieve input-specific running time for the signing algorithm. All other known expressive ABS schemes could at most support signing policies realizable by either arbitrary polynomial-size circuits or TMs having a pre-determined upper bound on the running time.