nach oben

Erschienen in:

2024 | OriginalPaper | Buchkapitel

Batch Signatures, Revisited

verfasst von : Carlos Aguilar-Melchor, Martin R. Albrecht, Thomas Bailleux, Nina Bindel, James Howe, Andreas Hülsing, David Joseph, Marc Manzano

Erschienen in: Topics in Cryptology – CT-RSA 2024

Verlag: Springer Nature Switzerland

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We revisit batch signatures (previously considered in a draft RFC and used in multiple recent works), where a single, potentially expensive, “inner” digital signature authenticates a Merkle tree constructed from many messages. We formalise a construction and prove its unforgeability and privacy properties.

We also show that batch signing allows us to scale slow signing algorithms, such as those recently selected for standardisation as part of NIST’s post-quantum project, to high throughput, with a mild increase in latency and demonstrate the practical efficiency of batch signing in the context of TLS. For the example of Falcon-512 in TLS, we can increase the amount of connections per second by a factor 3.2, at the cost of an increase in the signature size by 14% and the median latency by 25%; both run on the same 30 core server. For SPHINCS\(^+\)-128, throughput improves by a factor 4.6, with a negligible impact on signature size and an 11% impact on median latency.

We also discuss applications where batch signatures allow us to increase throughput and to save bandwidth. For example, again for 16 Falcon-512 signatures, once one batch signature is available, the additional bandwidth for each of the remaining is only 82 bytes.

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 Improved Meet-in-the-Middle Attacks on Nine Rounds of the AES-192 Block Cipher

Nächstes Kapitel History-Free Sequential Aggregation of Hash-and-Sign Signatures

See also the discussion of Falcon’s performance in Sect. 2.3.

Commit d5be452, dated 28 April 2023.

see https://openquantumsafe.org/applications/tls.html.

[ADWF+10]

Akdemir, K., et al.: Breakthrough AES Performance with Intel^® AES New Instructions. Whitepaper, Intel (2010)

[Ben20]

Benjamin, D.: Batch Signing for TLS. Internet-Draft draft-ietf-tls-batch-signing-00, Internet Engineering Task Force. January 2020. Work in Progress

[Ben22]

Benjamin, D.: Private communication (2022)

[BHK+19]

Bernstein, D.J., Hülsing, A., Kölbl, S., Niederhagen, R., Rijneveld, J., Schwabe, P.: The SPHINCS\(^+\) signature framework. In: Cavallaro, L., Kinder, J., Wang, X., Katz, J (eds.), ACM CCS 2019, pp. 2129–2146. ACM Press, November 2019

[BL18]

Bernstein, D.J., Lange, T.: SUPERCOP: system for unified performance evaluation related to cryptographic operations and primitives (2018). https://bench.cr.yp.to/supercop.html

[BOW23]

Benjamin, D., O’Brien, D., Westerbaan, B.: Merkle Tree Certificates for TLS. Internet-Draft draft-davidben-tls-merkle-tree-certs-00, Internet Engineering Task Force, March 2023. Work in Progress

[Clo23]

AWS CloudHSM. FAQS - Performance and capacity (2023). https://aws.amazon.com/cloudhsm/faqs/#Performance_and_capacity. Accessed 21 Feb 2023

[DOTV08]

Dahmen, E., Okeya, K., Takagi, T., Vuillaume, C.: Digital signatures out of second-preimage resistant hash functions. In: Buchmann, J., Ding, J. (eds.) PQCrypto 2008. LNS, pp. 109–123. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-88403-3_8CrossRef

[FHKS22]

Fregly, A., Harvey, J., Kaliski, Jr., B.S., Sheth, S.: Merkle tree ladder mode: reducing the size impact of NIST PQC signature algorithms in practice. Cryptology ePrint Archive, Report 2022/1730 (2022). https://eprint.iacr.org/2022/1730

[GK12]

Gueron, S., Krasnov, V.: Parallelizing message schedules to accelerate the computations of hash functions. J. Cryptogr. Eng. 2(4), 241–253 (2012)CrossRef

[GM18]

Genise, N., Micciancio, D.: Faster Gaussian sampling for trapdoor lattices with arbitrary modulus. In: Nielsen, J., Rijmen, V. (eds.) EUROCRYPT 2018 Part I. LNCS, vol. 10820, pp. 174–203. Springer, Heidelberg (2018). https://doi.org/10.1007/978-3-319-78381-9_7CrossRef

