nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Synchronized Aggregate Signatures from the RSA Assumption

verfasst von : Susan Hohenberger, Brent Waters

Erschienen in: Advances in Cryptology – EUROCRYPT 2018

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

In this work we construct efficient aggregate signatures from the RSA assumption in the synchronized setting. In this setting, the signing algorithm takes as input a (time) period t as well the secret key and message. A signer should sign at most once for each t. A set of signatures can be aggregated so long as they were all created for the same period t. Synchronized aggregate signatures are useful in systems where there is a natural reporting period such as log and sensor data, or for signatures embedded in a blockchain protocol.

We design a synchronized aggregate signature scheme that works for a bounded number of periods T that is given as a parameter to a global system setup. The big technical question is whether we can create solutions that will perform well with the large T values that we might use in practice. For instance, if one wanted signing keys to last up to ten years and be able to issue signatures every second, then we would need to support a period bound of upwards of \(2^{28}\).

We build our solution in stages where we start with an initial solution that establishes feasibility, but has an impractically large signing time where the number of exponentiations and prime searches grows linearly with T. We prove this scheme secure in the standard model under the RSA assumption with respect to honestly-generated keys. We then provide a tradeoff method where one can tradeoff the time to create signatures with the space required to store private keys. One point in the tradeoff is where each scales with \(\sqrt{T}\).

Finally, we reach our main innovation which is a scheme where both the signing time and storage scale with \(\lg {T}\) which allows for us to keep both computation and storage costs modest even for large values of T. Conveniently, our final scheme uses the same verification algorithm, and has the same distribution of public keys and signatures as the first scheme. Thus we are able to recycle the existing security proof for the new scheme.

We also extend our results to the identity-based setting in the random oracle model, which can further reduce the overall cryptographic overhead. We conclude with a detailed evaluation of the signing time and storage requirements for various settings of the system parameters.

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel Collision Resistant Hashing for Paranoids: Dealing with Multiple Collisions

Nächstes Kapitel More Efficient (Almost) Tightly Secure Structure-Preserving Signatures

Nur mit Berechtigung zugänglich

In this work, as in the case of [1], if the signers’ clocks become out of sync with each other, this will lead to inefficiencies in the system, as it will not be possible to aggregate some signatures, but this will not open up security issues. As in [1, 19], there is a security issue if a tag or period value is reused by the signer, so an adversary’s ability to move a user’s clock backward could lead to forgeries for that signer.

For any adversary \(\mathcal {A}\) that runs in time polynomial in \(\lambda \) will be restricted (by its own running time) to giving T values out that are polynomial in \(\lambda \).

