The search functionality is under construction.

The search functionality is under construction.

Most aggregate signature schemes are relying on pairings, but high computational and storage costs of pairings limit the feasibility of those schemes in practice. Zhao proposed the first pairing-free aggregate signature scheme (AsiaCCS 2019). However, the security of Zhao's scheme is based on the hardness of a newly introduced non-standard computational problem. The recent impossibility results of Drijvers et al. (IEEE S&P 2019) on two-round pairing-free multi-signature schemes whose security based on the standard discrete logarithm (DL) problem have strengthened the view that constructing a pairing-free aggregate signature scheme which is proven secure based on standard problems such as DL problem is indeed a challenging open problem. In this paper, we offer a novel solution to this open problem. We introduce a new paradigm of aggregate signatures, i.e., aggregate signatures with an additional *pre-communication* stage. In the pre-communication stage, each signer interacts with the aggregator to agree on a specific random value *before deciding messages to be signed*. We also discover that the impossibility results of Drijvers et al. take effect if the adversary can decide the whole randomness part of any individual signature. Based on the new paradigm and our discovery of the applicability of the impossibility result, we propose a pairing-free aggregate signature scheme such that any individual signature includes a random nonce which can be freely generated by the signer. We prove the security of our scheme based on the hardness of the *standard DL problem*. As a trade-off, in contrast to the plain public-key model, which Zhao's scheme uses, we employ a more restricted key setup model, i.e., the knowledge of secret-key model.

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E104-A No.9 pp.1188-1205

- Publication Date
- 2021/09/01

- Publicized
- 2021/06/10

- Online ISSN
- 1745-1337

- DOI
- 10.1587/transfun.2020DMP0023

- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

- Category
- Cryptography and Information Security

Kaoru TAKEMURE

the University of Electro-Communications,the National Institute of Advanced Industrial Science and Technology

Yusuke SAKAI

the National Institute of Advanced Industrial Science and Technology

Bagus SANTOSO

the University of Electro-Communications

Goichiro HANAOKA

the National Institute of Advanced Industrial Science and Technology

Kazuo OHTA

the University of Electro-Communications,the National Institute of Advanced Industrial Science and Technology

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

Kaoru TAKEMURE, Yusuke SAKAI, Bagus SANTOSO, Goichiro HANAOKA, Kazuo OHTA, "Achieving Pairing-Free Aggregate Signatures using Pre-Communication between Signers" in IEICE TRANSACTIONS on Fundamentals,
vol. E104-A, no. 9, pp. 1188-1205, September 2021, doi: 10.1587/transfun.2020DMP0023.

Abstract: Most aggregate signature schemes are relying on pairings, but high computational and storage costs of pairings limit the feasibility of those schemes in practice. Zhao proposed the first pairing-free aggregate signature scheme (AsiaCCS 2019). However, the security of Zhao's scheme is based on the hardness of a newly introduced non-standard computational problem. The recent impossibility results of Drijvers et al. (IEEE S&P 2019) on two-round pairing-free multi-signature schemes whose security based on the standard discrete logarithm (DL) problem have strengthened the view that constructing a pairing-free aggregate signature scheme which is proven secure based on standard problems such as DL problem is indeed a challenging open problem. In this paper, we offer a novel solution to this open problem. We introduce a new paradigm of aggregate signatures, i.e., aggregate signatures with an additional *pre-communication* stage. In the pre-communication stage, each signer interacts with the aggregator to agree on a specific random value *before deciding messages to be signed*. We also discover that the impossibility results of Drijvers et al. take effect if the adversary can decide the whole randomness part of any individual signature. Based on the new paradigm and our discovery of the applicability of the impossibility result, we propose a pairing-free aggregate signature scheme such that any individual signature includes a random nonce which can be freely generated by the signer. We prove the security of our scheme based on the hardness of the *standard DL problem*. As a trade-off, in contrast to the plain public-key model, which Zhao's scheme uses, we employ a more restricted key setup model, i.e., the knowledge of secret-key model.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2020DMP0023/_p

