The provable security of elgamal-type signature schemes
Manuel Fersch · Dokumentenrepositorium der RUB (Ruhr University Bochum) · 2018
Zu den in der Praxis am weitesten verbreiteten Signaturschemata gehören DSA und ECDSA. Sie sind in vielen Standards vertreten, darunter IEEE P1363, ANSI X9.62, und FIPS 186-4. In dieser Arbeit beschreiben wir GenElgamal, ein Rahmenwerk für Signaturschemata, das sowohl DSA und ECDSA, als auch deren russische und chinesische Pendants GOST 34.10 und SM2 umfasst. Nach sorgfältiger Modellierung der "modulo q"-Konversionsabbildung als Komposition von drei unabhängigen Funktionen beweisen wir Resultate zur Sicherheit von GenElgamal, die darauf schließen lassen, dass das Fälschen von Signaturen so schwer ist, wie das Berechnen diskreter Logarithmen. Mit einem konservativeren Ansatz zeigen wir weiter, dass das Signatur-Orakel redundant ist, wenn die Hash-Funktion von GenElgamal als Zufallsorakel modelliert wird und der Signierer höchstens eine Signatur pro Nachricht ausgibt. Abschließend diskutieren wir, ob und wie die oben beschriebenen Argumente speichereffizienter gemacht werden können.