Skip to main content

2020 | OriginalPaper | Buchkapitel

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

verfasst von : Kaoru Takemure, Yusuke Sakai, Bagus Santoso, Goichiro Hanaoka, Kazuo Ohta

Erschienen in: Provable and Practical Security

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

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 has 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. apply 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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Fußnoten
1
It should be noted that an aggregate signature schemes or a multi-signature do not have to have all the three stages.
 
2
The KOSK model is essential because there is a sub-exponential attack against this scheme in the plain PK model by using k-sum algorithm as in  [10]. For more detail of this attack, see the full version of this paper.
 
3
For the convenience of considering multiple users, we added the public key to the input of the hash function.
 
4
If we set \(m_1=m_2=\cdots =m_n\), then we can see it as multi-signatures.
 
5
In [5], Bellare and Neven consider the case where there are several public keys with the same values.
 
6
Here, we implicitly assumed the same restriction as we assumed in Sect. 1.3 for discussing Bellare-Neven’s approach to the difficulty (III). However, this restriction can be removed in the actual proof of this proposed scheme. For detail, see the security model in Sect. 3.1.
 
7
This restriction is essential. If this restriction is omitted, there is an attack against our proposed scheme. See Remark 1 for more detail.
 
Literatur
1.
Zurück zum Zitat Ahn, J.H., Green, M., Hohenberger, S.: Synchronized aggregate signatures: new definitions, constructions and applications. In: CCS 2010, pp. 473–484 (2010) Ahn, J.H., Green, M., Hohenberger, S.: Synchronized aggregate signatures: new definitions, constructions and applications. In: CCS 2010, pp. 473–484 (2010)
2.
Zurück zum Zitat Bagherzandi, A., Cheon, J.H., Jarecki, S.: Multisignatures secure under the discrete logarithm assumption and a generalized forking lemma. In: CCS 2008, pp. 449–458 (2008) Bagherzandi, A., Cheon, J.H., Jarecki, S.: Multisignatures secure under the discrete logarithm assumption and a generalized forking lemma. In: CCS 2008, pp. 449–458 (2008)
5.
Zurück zum Zitat Bellare, M., Neven, G.: Multi-signatures in the plain public-key model and a general forking lemma. In: CCS 2006, pp. 390–399 (2006) Bellare, M., Neven, G.: Multi-signatures in the plain public-key model and a general forking lemma. In: CCS 2006, pp. 390–399 (2006)
7.
Zurück zum Zitat Boldyreva, A., Gentry, C., O’Neill, A., Yum, D.H.: Ordered multisignatures and identity-based sequential aggregate signatures, with applications to secure routing. In: CCS 2007, pp. 276–285 (2007) Boldyreva, A., Gentry, C., O’Neill, A., Yum, D.H.: Ordered multisignatures and identity-based sequential aggregate signatures, with applications to secure routing. In: CCS 2007, pp. 276–285 (2007)
10.
Zurück zum Zitat Drijvers, M., et al.: On the security of two-round multi-signatures. In: IEEE S&P 2019, pp. 1084–1101 (2019) Drijvers, M., et al.: On the security of two-round multi-signatures. In: IEEE S&P 2019, pp. 1084–1101 (2019)
11.
Zurück zum Zitat Drijvers, M., Gorbunov, S., Neven, G., Wee, H.: Pixel: multi-signatures for consensus. In: IACR Cryptology ePrint Archive 2019, p. 514 (2019) Drijvers, M., Gorbunov, S., Neven, G., Wee, H.: Pixel: multi-signatures for consensus. In: IACR Cryptology ePrint Archive 2019, p. 514 (2019)
12.
Zurück zum Zitat Fiat, A., Shamir, A.: How to prove yourself: practical solutions to identification and signature problems. In: CRYPTO 1986, pp. 186–194 (1986) Fiat, A., Shamir, A.: How to prove yourself: practical solutions to identification and signature problems. In: CRYPTO 1986, pp. 186–194 (1986)
21.
23.
Zurück zum Zitat Ma, D., Tsudik, G.: Extended abstract: forward-secure sequential aggregate authentication. In: S&P 2007, pp. 86–91 (2007) Ma, D., Tsudik, G.: Extended abstract: forward-secure sequential aggregate authentication. In: S&P 2007, pp. 86–91 (2007)
24.
Zurück zum Zitat Maurer, U.M.: Abstract models of computation in cryptography. In: IMA 2005, pp. 1–12 (2005) Maurer, U.M.: Abstract models of computation in cryptography. In: IMA 2005, pp. 1–12 (2005)
25.
Zurück zum Zitat Micali, S., Ohta, K., Reyzin, L.: Accountable-subgroup multisignatures: extended abstract. In: CCS 2001, pp. 245–254 (2001) Micali, S., Ohta, K., Reyzin, L.: Accountable-subgroup multisignatures: extended abstract. In: CCS 2001, pp. 245–254 (2001)
28.
Zurück zum Zitat Schnorr, C.: Efficient identification and signatures for smart cards. In: CRYPTO 1989, pp. 239–252 (1989) Schnorr, C.: Efficient identification and signatures for smart cards. In: CRYPTO 1989, pp. 239–252 (1989)
29.
Zurück zum Zitat Syta, E., et al.: Keeping authorities “honest or bust” with decentralized witness cosigning. In: S&P 2016, pp. 526–545 (2016) Syta, E., et al.: Keeping authorities “honest or bust” with decentralized witness cosigning. In: S&P 2016, pp. 526–545 (2016)
31.
Zurück zum Zitat Yao, A.C., Zhao, Y.: Online/offline signatures for low-power devices. IEEE Trans. Inf. Forensics Secur. 8(2), 283–294 (2013)MathSciNetCrossRef Yao, A.C., Zhao, Y.: Online/offline signatures for low-power devices. IEEE Trans. Inf. Forensics Secur. 8(2), 283–294 (2013)MathSciNetCrossRef
32.
Zurück zum Zitat Zhao, Y.: Practical aggregate signature from general elliptic curves, and applications to blockchain. In: AsiaCCS, 2019, pp. 529–538 (2019) Zhao, Y.: Practical aggregate signature from general elliptic curves, and applications to blockchain. In: AsiaCCS, 2019, pp. 529–538 (2019)
Metadaten
Titel
Achieving Pairing-Free Aggregate Signatures using Pre-Communication between Signers
verfasst von
Kaoru Takemure
Yusuke Sakai
Bagus Santoso
Goichiro Hanaoka
Kazuo Ohta
Copyright-Jahr
2020
DOI
https://doi.org/10.1007/978-3-030-62576-4_4