Beweisbar sichere, effiziente und langfristig sichere Varianten des Merkle Signaturverfahrens

• Antragsteller: Professor Dr. Johannes Buchmann
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2010 bis 2014
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 164415288

• Erstellungsjahr: 2013

Zusammenfassung der Projektergebnisse

Im Rahmen des Projektes wurde gezeigt, dass Hash-basierte Signaturverfahren eine für alle Anwendungsbereiche geeignete, langfristig sichere Post-Quantum-Alternative zu den heute verwendeten Signaturverfahren sind. Mit XMSS wurde ein neues Hash-basiertes Signaturverfahren entwickelt, das minimale Sicherheitsvoraussetzungen im doppelten Sinn hat. Einerseits wird im Gegensatz zu den heute verwendeten Verfahren nur eine sichere Hashfunktion benötigt und kein zusätzliches mathematisches Problem. Andererseits sind die Sicherheitsannahmen von XMSS auch komplexitätstheoretisch minimal. Darüberhinaus ist eine XMSS Signatur nur halb so groß wie eine Signatur mit GMSS – dem zuvor effizientesten Hash-basierten Signaturverfahren – bei gleichbleibendem Sicherheitslevel. Dies ist besonders relevant, da die Signaturgröße als der größte Nachteil Hash-basierter Signaturen gegenüber anderen Verfahren betrachtet wird. Neben der Entwicklung von XMSS konnte gezeigt werden, dass XMSS sich für alle gängigen Anwendungsfälle eignet. So wurde neben Implementierungen für Standard-CPUs auch eine Umsetzung auf einem Smartcard Micro-Prozessor erstellt. Selbst auf dieser Ressourcen-beschränkten Plattform erreicht XMSS eine Performance, vergleichbar zu jener von RSA. Weiterhin wurde ein Programm entwickelt, das auf der Basis linearer Optimierung optimale Parameter für einen gegebenen Anwendungsfall erzeugt. Ebenso konnte gezeigt werden, dass XMSS eine Vielzahl an Vorteilen mit sich bringt, wenn eine langfristige Sicherheit von Signaturen notwendig ist. Es wurde bewiesen, dass XMSS neben Standardsicherheit auch Vorwärtssicherheit bietet. Diese Eigenschaft erlaubt es den Einsatz von Zeitstempeln für Signaturen zu minimieren. Dies reduziert den Speicherbedarf bei der langfristigen Archivierung von Signaturen. Darüberhinaus konnte gezeigt werden, wie durch den Einsatz von Hashcombinern die Wahrscheinlichkeit für einen plötzlichen Bruch des Verfahrens minimiert werden kann. Dies ist für heutige Signaturverfahren nur durch Mehrfachsignaturen zu erreichen. Zu guter Letzt sind die Eigenschaften die XMSS von der verwendeten Hashfunktion fordert weit schwächer als jene die eine sichere kryptographische Hashfunktion allgemein bieten muss. Die Erfahrung mit etablierten Hashfunktionen zeigt, dass wenn eine etablierte Hashfunktion als theoretisch gebrochen gilt, diese schwächeren Annahmen noch bestehen. Dies kann als Frühwarnsystem verwendet werden, um in Szenarien mit Anforderungen an Langzeitsicherheit rechtzeitig eine Übersignatur zu veranlassen.

Projektbezogene Publikationen (Auswahl)

• On the security of the Winternitz one-time signature scheme. In A. Nitaj and D. Pointcheval, editors, Africacrypt 2011, volume 6737 of Lecture Notes in Computer Science, pages 363–378. Springer Berlin / Heidelberg, 2011
  Johannes Buchmann, Erik Dahmen, Sarah Ereth, Andreas Hülsing, and Markus Rückert
  
• XMSS - a practical forward secure signature scheme based on minimal security assumptions. In Bo-Yin Yang, editor, Post-Quantum Cryptography, volume 7071 of Lecture Notes in Computer Science, pages 117–129. Springer Berlin / Heidelberg, 2011
  Johannes Buchmann, Erik Dahmen, and Andreas Hülsing
  
• Forward secure signatures on smart cards. In Lars R. Knudsen and Huapeng Wu, editors, Selected Areas in Cryptography, volume 7707 of Lecture Notes in Computer Science, pages 66–80. Springer Berlin Heidelberg, 2013
  Andreas Hülsing, Christoph Busold, and Johannes Buchmann
  
• On the security of the Winternitz one-time signature scheme. Journal of Applied Cryptography, 3(1):84–96, 2013
  Johannes Buchmann, Erik Dahmen, Sarah Ereth, Andreas Hülsing, and Markus Rückert
  
• Optimal parameters for XMSSM T . In Alfredo Cuzzocrea, Christian Kittl, DimitrisE. Simos, Edgar Weippl, and Lida Xu, editors, Security Engineering and Intelligence Informatics, volume 8128 of Lecture Notes in Computer Science, pages 194–208. Springer Berlin Heidelberg, 2013
  Andreas Hülsing, Lea Rausch, and Johannes Buchmann
  
• W-OTS+ — shorter signatures for hash-based signature schemes. In A.Youssef, A. Nitaj, and A.E. Hassanien, editors, Africacrypt 2013, volume 7918 of Lecture Notes in Computer Science, pages 173–188. Springer Berlin / Heidelberg, 2013
  Andreas Hülsing