Learning Parity with Noise

[strahinjapraska]

Članovi tima: \ Strahinja Praška RA 245/2021 5. grupa\ Asistent: \ Filip Volarić\ Problem koji se rešava:\ "Rešavanje" Learning Parity with Noise problema, ovaj problem se javlja kod razbijanja HB protokola gde imamo komunikaciju izmedju R(eader) i T(ag), gde R postavlja testove T da vidi da li ima odgovarajući tajni ključ. Ti testovi su skalarni proizvod vektora $\langle a,s \rangle$ (računamo u polju $GF(2)$ ) gde je $s$ tajni ključ, a $a$ je random vektor koji je R poslao T i očekuje odgovor. Kada bi ovako uradili A(dversary) koji osluškuje bi mogao da pronadje tajni ključ $s$ Gausovom eliminacijom, zato T dodaje Bernulijev šum u odgovor,tj. $\langle a, s \rangle + e$ gde je $e = 1$ sa verovatnoćom $p$. Sada A rešava sistema jednačina $As\approx b$(svaka jednačina sistema je tačna sa verovatnoćom $p-1$). Naravno ovo je manja instanca problema, jer za dovoljno dugačak ključ problem je nerešiv.\ Algoritmi/tehnike:\ Bernoulli Naive Bayes, Random Forest(Decision Tree), Logistička regresija, ANN\ Podaci koji se koriste:\ Uzorci dobijeni iz LPNOracle-a\ Metrika za merenje performansi/Validacija rešenja:\ Hamming weight, ukoliko je visok znači da nam je kandidat za tajni ključ loš, ako je kandidat baš taj ključ $HW = broj\ uzoraka*p$

[Fickos]

Tema je odobrena. Srećan rad.

[strahinjapraska]

https://github.com/strahinjapraska/hb-cryptanalysis-ml