For Full-Text 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.
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
Publication Date: 2020/01/01
Online ISSN: 1745-1337
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.