most recent 30 from http://mathoverflow.net 2013-05-24T05:31:43Z http://mathoverflow.net/feeds/user/24035 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/98093/generating-a-set-of-integer-passwords-that-can-be-securely-authenticated/98199#98199 none 2012-05-28T15:52:05Z 2012-05-28T15:52:05Z

<p>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.</p> <p>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.</p> <p>If you want to see how cryptographers approach this sort of problem, I like Bellare and Rogaway's lecture notes:</p> <ul> <li><a href="http://cseweb.ucsd.edu/users/mihir/cse207/classnotes.html" rel="nofollow">http://cseweb.ucsd.edu/users/mihir/cse207/classnotes.html</a></li> </ul> <p>Reading through the first 3 chapters or so should give you a feel for the subject.</p>