As observed by [1], one can relax this unforgeability condition to allow the forgery message, \(M_{z^*}'\), to have been previously queried to the signing oracle provided that it was not done during the same period used in the forgery. This “stronger” notion can be achieved by any scheme satisfying the above unforgeability definition by having the signer incorporate the period into each message.

In practice, one might use a collision-resistant hash function to map arbitrarily long messages into \(L=256\) bits and then set \(\ell =32\) and \(k=8\). We discuss the efficiency implications of these choices in Sect. 8.

We expect this default case to be exercised only with negligible probability, but define it so that the function \(H_K(t)\) is guaranteed to terminate in a bounded amount of time.

Our scheme has the property that any \(\sigma _{agg}\) that verifies on period t for \( pk _1,\dots , pk _z\) and \(M_1,\dots ,M_z\) also verifies on any permutation applied to both sequences.

We expect this to be the normal mode of operation in a synchronized scheme, however, the previous schemes have the ability to sign for periods in an arbitrary order.

In a particular \(S_i\) there might be zero, one or two tuples. If there are two, the one with the larger \(\mathtt {open}\) value is ignored. Ties will not occur, as we will see from the case analysis in Sect. 6.2.

We remark that the parameters given for this evaluation do not have a total correspondence to the scheme description. For example, using 80-bit e values will technically require a variant of the RSA assumption with smaller exponents. And we do not attempt to set the modulus size to match the security loss of our reduction. (It is unknown whether this loss can actually be utilized by an attacker or not.) Our focus here is to give the reader a sense of the relative performance of the scheme variants for parameters that might be used in practice.

Ahn, J.H., Green, M., Hohenberger, S.: Synchronized aggregate signatures: new definitions, constructions and applications. In: ACM Conference on Computer and Communications Security, pp. 473–484 (2010)

Anonymous. Increasing anonymity in bitcoin (2013). https://bitcointalk.org/index.php?topic=1377298.0

Bagherzandi, A., Jarecki, S.: Identity-based aggregate and multi-signature schemes based on RSA. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 480–498. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13013-7_28CrossRef

El Bansarkhani, R., Mohamed, M.S.E., Petzoldt, A.: MQSAS - a multivariate sequential aggregate signature scheme. In: Bishop, M., Nascimento, A.C.A. (eds.) ISC 2016. LNCS, vol. 9866, pp. 426–439. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-45871-7_25CrossRef

Barak, B., Canetti, R., Nielsen, J.B., Pass, R.: Universally composable protocols with relaxed set-up assumptions. In: Symposium on Foundations of Computer Science, pp. 186–195. IEEE Computer Society (2004)

Barić, N., Pfitzmann, B.: Collision-free accumulators and fail-stop signature schemes without trees. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 480–494. Springer, Heidelberg (1997). https://doi.org/10.1007/3-540-69053-0_33CrossRef

Bellare, M., Namprempre, C., Neven, G.: Unrestricted aggregate signatures. In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 411–422. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-73420-8_37CrossRef

Bellare, M., Neven, G.: Identity-based multi-signatures from RSA. In: Abe, M. (ed.) CT-RSA 2007. LNCS, vol. 4377, pp. 145–162. Springer, Heidelberg (2006). https://doi.org/10.1007/11967668_10CrossRef

Benaloh, J., de Mare, M.: One-way accumulators: a decentralized alternative to digital signatures. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 274–285. Springer, Heidelberg (1994). https://doi.org/10.1007/3-540-48285-7_24CrossRef

10.

Boldyreva, A.: Threshold signatures, multisignatures and blind signatures based on the Gap-Diffie-Hellman-Group signature scheme. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 31–46. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-36288-6_3CrossRef

11.

Boldyreva, A., Gentry, C., O’Neill, A., Yum, D.H.: Ordered multisignatures and identity-based sequential aggregate signatures, with applications to secure routing. In: ACM Conference on Computer and Communications Security (CCS), pp. 276–285 (2007), http://www.cc.gatech.edu/~amoneill/bgoy.html

12.

Boneh, D., Franklin, M.K.: Efficient generation of shared RSA keys. J. ACM 48(4), 702–722 (2001)MathSciNetCrossRefMATH

13.

Boneh, D., Gentry, C., Lynn, B., Shacham, H.: Aggregate and verifiably encrypted signatures from bilinear maps. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 416–432. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-39200-9_26CrossRef

14.

Boneh, D., Gentry, C., Lynn, B., Shacham, H.: A survey of two signature aggregation techniques. RSA Cryptobytes 6(2), 1–9 (2003)

15.

Brogle, K., Goldberg, S., Reyzin, L.: Sequential aggregate signatures with lazy verification from trapdoor permutations. Inf. Comput. 239, 356–376 (2014)MathSciNetCrossRefMATH

16.

Cramer, R., Shoup, V.: Signature schemes based on the strong RSA assumption. ACM Trans. Inf. Syst. Secur. 3(3), 161–185 (2000)CrossRef

17.

Fischlin, M., Lehmann, A., Schröder, D.: History-free sequential aggregate signatures. In: Visconti, I., De Prisco, R. (eds.) SCN 2012. LNCS, vol. 7485, pp. 113–130. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32928-9_7CrossRef

18.

Freire, E.S.V., Hofheinz, D., Paterson, K.G., Striecks, C.: Programmable hash functions in the multilinear setting. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 513–530. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40041-4_28CrossRef

19.

Gentry, C., Ramzan, Z.: Identity-based aggregate signatures. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T. (eds.) PKC 2006. LNCS, vol. 3958, pp. 257–273. Springer, Heidelberg (2006). https://doi.org/10.1007/11745853_17CrossRef

20.

Guo, X., Wang, Z.: An efficient synchronized aggregate signature scheme from standard RSA assumption. Int. J. Future Gener. Commun. Netw. 7(3), 229–240 (2014)CrossRef

21.

Hofheinz, D., Jager, T., Kiltz, E.: Short signatures from weaker assumptions. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 647–666. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25385-0_35CrossRef

22.

Hohenberger, S., Koppula, V., Waters, B.: Universal signature aggregators. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 3–34. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46803-6_1

23.

Hohenberger, S., Sahai, A., Waters, B.: Full domain hash from (leveled) multilinear maps and identity-based aggregate signatures. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 494–512. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40041-4_27CrossRef

24.

Hohenberger, S., Waters, B.: Short and stateless signatures from the RSA assumption. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 654–670. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03356-8_38CrossRef

25.

Hohenberger, S., Waters, B.: Synchronized aggregate signatures from the RSA assumption. In: Eurocrypt (This Issue) (2018). The full version appears, https://eprint.iacr.org/2018/082

26.

Itkis, G., Reyzin, L.: Forward-secure signatures with optimal signing and verifying. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 332–354. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44647-8_20CrossRef

27.

Lee, K., Lee, D.H., Yung, M.: Sequential aggregate signatures made shorter. In: Jacobson, M., Locasto, M., Mohassel, P., Safavi-Naini, R. (eds.) ACNS 2013. LNCS, vol. 7954, pp. 202–217. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38980-1_13CrossRef

28.

Lee, K., Lee, D.H., Yung, M.: Sequential aggregate signatures with short public keys: design, analysis and implementation studies. In: Kurosawa, K., Hanaoka, G. (eds.) PKC 2013. LNCS, vol. 7778, pp. 423–442. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36362-7_26CrossRef

29.

Lu, S., Ostrovsky, R., Sahai, A., Shacham, H., Waters, B.: Sequential aggregate signatures and multisignatures without random oracles. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 465–485. Springer, Heidelberg (2006). https://doi.org/10.1007/11761679_28. http://cseweb.ucsd.edu/~hovav/dist/agg-sig.pdfCrossRef

30.

Lysyanskaya, A., Micali, S., Reyzin, L., Shacham, H.: Sequential aggregate signatures from trapdoor permutations. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 74–90. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24676-3_5CrossRef

31.

Ma, D., Tsudik, G.: Extended abstract: forward-secure sequential aggregate authentication. In: IEEE Symposium on Security and Privacy, pp. 86–91 (2007)

32.

Miller, G.L.: Riemann’s hypothesis and tests for primality. J. Comput. Syst. Sci. 13, 300–317 (1976)MathSciNetCrossRefMATH

33.

Neven, G.: Efficient sequential aggregate signed data. In: Smart, N. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 52–69. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78967-3_4CrossRef

34.

Rabin, M.O.: Probabilistic algorithm for testing primality. J. Number Theory 12, 128–138 (1980)MathSciNetCrossRefMATH

35.

Rivest, R.L., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Comm. ACM 21(2), 120–126 (1978)MathSciNetCrossRefMATH

36.

Rückert, M., Schröder, D.: Aggregate and verifiably encrypted signatures from multilinear maps without random oracles. In: Park, J.H., Chen, H.-H., Atiquzzaman, M., Lee, C., Kim, T., Yeo, S.-S. (eds.) ISA 2009. LNCS, vol. 5576, pp. 750–759. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-02617-1_76CrossRef

37.

Sharmila Deva Selvi, S., Sree Vivek, S., Pandu Rangan, C.: Deterministic identity based signature scheme and its application for aggregate signatures. In: Susilo, W., Mu, Y., Seberry, J. (eds.) ACISP 2012. LNCS, vol. 7372, pp. 280–293. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-31448-3_21CrossRef

38.

Shoup, V.: NTL: A Library for doing Number Theory, v10.5.0 (2017). http://www.shoup.net/ntl/

Titel: Synchronized Aggregate Signatures from the RSA Assumption
verfasst von: Susan Hohenberger
Brent Waters
Verlag: Springer International Publishing
Buch: Advances in Cryptology – EUROCRYPT 2018
Print ISBN: 978-3-319-78374-1

Electronic ISBN: 978-3-319-78375-8

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-78375-8_7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"