Prova della sicurezza quantistica dello schema di firma Merkle

1

L' articolo di Wikipedia sullo schema delle firme di Merkle afferma che è

very adjustable and resistant against quantum computing.

Che prove ci sono di questo?

    
posta user2443423 03.01.2014 - 16:28
fonte

1 risposta

1

Lo schema di firma Merkle si basa su un albero hash su firme singole, ad es. utilizzando lo schema di Lamport .

In parole povere, sia lo schema di Lamport che l'albero di hash sono sicuri fintanto che la funzione di hash è resistente alle pre-immagini e alle seconde pre-immagini. Ci possono essere dettagli perché quando si usano gli alberi di hash, gli attacchi di pre-immagine sono spesso multi-target , cioè ci sono diversi valori per i quali l'attaccante vorrebbe una pre-immagine, e una pre-immagine per ognuno di essi darebbe un successo. Tuttavia, la resistenza al preimage continua a guidare la robustezza complessiva dello schema.

Contro il calcolo quantistico, una funzione "perfetta" di hash dei bit di dimensione n di output offre ancora una resistenza 2 n / 2 . Per esempio. con SHA-256 (un'uscita a 256 bit), il miglior computer quantistico avrebbe comunque bisogno di 2 128 operazioni (vale a dire troppi per essere fattibili, con un enorme margine) per rompere la resistenza di pre-immagine.

(Questo significa anche che contro i classici computer, una funzione hash a 256 bit è un overkill totale quando viene usata nello schema Merkle, ma, contro i computer classici, possiamo anche usare RSA o ECDSA, che sono molto più efficiente dello schema di Merkle.)

    
risposta data 03.01.2014 - 17:06
fonte

Leggi altre domande sui tag