Обучение с «молчаливыми» оракулами

Мой вопрос немного общий, поэтому я придумываю хорошую историю, чтобы оправдать его. Терпите меня, если это не реально ;-)

Сказка

Г-н Х, глава отдела компьютерной безопасности крупной компании, немного параноик: он требует, чтобы все сотрудники меняли свои пароли раз в месяц, чтобы минимизировать риски кражи личных данных или информации. Более того, он не верит, что сотрудники смогут придумать надежные пароли.

Поэтому каждый месяц он генерирует новые пароли, используя написанное им программное обеспечение, и передает их сотрудникам, чтобы они могли снова войти в систему. Но помимо того, что он параноик, мистер Х также немного ленив: все генерируемые им пароли следуют некоторому шаблону, а алгоритм, используемый для входа в систему, только проверяет, что пароль «выглядит хорошо» в соответствии с этим правилом и что отсутствует в «списке с истекшим сроком действия».

К сожалению, его претенциозное поведение вызвало недовольство многих людей, и один из них, г-н Y, решает доказать ему, что он может взломать свои пароли. Итак, однажды ночью он собирает несколько из них и начинает пытаться разработать алгоритм обучения для генерации действительных паролей, используя свой персональный компьютер для их проверки.

Вопрос

Оракул, использованный г-ном Y, немного странный, поскольку он говорит ему «правду, но не всю правду» (отсюда и прилагательное «молчаливый»). Точнее: г-н Y будет знать, что пароль действителен, когда его компьютер принимает его, но когда пароль отклонен, г-н Y не будет знать, мог ли он быть действительным: пароль может быть отклонен, потому что он не соответствуют некоторому шаблону, но он также может быть отклонен, потому что раньше он действовал, но больше не является, согласно правилу г-на Х «изменение один раз в месяц».

Так сможет ли мистер Y когда-нибудь придумать что-нибудь в этой обстановке? Или мы можем утверждать / доказывать, что пароли г-на X по своей природе непредсказуемы (как определено в настройке обучения PAC, но, возможно, эта концепция существует в других структурах)?

Кажется, вы пытаетесь PAC выучить язык, увидев только положительные примеры. Это называется «учиться на положительных примерах (только)». Но у вас также есть возможность пометить некоторые из ваших собственных вымышленных примеров: если бы оракул был полностью правдив, то это были бы запросы на членство, поэтому ваша модель была бы известна как «изучение положительных примеров и запросов на членство». В этой структуре есть некоторые результаты - например, древовидные языки являются изучаемыми (небезопасными). DFA не из-за результатов криптостойкости . (Также посмотрите это .)

Конечно, ваши настройки не совсем так. Ваши запросы на членство более ограничены. Похоже, что тогда известные результаты проходимости будут перенесены в ваши настройки из описанной мною модели, но результаты обучения помогут вам проделать определенную работу. Но схема мистера X безопасна или нет, в зависимости от того, какой «шаблон» он использует.

Кроме того - кажется странным требование быть в состоянии доказать, что «пароли мистера Икс по своей природе непредсказуемы». Разве обычно не достаточно просто создать новый действительный пароль, чтобы взломать такую ​​систему? Но это, кажется, запрос к самому алгоритму мистера Y ...

Кажется, что сложность обратного инжиниринга алгоритма зависит от того, сколько из пространства ключей уже истекло.

Скажем, алгоритм мистера X очень ограничен, поэтому есть (скажем) только 10 000 потенциально допустимых ключей. Если г-н Х только недавно основал эту компанию, поэтому у него очень мало ключей с истекшим сроком действия и, следовательно, мало «ложных негативов», то обратный инжиниринг алгоритма может быть относительно простым. Если у мистера X уже истекло 9 000 потенциально допустимых ключей, и поэтому у нас есть 9 из 10 «ложных негативов», то обратный инжиниринг алгоритма кажется гораздо более сложным. И, конечно же, если у мистера X уже истек срок действия каждого потенциально действительного ключа, кроме тех, которые мистер Y и его сотрудники уже знают, то «молчаливый оракул» даст ему ноль новой информации.

Похоже, что на самом деле можно использовать только конечное число действительных паролей. Если язык паролей конечен, то надежды нет (как в этом случае, могут использоваться все действительные пароли, и в этом случае оракул всегда возвращает FALSE).

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