Ei bine, îmi dau seama că dacă tu într-adevăr reduceți lucrurile [1], puteți reduce semnătura la puțin sub 100 de octeți. Iată cum ți-am ajustat cerințele:
Vreau securitate pe 128 de biți sau mai bună (deși nu este o cerință grea).
Din moment ce ați spus că nu este o cerință grea, am resetat asta la securitate de 80 de biți (dacă faceți acest lucru cu securitate de 128 de biți, obțineți o semnătură de aproximativ 200 de biți). Prin țintirea securității de 80 de biți, putem folosi hash-uri de 80 de biți (de exemplu, SHA-256 trunchiat la 80 de biți - am putea încerca să folosim o funcție hash mai rapidă cu un nivel de securitate mai mic, totuși care accelerează lucrurile doar cu un factor modest, deci nu ma astept ca asta sa ne cumpere prea mult).
Voi semna blocuri de date care au 128 de octeți sau mai mici.
Nu este o problemă
Schema de semnătură nu trebuie să fie utilizată pe scară largă, standardizată de niciun organism autorizat sau compatibilă cu orice alte sisteme.
Nimeni nu este suficient de nebun pentru a standardiza această abordare
Eficiența calculării cheilor sau semnăturii nu este un factor major, atâta timp cât nu durează mai mult de un minut sau două pentru a face oricare pentru un bloc de 128 de octeți.
Ei bine, calculul cheii publice este polul lung aici, așa că voi lua o limită de 2 minute pentru asta. Cu toate acestea, nu ați spus care este hardware-ul, așa că voi presupune un hardware decent agresiv acolo - 8 nuclee rapide cu hardware AVX512 (de fapt, am putea deveni mai agresivi cu hardware dedicat, totuși asta nu ne-ar permite să micșorăm semnatura atat)
Să presupunem că vreau doar să emit aproximativ 10 ~ 20 de semnături și apoi să arunc cheia privată pentru totdeauna.
Voi presupune că 20 de semnături este maxim (un maxim de 16 ne-ar permite să reducem dimensiunea semnăturii cu încă 10 octeți).
Ok, iată ce facem: începem cu un design LMS/XMSS (fie modificând LMS pentru a permite un factor W mai mare, fie eliminând bitmasking-ul XMSS și amestecând locația în alt mod); atunci:
Avem un obiectiv de 20 de semnături; aceasta implică o înălțime Merkle de 5 (pe care am putea să o reducem înapoi la 4 dacă am putea presupune un maxim de 16 semnături)
O măsurătoare pe procesorul meu Xeon arată că un singur nucleu poate, cu instrucțiunile sale AVX2, să calculeze 6,6 milioane hashe-uri pe secundă; dacă ar fi să folosim un procesor mai rapid cu instrucțiuni AVX512, probabil că am putea obține până la 20 de milioane de hashe-uri pe secundă. Avem 8 nuclee și avem 120 de secunde pentru a calcula cheile, așa că avem timp să calculăm nu chiar 20 de miliarde de hashe-uri.
Acum, trebuie să generăm 20 de chei publice cu semnătură unică [2] (și orice altceva este relativ trivial) - deci, avem timp pentru aproape 1 miliard de hashe-uri pe semnătură unică
Dacă folosim o valoare Winternitz a $W \aproximativ 200.000.000$, care ne-ar permite să codificăm aproximativ 27 de biți. Acum, hash-ul pe care îl semnează semnătura unică este de 80 de biți; asta înseamnă că, cu codificare cu sumă constantă, ar trebui să generăm cu ușurință 4 cifre de bază-200.000.000 (metodă; introduceți valoarea care este semnată în SHAKE; generăm 3 cifre de bază-200.000.000 de cifre; vedeți dacă există o a patra cifră, astfel încât suma să fie ținta ; dacă nu, atunci întoarceți-vă și generați mai multe cifre)
- De fapt, deoarece calcularea lanțurilor Winternitz individuale nu este paralelizabilă, timpul luat (cu estimările hardware date) ar fi de fapt de aproximativ 2 minute și 40 de secunde. Simt că este încă în cerința „[nu] mai mult de un minut sau două” (și dacă nu, obțineți hardware ceva mai rapid...)
Deci, semnătura ar consta din:
Semnătura unică a hashului; 4 hash-uri a câte 10 octeți = 40 octeți
Calea de autentificare; 5 hashe-uri a câte 10 octeți = 50 octeți
Hash randomizator (de care aveți nevoie pentru a preveni posibilele atacuri de coliziune; aceasta este aleatorie pe care o amestecați în mesaj când îl hash); 40 de biți = 5 octeți
Indexul (de fapt, ați putea să renunțați la asta și doar verificatorul să verifice toți indicii posibili; nu am crezut că o economie de 1 octet a meritat); 1 octet
Total: 96 de octeți (cu o posibilitate de 86 de octeți dacă trebuie să generați doar 16 semnături)
[1]: Ați văzut filmul „Marțianul” (sau mai bine, citiți cartea – intră în mai multe detalii)? Dacă da, ceea ce fac eu seamănă mult cu ceea ce i-a făcut Mark Watney MAV...
[2]: Pentru acele noduri frunze Merkle pe care nu le vom folosi niciodată, de fapt nu trebuie să calculăm acele chei publice unice - în schimb, putem introduce doar valori inactiv. Nu vom putea semna cu ei - nu intenționăm niciodată
