A Constant-Size Signature Scheme with a Tighter Reduction from the CDH Assumption

Kaisei KAJITA  Kazuto OGAWA  Eiichiro FUJISAKI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E103-A    No.1    pp.141-149
Publication Date: 2020/01/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.2019CIP0015
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
digital signature,  CDH assumption,  trapdoor commitment,  tight security reduction,  

Full Text: FreePDF(1MB)

We present a constant-size signature scheme under the CDH assumption. It has a tighter security reduction than any other constant-size signature scheme with a security reduction to solving some intractable search problems. Hofheinz, Jager, and Knapp (PKC 2012) presented a constant-size signature scheme under the CDH assumption with a reduction loss of O(q), where q is the number of signing queries. They also proved that the reduction loss of O(q) is optimal in a black-box security proof. To the best of our knowledge, no constant-size signature scheme has been proposed with a tighter reduction (to the hardness of a search problem) than that proposed by Hofheinz et al., even if it is not re-randomizable. We remark that our scheme is not re-randomizable. We achieve the reduction loss of O(q/d), where d is the number of group elements in a public key.