Copy

@ARTICLE{e104-a_9_1188,

author={Kaoru TAKEMURE, Yusuke SAKAI, Bagus SANTOSO, Goichiro HANAOKA, Kazuo OHTA, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={Achieving Pairing-Free Aggregate Signatures using Pre-Communication between Signers},

year={2021},

volume={E104-A},

number={9},

pages={1188-1205},

abstract={Most aggregate signature schemes are relying on pairings, but high computational and storage costs of pairings limit the feasibility of those schemes in practice. Zhao proposed the first pairing-free aggregate signature scheme (AsiaCCS 2019). However, the security of Zhao's scheme is based on the hardness of a newly introduced non-standard computational problem. The recent impossibility results of Drijvers et al. (IEEE S&P 2019) on two-round pairing-free multi-signature schemes whose security based on the standard discrete logarithm (DL) problem have strengthened the view that constructing a pairing-free aggregate signature scheme which is proven secure based on standard problems such as DL problem is indeed a challenging open problem. In this paper, we offer a novel solution to this open problem. We introduce a new paradigm of aggregate signatures, i.e., aggregate signatures with an additional *pre-communication* stage. In the pre-communication stage, each signer interacts with the aggregator to agree on a specific random value *before deciding messages to be signed*. We also discover that the impossibility results of Drijvers et al. take effect if the adversary can decide the whole randomness part of any individual signature. Based on the new paradigm and our discovery of the applicability of the impossibility result, we propose a pairing-free aggregate signature scheme such that any individual signature includes a random nonce which can be freely generated by the signer. We prove the security of our scheme based on the hardness of the *standard DL problem*. As a trade-off, in contrast to the plain public-key model, which Zhao's scheme uses, we employ a more restricted key setup model, i.e., the knowledge of secret-key model.},

keywords={},

doi={10.1587/transfun.2020DMP0023},

ISSN={1745-1337},

month={September},}

Copy

TY - JOUR

TI - Achieving Pairing-Free Aggregate Signatures using Pre-Communication between Signers

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 1188

EP - 1205

AU - Kaoru TAKEMURE

AU - Yusuke SAKAI

AU - Bagus SANTOSO

AU - Goichiro HANAOKA

AU - Kazuo OHTA

PY - 2021

DO - 10.1587/transfun.2020DMP0023

JO - IEICE TRANSACTIONS on Fundamentals

SN - 1745-1337

VL - E104-A

IS - 9

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - September 2021

AB - Most aggregate signature schemes are relying on pairings, but high computational and storage costs of pairings limit the feasibility of those schemes in practice. Zhao proposed the first pairing-free aggregate signature scheme (AsiaCCS 2019). However, the security of Zhao's scheme is based on the hardness of a newly introduced non-standard computational problem. The recent impossibility results of Drijvers et al. (IEEE S&P 2019) on two-round pairing-free multi-signature schemes whose security based on the standard discrete logarithm (DL) problem have strengthened the view that constructing a pairing-free aggregate signature scheme which is proven secure based on standard problems such as DL problem is indeed a challenging open problem. In this paper, we offer a novel solution to this open problem. We introduce a new paradigm of aggregate signatures, i.e., aggregate signatures with an additional *pre-communication* stage. In the pre-communication stage, each signer interacts with the aggregator to agree on a specific random value *before deciding messages to be signed*. We also discover that the impossibility results of Drijvers et al. take effect if the adversary can decide the whole randomness part of any individual signature. Based on the new paradigm and our discovery of the applicability of the impossibility result, we propose a pairing-free aggregate signature scheme such that any individual signature includes a random nonce which can be freely generated by the signer. We prove the security of our scheme based on the hardness of the *standard DL problem*. As a trade-off, in contrast to the plain public-key model, which Zhao's scheme uses, we employ a more restricted key setup model, i.e., the knowledge of secret-key model.

ER -