The above requirements rule out all existing solutions for short signatures. In this paper, as a feasibility result, we provide the first instantiation of all variants of adjustable signatures based on indistinguishability obfuscation. Our starting point is the state-of-the-art construction by Ramchen and Waters [ACM CCS 2014]. We observe that their scheme fails to meet our requirements for an adjustable signature scheme, and enhance it to obtain adjustable signatures with {\em shorter} signatures, {\em faster} signing and {\em strong} unforgeability. We also employ new proof techniques in order toobtain the above-mentioned notions of security.
For the simpler case where adversarial effort does not grow with the number of forgeries, we also provide a concrete construction based on the BLS signature scheme, by instantiating it using smaller group sizes that yield shorter signature lengths while providing reasonable security. We implement this scheme for various signature sizes an report on its efficiency.
Category / Keywords: public-key cryptography / Digital signatures, indistinguishability obfuscation, bilinear maps Date: received 1 Jun 2016, last revised 10 Oct 2016 Contact author: xfan at cs cornell edu Available format(s): PDF | BibTeX Citation Version: 20161010:151518 (All versions of this report) Short URL: ia.cr/2016/549