Nauka z „małomównymi” wyroczniami

Moje pytanie jest trochę ogólne, więc wymyślam fajną historię, aby to uzasadnić. Zrób ze mną, jeśli to nie jest realistyczne ;-)

Fabuła

Pan X, szef działu bezpieczeństwa komputerowego w dużej firmie, jest nieco paranoiczny: wymaga od wszystkich pracowników zmiany hasła raz w miesiącu, aby zminimalizować ryzyko kradzieży tożsamości lub informacji. Co więcej, nie ufa pracownikom, że wymyślą bezpieczne hasła.

Dlatego co miesiąc generuje nowe hasła za pomocą napisanego przez siebie oprogramowania i przekazuje je pracownikom, aby mogli się ponownie zalogować. Ale oprócz tego, że jest paranoikiem, pan X jest również trochę leniwy: hasła, które generuje, są zgodne z pewnym wzorcem, a algorytm pozwalający na logowanie się tylko sprawdza, czy hasło „wygląda dobrze” zgodnie z tą zasadą i czy jest zgodne nie ma na „liście wygasłych”.

Niestety jego pretensjonalne zachowanie spowodowało, że wielu ludzi było zgorzkniałych, a jeden z nich, pan Y, postanowił udowodnić mu, że potrafi złamać swoje hasła. Pewnej nocy zbiera kilka z nich i zaczyna próbować zaprojektować algorytm uczenia się do generowania prawidłowych haseł, używając swojego komputera osobistego do ich weryfikacji.

Pytanie

Wyrocznia użyta przez pana Y jest nieco dziwna, ponieważ mówi mu „prawdę, ale nie całą prawdę” (stąd przymiotnik „milczący”). Dokładniej: Pan Y będzie wiedział, że hasło jest ważne, gdy jego komputer je zaakceptuje, ale gdy hasło zostanie odrzucone, Pan Y nie będzie wiedział, czy mogło być ważne: hasło może zostać odrzucone, ponieważ nie odpowiadają pewnemu wzorowi, ale można go również odrzucić, ponieważ był ważny, ale już nie jest, zgodnie z regułą pana X dotyczącą „zmiany raz w miesiącu”.

Czy pan Y kiedykolwiek będzie w stanie wymyślić coś w tym otoczeniu? Czy też możemy twierdzić / udowodnić, że hasła Pana X są z natury nieprzewidywalne (jak zdefiniowano w ustawieniach uczenia się PAC, ale może ta koncepcja istnieje w innych ramach)?

Wygląda na to, że próbujesz PAC nauczyć się języka, widząc tylko pozytywne przykłady. Nazywa się to „uczeniem się na pozytywnych przykładach (tylko)”. Ale masz również moc, aby oznaczyć niektóre z twoich wymyślonych przykładów: jeśli wyrocznia byłaby w pełni zgodna z prawdą, to byłyby to pytania o członkostwo, więc twój model byłby znany jako „uczenie się na podstawie pozytywnych przykładów i pytań o członkostwo”. W tej strukturze są pewne wyniki - na przykład, języki drzewa można się nauczyć (nie są bezpieczne). DFA nie wynikają z twardości kryptograficznej . (Patrz także to ).

Oczywiście twoje ustawienie nie jest do końca takie. Twoje pytania dotyczące członkostwa są bardziej ograniczone. Wygląda na to, że znane wyniki nieuchronności przeniosłyby się do twojego ustawienia z modelu, który opisałem, ale wyniki uczenia się pozostawiłyby ci trochę pracy. Ale schemat pana X jest bezpieczny lub nie, w zależności od „wzorca”, którego używa.

Ponadto - wydaje się dziwnym wymogiem, aby móc udowodnić, że „hasła pana X są z natury nieprzewidywalne”. Czy zwykle nie wystarczy wygenerować nowe prawidłowe hasło, aby złamać taki system? Ale wydaje się, że jest to zapytanie do samego algorytmu pana Y ...

Trudność inżynierii wstecznej algorytmu wydaje się zależeć od tego, ile przestrzeni kluczy już wygasło.

Powiedzmy, że algorytm pana X jest bardzo ograniczony, więc istnieje (powiedzmy) tylko 10 000 potencjalnie poprawnych kluczy. Jeśli Pan X dopiero niedawno założył tę firmę, więc jest bardzo mało kluczy, które wygasły - a zatem niewiele „fałszywych negatywów” - to odwrotna inżynieria algorytmu może być stosunkowo łatwa. Jeśli Pan X wygasł już 9 000 potencjalnie ważnych kluczy, a więc mamy 9 na 10 „fałszywych negatywów”, wówczas inżynieria wsteczna algorytmu wydaje się znacznie trudniejsza. I oczywiście, jeśli Pan X wygasł już każdy potencjalnie ważny klucz, z wyjątkiem tych, które pan Y i jego współpracownicy już znają, wówczas „milcząca wyrocznia” da mu zero nowych informacji.

Wygląda na to, że w rzeczywistości można użyć tylko wielu poprawnych haseł. Jeśli język haseł jest skończony, nie ma nadziei (tak jak w tym przypadku można użyć wszystkich poprawnych haseł, w którym to przypadku wyrocznia zawsze zwraca FAŁSZ).

$N$$> 2^n$$n$