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:


1. Given only information on $S$, one can verify in polynomial time whether or not a given integer $n$ satisfies all the properties in $S$.
2. Given only information on $S$, one cannot generate any of the $k$ positive integers in polynomial time.
3. 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:


1. **Quick Authentication**. With only information on $S$, the safe is able to quickly authenticate a correct password.
2. **Security**. Even if the information on $S$ is compromised, no third party will be able to generate any of the correct passwords.
3. **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.



Generating a set of integer passwords that can be securely authenticated
What about this simple solution: the "safe" contains the $k$ public keys of some RSA pair, the users own each one his/her private key. Standard public/private key authentication methods can now be used. Your set $S$ contains the single property "the key is the private key associated to either one of these $k$ public keys."


