Corectarea erorii „Reverse” Reed-Solomon, dat fiind prefixul de intrare

Am o sfoară $S$ de lungime (să zicem) 34, despre care cunosc primii (să zicem) 24 de octeți, dar nu ultimii 10. Am și codul de corectare a erorilor de 10 octeți $RS_{44,34}(S)$ în întregime. Am vreo speranță să-mi revin? $S$?

Cantitatea de informații de $S$ care îmi lipsesc depășește cu mult garanția teoretică a lui Reed-Solomon (care cred că în acest caz este de 3 octeți), dar, în același timp, există $2^{80}$ valori posibile pentru porțiunea necunoscută a $S$, Si deasemenea $2^{80}$ posibile ieşiri pentru corectarea erorilor. Dacă ar fi să iterăm peste toate valorile posibile pentru porțiunea necunoscută a $S$, m-aș aștepta naiv ca aproximativ 1 dintre ele să se potrivească cu corectarea erorilor. Dar $2^{80}$ este prea mult pentru forța brută.

Există tehnici care ar putea recupera (sau cel puțin reduce spațiul de stare pentru) o intrare, având în vedere Reed-Solomon EC? Există vreun motiv să credem într-un fel sau altul că RS este sigur din punct de vedere criptografic în acest sens?

Pentru fundal, aplicația „lumea reală” de aici este că am un cod QR (versiunea 2, EC de nivel L) unde nu am biții de date principali, dar am biții EC. Știu că datele sunt o adresă URL pe un anumit domeniu, deci prefixul.

Există tehnici care ar putea recupera (sau cel puțin reduce spațiul de stare pentru) o intrare, având în vedere Reed-Solomon EC?

Ai noroc - Reed-Solomon este un cod liniar, adică secțiunea de corectare a erorilor este o funcție liniară a intrării și, de fapt, prin fixarea tuturor, cu excepția a 10 octeți ai intrării, este o bijecție.

Acest lucru înseamnă că puteți reconstrui eficient cei 10 octeți lipsă ai intrării; Eliminarea gaussiană ar funcționa și, deși probabil că vor fi disponibili algoritmi mai eficienți, eliminarea gaussiană ar dura aproximativ $10^3$ operațiuni și astfel că ar putea fi suficient de eficient.

Nu toate codurile au proprietatea plăcută pe care o au codurile RS, adică fiecare $k$ simbolurile sunt un set de informații care poate fi folosit pentru a reconstrui cuvântul de cod original.

Sunt eficiente decodoare de ștergere acolo. Ștergerea înseamnă că unele simboluri sunt necunoscute, nu doar greșite.

De exemplu, aceasta lucrare recentă prezintă un algoritm de decodare eficient pentru codurile RS peste câmpul finit cu $q$ elemente, $\mathbb{F}_q$ cu $q=2^m,$ în $O(q \log_q q^2)$ timp. Utilizează transformări Walsh pentru a face interpolarea Lagrange.