2
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ Here's a simple idea: Let $P$ be the product of $2k$ large primes, half of which are congruent to $1$ modulo $4$, and consider the properties of being a prime, being a divisor of $P$, and being congruent to $1$ modulo $4$. Unfortunately, there is no guarantee that factoring is hard... $\endgroup$
    – zeb
    May 27, 2012 at 8:08
  • $\begingroup$ This sounds like a special case of a $(n,k)$-threshold scheme. Such a scheme can be used to share a secrete among $n$ individuals, such that any subset of at least $k$ of them can recover the secret. You are interested in the case $k=1$. There are tons of material on that in the literature; indeed, the Wikipedia page might be a good starting point: en.wikipedia.org/wiki/Secret_sharing $\endgroup$
    – Max Horn
    May 27, 2012 at 9:46
  • $\begingroup$ @zeb That sounds like a pretty good solution! When you say that there is no guarantee that factoring is hard, do you mean that the system would be approximately as secure as encryption schemes like the RSA algorithm? $\endgroup$
    – Vincent Tjeng
    May 27, 2012 at 14:20
  • $\begingroup$ Hi @Max, I read up on the secret sharing scheme, and, based on what I've understood, I think that problem and the one I've posed could be related but are not the same. In fact, I believe that secret sharing is only "interesting" when $k>1$. Substituting $k=1$ into most solutions for the secret-sharing schemes I've found do not address conditions 2 & 3 since they are not designed to. $\endgroup$
    – Vincent Tjeng
    May 27, 2012 at 14:50

3 Answers 3

Reset to default
3
$\begingroup$

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."

Improve this answer
$\endgroup$
4
  • $\begingroup$ Hi Federico, I'm not sure how exactly the safe would authenticate the user's private key as being correct. Could you elaborate on this? $\endgroup$
    – Vincent Tjeng
    May 27, 2012 at 14:52
  • 1
    $\begingroup$ Are you familiar with public-key cryptography? en.wikipedia.org/wiki/Public-key_cryptography Essentially, you can use a public/private key pair not only for encrypting messages, but also for signing them and thus identifying the sender in a tamper-proof way. That's how password-less authentication in SSH is handled, for instance. $\endgroup$
    – Federico Poloni
    May 27, 2012 at 18:31
  • $\begingroup$ I was familiar with the encryption aspect of public-key cryptography but not with its application in digital signature schemes! Thanks for pointing me there - I think the solution is simply and works! $\endgroup$
    – Vincent Tjeng
    May 28, 2012 at 13:13
  • $\begingroup$ My pleasure! Unfortunately this solution contains no interesting mathematical ideas though... $\endgroup$
    – Federico Poloni
    May 28, 2012 at 15:32
0
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Hi Aaron, thanks for your suggestion regarding the function $S(x)$, I think it would nicely help to expand a solution for a single individual to multiple individuals in most cases. However, I've read up some of the literature on threshold schemes and am still not sure how the solutions are applicable to my problem. In this problem, only one person's password is required to know everything, so as @max mentioned it's the special case where k=1. Or am I missing something here. $\endgroup$
    – Vincent Tjeng
    May 28, 2012 at 13:20
  • 1
    $\begingroup$ I agree. Threshold schemes are not relevant to your problem although they are very cool en.wikipedia.org/wiki/Secret_sharing. A k=1 threshold scheme is like the front door on most homes. Several people have the same key, any k=1 can do everything. Not what you want. $\endgroup$
    – Aaron Meyerowitz
    May 28, 2012 at 22:29
0
$\begingroup$

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:

Reading through the first 3 chapters or so should give you a feel for the subject.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.