Signatures from Trapdoor Commitments with Strong Openings

Goichiro HANAOKA

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E100-A    No.9    pp.1924-1931
Publication Date: 2017/09/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E100.A.1924
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
signatures,  generic construction,  trapdoor commitments,  

Full Text: PDF(558.7KB)>>
Buy this Article

In this paper, we propose a new generic construction of signatures from trapdoor commitments with strong openings in the random oracle model. Our construction is very efficient in the sense that signatures consist of just a single decommitment of the underlying commitment scheme, and verification corresponds to verifying this decommitment against a commitment derived via a hash function. Furthermore, assuming the commitment scheme provides sufficiently strong statistical hiding and trapdoor opening properties, the reduction of the security of the signature scheme to the binding property of the commitment scheme is tight. To instantiate our construction, we propose two new commitment schemes with strong openings. Both of these are statistically hiding, and have binding properties based on a Diffie-Hellman inversion problem and factoring, respectively. The signature schemes obtained from these are very efficient; the first matches the performance of BLS signatures, which currently provides the shortest signatures, and the second provides signatures of similar length to the shortest version of Rabin-Williams signatures while still being tightly related to factoring.