A company uses a set of locks to secure their employees' offices. Each lock can be operated by a key distinct from other locks (the office holder's key) as well as a master key that is common to all locks. Each lock has 7 pins (7 positions on the key), and each of these positions has 6 possible cut depths. Any user's key can be represented as a series of these depths, e.g. 3-4-1-6-6-2-3. The master key can also be represented this way; let's say the master is: 5-2-3-4-2-6-1. There are two rules for users' keys:
- For each position, the user's code cannot be the same as the master key. E.g., no user could ever have a key that has a 5 in the first position.
- A user's code for any given position cannot be +/- 1 off from the master. E.g. in the first position, a user key cannot be 4 or 6. In the last position, a user's key cannot be 2.
Now consider a malicious insider, Eve, who can obtain access to other peoples' keys, but not the master key. Eve wants to determine the master key code. Suppose Eve samples legal user keys uniformly at random, without replacement (but the answer with replacement would be good, too, if it's simple).
Is it possible to determine approximately how many keys would Eve need to examine to have, say, a 50% chance of knowing the master key exactly by process of elimination? 90? We are not allowing Eve to make an attempt on the master lock before she is sure what it is.
A computational solution is welcome!