First, apologies for the title. This is an odd question, and I couldn't come up with a simple title for it.
My question is as follows.
Given a positive integer $k$, determine a set of properties $S$ such that exactly $k$ positive integers satisfy all the properties in $S$, subject to the following conditions:
- Given only information on $S$, one can verify in polynomial time whether or not a given integer $n$ satisfies all the properties in $S$.
- Given only information on $S$, one cannot generate any of the $k$ positive integers in polynomial time.
- Given only information on any $m$ of the $k$ integers, there is no practicably fast way of guessing any of the remaining $k-m$ integers.
The inspiration behind this question is in allowing $k$ different individuals to access the same safe. By providing $k$ different passwords (the $k$ positive integers above), it is possible to track which individual has accessed the safe. The three properties above are imposed for the following reasons:
- Quick Authentication. With only information on $S$, the safe is able to quickly authenticate a correct password.
- Security. Even if the information on $S$ is compromised, no third party will be able to generate any of the correct passwords.
- Prevention of Fraud / Impersonation. No $m$ of the individuals can use the information they have on their own passwords to guess one of the remaining $k-m$ passwords.
I'm not sure that the two problems are exactly parallel but I believe that mathematics should be interesting on its own.