Aprendendo com oráculos "taciturnos"

Minha pergunta é um pouco genérica, então estou inventando uma boa história para justificá-la. Tenha paciência comigo se não for realista ;-)

História

X, chefe do departamento de segurança de computadores de uma grande empresa, é um pouco paranóico: ele exige que todos os funcionários alterem suas senhas uma vez por mês, a fim de minimizar os riscos de roubo de identidade ou informações. Além disso, ele não confia que os funcionários possam criar senhas seguras.

Portanto, todos os meses, ele gera novas senhas usando um software que ele escreveu e as entrega aos funcionários para que eles possam efetuar login novamente. Mas, além de ser paranóico, o Sr. X também é um pouco preguiçoso: as senhas que ele gera seguem alguns padrões, e o algoritmo usado para permitir que as pessoas façam login apenas verifica se a senha "parece bem" de acordo com essa regra, e que não está na "lista expirada".

Infelizmente, seu comportamento pretensioso deixou muita gente amarga, e um deles, o Sr. Y, decide provar que ele pode decifrar suas senhas. Então, uma noite, ele coleta algumas delas e começa a tentar criar um algoritmo de aprendizado para gerar senhas válidas, usando seu computador pessoal para verificá-las.

Questão

O oráculo usado pelo Sr. Y é um pouco estranho, pois diz a ele "a verdade, mas não toda a verdade" (daí o adjetivo "taciturno"). Mais precisamente: o Sr. Y saberá que uma senha é válida quando o computador a aceitar, mas quando uma senha for rejeitada, o Sr. Y não saberá se poderia ou não ter sido válido: a senha pode ser rejeitada porque não corresponde a algum padrão, mas também pode ser rejeitado porque costumava ser válido, mas não é mais, de acordo com a regra de "mudança uma vez por mês" do Sr. X.

Então, o Sr. Y será capaz de criar alguma coisa nesse cenário? Ou podemos afirmar / provar que as senhas do Sr. X são inerentemente imprevisíveis (conforme definido na configuração de aprendizado do PAC, mas talvez esse conceito exista em outras estruturas)?

Parece que você está tentando fazer o PAC aprender um idioma apenas vendo exemplos positivos. Isso é chamado "aprendendo com exemplos positivos (apenas)". Mas você também tem o poder de rotular alguns de seus próprios exemplos inventados: se o oráculo fosse totalmente verdadeiro, essas seriam consultas de associação, para que seu modelo fosse conhecido como "aprendendo com exemplos positivos e consultas de associação". Nesta estrutura, existem alguns resultados - por exemplo, linguagens em árvore são aprendidas (não seguras). O DFA não se deve a resultados de dureza de criptografia . (Veja também isso .)

Obviamente, sua configuração não é bem assim. Suas consultas de associação são mais limitadas. Parece que os resultados conhecidos da intratabilidade seriam transferidos para a sua configuração a partir do modelo que descrevi, mas os resultados da capacidade de aprendizado deixariam você com algum trabalho a fazer. Mas o esquema do Sr. X é seguro ou não, dependendo do "padrão" que ele usa.

Além disso - parece um requisito estranho ser capaz de provar "as senhas do Sr. X são inerentemente imprevisíveis". Normalmente, não basta gerar uma nova senha válida para quebrar um sistema assim? Mas essa parece ser a consulta ao próprio algoritmo do Sr. Y ...

A dificuldade de engenharia reversa do algoritmo parece depender de quanto do espaço de chaves já expirou.

Digamos que o algoritmo do Sr. X seja muito restrito, então existem (digamos) apenas 10.000 chaves potencialmente válidas. Se o Sr. X iniciou recentemente essa empresa, existem muito poucas chaves expiradas - e, portanto, poucos "falsos negativos" -, então a engenharia reversa do algoritmo pode ser relativamente fácil. Se o Sr. X já expirou 9.000 das chaves potencialmente válidas e, portanto, temos 9 em cada 10 "falsos negativos", a engenharia reversa do algoritmo parece ser muito mais difícil. E, é claro, se o Sr. X já expirou todas as chaves potencialmente válidas, exceto aquelas que o Sr. Y e seus colaboradores já conhecem, o "oráculo taciturno" fornecerá zero novas informações.

Parece que apenas finitas senhas válidas podem ser usadas. Se o idioma da senha for finito, não haverá esperança (como neste caso, todas as senhas válidas podem ser usadas; nesse caso, o oracle sempre retorna FALSE).

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