Learning with "taciturn" oracles

Question

My question is a bit generic, so I'm making up a nice story to justify it. Bear with me if it's not realistic ;-)

Story

Mr. X, the head of the computer security department at a big company, is a bit paranoid: he requires that all employees change their passwords once a month, in order to minimise the risks of identity or information theft. Moreover, he does not trust the employees to be able to come up with secure passwords.

Therefore, every month, he generates new passwords using a piece of software he wrote, and gives them to the employees so that they can log in again. But besides being paranoid, Mr. X is also a bit lazy: the passwords he generates all follow some pattern, and the algorithm used to allow people to log in only checks that the password "looks okay" according to that rule, and that it is not in the "expired list".

Unfortunately, his pretentious behaviour made a lot of people bitter, and one of them, Mr. Y, decides to prove him that he can crack his passwords. So, one night, he collects a few of them, and starts trying to design a learning algorithm for generating valid passwords, using his personal computer to verify them.

Question

The oracle used by Mr. Y is a bit strange, in that it tells him "the truth, but not the whole truth" (hence the "taciturn" adjective). More precisely: Mr. Y will know that a password is valid when his computer accepts it, but when a password is rejected, Mr. Y will not know whether or not it could have been valid: the password may be rejected because it does not correspond to some pattern, but it may also be rejected because it used to be valid but no longer is, according to Mr. X's "change once a month"-rule.

So, will Mr. Y ever be able to come up with anything in that setting? Or can we claim/prove that Mr. X's passwords are inherently unpredictable (as defined in the PAC learning setting, but maybe this concept exists in other frameworks)?

Answer 1

It seems you're trying to PAC learn a language by only seeing positive examples. This is called "learning from positive examples (only)." But you also have the power to get some of your own made-up examples labeled: if the oracle were fully truthful, then these would be membership queries, so your model would be known as "learning from positive examples and membership queries." In this framework, there are some results - for example, tree languages are learnable (not secure). DFA are not due to crypto hardness results. (Also see this.)

Of course, your setting isn't quite this. Your membership queries are more limited. It seems that then the known intractability results would transfer to your setting from the model I described, but the learnability results would leave you with some work to do. But Mr. X's scheme is secure or not depending on the "pattern" he uses.

Also - it seems like a strange requirement to be able to prove "Mr. X's passwords are inherently unpredictable." Isn't it usually enough to just be able to generate a new valid password to break such a system? But this seems to be the query to Mr. Y's algorithm itself...

Answer 2

The difficulty of reverse-engineering the algorithm seems to depend on how much of the keyspace has already been expired.

Say the algorithm of Mr. X is very restricted, so there are (say) only 10,000 potentially valid keys. If Mr. X only recently started this company, so there are very few expired keys -- and hence few "false negatives" -- then reverse-engineering the algorithm may be relatively easy. If Mr. X has already expired 9,000 of the potentially valid keys, and so we have 9 out of 10 "false negatives", then reverse-engineering the algorithm seems to be much more difficult. And, of course, if Mr. X has already expired every potentially valid key except for the ones that Mr. Y and his collaborators already know, then the "taciturn oracle" will give him zero new information.

Answer 3

It appears that only finitely many valid passwords can in fact be used. If the password language is finite, then there is no hope (as in this case, all of the valid passwords may be used, in which case the oracle always returns FALSE).

Otherwise, simply restrict the learning process to sufficiently large samples. As this is a finite requirement, it does not change the complexity of the problem. You can use an exponential strategy to search for $N$ for sufficiently large. Try learning on queries $> 2^n$; if the learning algorithms fails increment $n$.