[GPV08]

Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Ladner, R.E., Dwork, C. (eds.) 40th ACM STOC, pp. 197–206. ACM Press, May 2008

[HBD+22]

Hülsing, A., et al.: SPHINCS⁺. Technical report, National Institute of Standards and Technology (2022). https://csrc.nist.gov/Projects/post-quantum-cryptography/selected-algorithms-2022

[HTT23]

HTTP Archive. Report: Page Weight (2023). https://httparchive.org/reports/page-weight. Accessed 21 July 2023

[HW22]

Howe, J., Westerbaan, B.: Benchmarking and analysing the NIST PQC finalist lattice-based signature schemes on the ARM cortex M7. Cryptology ePrint Archive, Report 2022/405 (2022). https://eprint.iacr.org/2022/405

[Kle17]

Klein, M.: Lyft’s Envoy: Experiences Operating a Large Service Mesh. SREcon17 Americas (2017). https://www.usenix.org/sites/default/files/conference/protected-files/srecon17americas_slides_klein.pdf

[LDK+22]

Lyubashevsky, V., et al.: CRYSTALS-DILITHIUM. Technical report, National Institute of Standards and Technology (2022)

[MP12]

Micciancio, D., Peikert, C.: Trapdoors for lattices: Simpler, tighter, faster, smaller. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 700–718. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_41CrossRef

[PFH+20]

Prest, T., et al.: FALCON. Technical report, National Institute of Standards and Technology (2020). https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization/round-3-submissions

[PFH+22]

Prest, T., et al.: FALCON. Technical report, National Institute of Standards and Technology (2022)

[Por19]

Pornin, T.: New efficient, constant-time implementations of Falcon. Cryptology ePrint Archive, Report 2019/893 (2019). https://eprint.iacr.org/2019/893

[PST20]

Paquin, C., Stebila, D., Tamvada, G.: Benchmarking post-quantum cryptography in TLS. In: Ding, J., Tillich, J.-P. (eds.) PQCrypto 2020. LNCS, pp. 72–91. Springer, Heidelberg (2020). https://doi.org/10.1007/978-3-030-44223-1_5CrossRef

[SKD20]

Sikeridis, D., Kampanakis, P., Devetsikiotis, M.: Post-quantum authentication in TLS 1.3: a performance study. In: NDSS 2020. The Internet Society, February 2020

[SM16]

Stebila, D., Mosca, M.: Post-quantum key exchange for the internet and the open quantum safe project. In: Avanzi, R., Heys, H.M. (eds.) SAC 2016. LNCS, vol. 10532, pp. 14–37. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-319-69453-5_2CrossRef

[Smi23]

Smith, B.: Crate ring (2023). https://github.com/briansmith/ring. Accessed 24 Feb 2023

[SSW20]

Schwabe, P., Stebila, D., Wiggers, T.: Post-quantum TLS without handshake signatures. In: Ligatti, J., Ou, X., Katz, J., Vigna, G (eds.) ACM CCS 2020, pp. 1461–1480. ACM Press, November 2020

[ST16]

Santesson, S., Tschofenig, H.: Transport Layer Security (TLS) Cached Information Extension. RFC 7924, July 2016

[TSH+12]

Topalovic, E., Saeta, B., Huang, L.S., Jackson, C., Boneh, D.: Towards short-lived certificates. In: IEEE Oakland Web 2.0 Security and Privacy (W2SP) (2012)

[Wes21]

Westerbaan, B.: Sizing up post-quantum signatures (2021). https://blog.cloudflare.com/sizing-up-post-quantum-signatures/. Accessed 21 July 23

[You22]

Young, S.D.: National security memo on promoting United States leadership in quantum computing while mitigating risks to vulnerable cryptographic systems (NSM-10). Executive Office of the President, Office of Management and Budget, Washington, DC, USA (2022)

Titel: Batch Signatures, Revisited
verfasst von: Carlos Aguilar-Melchor
Martin R. Albrecht
Thomas Bailleux
Nina Bindel
James Howe
Andreas Hülsing
David Joseph
Marc Manzano
Verlag: Springer Nature Switzerland
Buch: Topics in Cryptology – CT-RSA 2024
Print ISBN: 978-3-031-58867-9

Electronic ISBN: 978-3-031-58868-6

Copyright-Jahr: 2024
DOI: https://doi.org/10.1007/978-3-031-58868-6_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"

Premium Partner