RSA-Full Domain Hash Revisited
Timo Räth · 2014
RSA Full Domain Hash ist im Zufallsorakelmodell ein EUF-CMA sicheres Signaturverfahren (existentially unforgeable under chosen-message attacks). Der Sicherheitsbeweis wird unter anderem in der Vorlesung Einf{\u}hrung in die Kryptographie vorgestellt. Auch bei einer genaueren Analyse verliert man bei der Reduktion einen Faktor icefrac{1}{q_{s}}(wobei q_{s}die Anzahl der Anfragen an das Signaturorakel darstellt), was f{\u}r die Praxis in relativ grosen Systemparametern (RSA-Modul) resultiert [1].Seit der Ver{\o}ffentlichung von [2] wurde geglaubt, dass der Faktor icefrac{1}{q_{s}}optimal ist. Erst zehn Jahre sp{\a}ter offenbarten die Autoren von [3] einen Fehler in [2] und zeigten eine bessere Reduktion allerdings unter einer etwas st{\a}rkeren Sicherheitsannahme.Die Ergebnisse aus [3] lassen sich auf PSS-Verfahren (Probabilistic Signature Scheme), das z.B. in PKCS #1 benutzt wird, {\u}bertragen und sind somit von groser Bedeutung f{\u}r die Praxis. Weiterhin sind die in den Beweisen verwendete Techniken n{\u}tzlich auch bei anderen kryptographischen Verfahren.In Rahmen dieser Arbeit sollen die entsprechenden Sicherheitsbeweise aufgearbeitet und dessen Auswirkungen f{\u}r die Praxis analysiert werden.[1] J.S. Coron, “On the Exact Security of Full Domain Hash”, CRYPTO 2000. LNCS 1880, pp. 229-235, 2000.[2] J.S. Coron, “Optimal security proofs for PPS and other signature schemes”, EUROCRYPT 2002. LNCS 2332, pp 272-287, 2002.[3] S.A. Kakvi and E. Kiltz, “Optimal Security Proofs for Full Domain Hash, Revisited”, in EUROCRYPT 2012. LNCS 7237, pp 537-553, 2012.