LM One-time-signature is NEIN NEIN SU-CMA

DMT
Windoof-User
Windoof-User
Beiträge: 25
Registriert: 18. Dez 2007 23:54

LM One-time-signature is NEIN NEIN SU-CMA

Beitrag von DMT » 27. Feb 2009 15:58

Hallo ihr Gitterheroes,
in der Vorlesung über Lattice-Based Hashfunctions haben wurde behauptet, dass das Lyubashevsky-Micciancio One-Time-Signature Verfahren Strongly unforgeble under choosen message attack sein soll.
Aber irgendwie is das wohl Murks, weil ein One-Time Verfahren impliziert, dass man es nur EINMAL benutzen darf. Bei SU-CMA kann man aber polynomiell oft ein Signatur-Orakel anfragen. Folglich dürfte das LM-OTS nicht SU-CMA sein!

Hier nochmal die Definitionen aus dem Skript:
CLAIM:
The LM one-time-signature is SU-CMA.

DEFINITION:
"Strongly Unforgeable under adaptive Chosen Message Attack" means that a forger can
query a signing-oracle polynomially many times with messages \(m_i\) of his choice for
which he gets the corresponding signature \(s_i\). A hash-function is called SU-CMA if
every forger cannot produce a valid message/signature pair \((m_{k+1},s_{k+1})\) with
\((m_{k+1},s_{k+1})\neq(m_1,s_1),\ldots,(m_k,s_k).\)
"Quis custodiet ipsos custodes?"
~Juvenal

rueckert
Mausschubser
Mausschubser
Beiträge: 57
Registriert: 9. Apr 2008 09:25

Re: LM One-time-signature is NEIN NEIN SU-CMA

Beitrag von rueckert » 27. Feb 2009 18:26

LM-OTS ist (poly(n), 1, \epsilon)-strongly unforgeable. Also sicher gegen Angreifer mit polynomieller Laufzeit im Sicherheitsparamter n, die eine Anfrage stellen dürfen. Die Erfolgswsk. solcher Angreifer ist nach oben durch ein vernachlässigbares \epsilon beschränkt.

Also.. JA JA JA -- SU-CMA.

Die Modelle für Einmalsignaturen haben in der (t,q,e) Schreibweise immer q = 1.
Potentiell kann man aus dieser einen Anfrage aber mehrere Signaturen gewinnen. Es merkt ja niemand, dass der aktuelle public key schon "verbraucht" ist. Man schickt ihn bei Merkle zusammen mit dem Authentisierungspfad und gut.

Antworten

Zurück zu „Archiv“