Generating a set of integer passwords that can be securely authenticated 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.
 A: 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."
A: Frederico has a good idea. First solve the problem for a single individual. I assume that whatever your  requirements are, you have a solution for that case. We can abstract the situation by saying that there is a known function $S$ such that $S(x)=0$ for a single integer $x$. 
Now imagine $k$ people and for each one their own $S_i(\cdot)$ with unique key $x_i$. First think of this as a room with $k$ different independent safes, that seems satisfactory for all three requirements (either scenario.). Instead make one big safe   $S(x)=S_1(x)S_2(x)\cdots S_k(x).$ That is as secure as the $k$ safe solution (just another way of looking at it.)
The $(n,k)$ threshold schemes are intricate in that any $k-1$ people together know nothing useful but any $k$ together know everything. That requires some clever interconnection. In this setting there need not be any essential connection; person 1 might use RSA, person 2 use elliptic curve cryptography etc.
A: If you're willing to assume the security of standard cryptographic primitives and add a few practical constraints in the description, this is a trivial crypto problem.  If you're not willing to assume the security of those primitives (i.e. you require proof of the nonexistence of a polynomial algorithm for generating the k integers, while keeping some practical size bounds on them), that inherently contains the massive open problem "P vs NP" for which you're unlikely to get an answer anytime soon.
The trivial solution assuming k is much smaller than $2^{128}$ is: the "good" numbers are the encryptions of $0,1,\ldots,k-1$ with AES under some secret key X.  To check a number knowing X, just decrypt it and see that the preimage is less than k.  If you want to go bigger than $2^{128}$ there are simple ways of building large ciphers using smaller ones as a building block.  This of course requires embedding X inside the safe, so the safe can generate more combinations.  You could also use a public-key scheme, like RSA signatures on the numbers 1,2...k-1 under soem appropriate padding method.
If you want to see how cryptographers approach this sort of problem, I like Bellare and Rogaway's lecture notes:


*

*http://cseweb.ucsd.edu/users/mihir/cse207/classnotes.html
Reading through the first 3 chapters or so should give you a feel for the subject.
