A multisignature (MS) scheme enables a group of signers to produce a compact signature on a common message. In analyzing security of MS schemes, a key registration protocol with proof-of-possession (POP) is considered to prevent rogue key attacks. In this paper, we refine the POP-based security model by formalizing a new strengthened POP model and showing relations between the previous POP models and the new one. We next suggest a MS scheme that achieves: (1) non-interactive signing process, (2) O(1) pairing computations in verification, (3) tight security reduction under the co-CDH assumption, and (4) security under the new strengthened POP model. Compared to the tightly-secure BNN-MS scheme, the verification in ours can be at least 7 times faster at the 80-bit security level and 10 times faster at the 128-bit security level. To achieve our goal, we introduce a novel and simple POP generation method that can be viewed as a one-time signature without random oracles. Our POP technique can also be applied to the LOSSW-MS scheme (without random oracles), giving the security in the strengthened POP model.
Jong Hwan PARK
Sangmyung University
Young-Ho PARK
Sejong Cyber University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copy
Jong Hwan PARK, Young-Ho PARK, "A Tightly-Secure Multisignature Scheme with Improved Verification" in IEICE TRANSACTIONS on Fundamentals,
vol. E99-A, no. 2, pp. 579-589, February 2016, doi: 10.1587/transfun.E99.A.579.
Abstract: A multisignature (MS) scheme enables a group of signers to produce a compact signature on a common message. In analyzing security of MS schemes, a key registration protocol with proof-of-possession (POP) is considered to prevent rogue key attacks. In this paper, we refine the POP-based security model by formalizing a new strengthened POP model and showing relations between the previous POP models and the new one. We next suggest a MS scheme that achieves: (1) non-interactive signing process, (2) O(1) pairing computations in verification, (3) tight security reduction under the co-CDH assumption, and (4) security under the new strengthened POP model. Compared to the tightly-secure BNN-MS scheme, the verification in ours can be at least 7 times faster at the 80-bit security level and 10 times faster at the 128-bit security level. To achieve our goal, we introduce a novel and simple POP generation method that can be viewed as a one-time signature without random oracles. Our POP technique can also be applied to the LOSSW-MS scheme (without random oracles), giving the security in the strengthened POP model.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E99.A.579/_p
Copy
@ARTICLE{e99-a_2_579,
author={Jong Hwan PARK, Young-Ho PARK, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Tightly-Secure Multisignature Scheme with Improved Verification},
year={2016},
volume={E99-A},
number={2},
pages={579-589},
abstract={A multisignature (MS) scheme enables a group of signers to produce a compact signature on a common message. In analyzing security of MS schemes, a key registration protocol with proof-of-possession (POP) is considered to prevent rogue key attacks. In this paper, we refine the POP-based security model by formalizing a new strengthened POP model and showing relations between the previous POP models and the new one. We next suggest a MS scheme that achieves: (1) non-interactive signing process, (2) O(1) pairing computations in verification, (3) tight security reduction under the co-CDH assumption, and (4) security under the new strengthened POP model. Compared to the tightly-secure BNN-MS scheme, the verification in ours can be at least 7 times faster at the 80-bit security level and 10 times faster at the 128-bit security level. To achieve our goal, we introduce a novel and simple POP generation method that can be viewed as a one-time signature without random oracles. Our POP technique can also be applied to the LOSSW-MS scheme (without random oracles), giving the security in the strengthened POP model.},
keywords={},
doi={10.1587/transfun.E99.A.579},
ISSN={1745-1337},
month={February},}
Copy
TY - JOUR
TI - A Tightly-Secure Multisignature Scheme with Improved Verification
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 579
EP - 589
AU - Jong Hwan PARK
AU - Young-Ho PARK
PY - 2016
DO - 10.1587/transfun.E99.A.579
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E99-A
IS - 2
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - February 2016
AB - A multisignature (MS) scheme enables a group of signers to produce a compact signature on a common message. In analyzing security of MS schemes, a key registration protocol with proof-of-possession (POP) is considered to prevent rogue key attacks. In this paper, we refine the POP-based security model by formalizing a new strengthened POP model and showing relations between the previous POP models and the new one. We next suggest a MS scheme that achieves: (1) non-interactive signing process, (2) O(1) pairing computations in verification, (3) tight security reduction under the co-CDH assumption, and (4) security under the new strengthened POP model. Compared to the tightly-secure BNN-MS scheme, the verification in ours can be at least 7 times faster at the 80-bit security level and 10 times faster at the 128-bit security level. To achieve our goal, we introduce a novel and simple POP generation method that can be viewed as a one-time signature without random oracles. Our POP technique can also be applied to the LOSSW-MS scheme (without random oracles), giving the security in the strengthened POP model.
ER -