1
$\begingroup$

Ok, I'm looking for a way to be able to decrypt ONLY message product and not individual messages. The message product can contain an arbitrary number of messages as long as it's greater than some margin. Probably it's impossible, but I need to make sure.

Suppose it's some weird inverse DKG: you have 5 shares of a public key and can encrypt messages (numbers) using any share. However, you can decrypt only product of messages, that contains at least one message encrypted with each share. However, there is NO escrow key and no possibility to decrypt just one message.

I've been thinking about id-based encryption schemes, but it always seems to have escrow key and allows to decrypt individual messages. Commitments do not work with an arbitrary number (>=5) of messages in a product. Any ideas?

Is it even possible in theory to design such scheme?

I know, the problem is kind of weird, but it bugs me that I can't find a solution or prove that there is no solution at all.

$\endgroup$
  • $\begingroup$ So, you want to share-split the private key right? Because splitting a public key does not make sense. $\endgroup$ – Elias Jan 19 '18 at 11:49
  • $\begingroup$ @Elias, not actually. I want to be able to decrypt ONLY message product and not individual messages. The message product can contain an arbitrary number of messages as long as it's greater than some margin. $\endgroup$ – pintor Jan 19 '18 at 11:53
  • $\begingroup$ @Elias, you are right. The question is confusing. I've changed it. $\endgroup$ – pintor Jan 19 '18 at 11:56
  • 1
    $\begingroup$ So you want functional encryption? en.wikipedia.org/wiki/Functional_encryption $\endgroup$ – Elias Jan 19 '18 at 11:56
  • 1
    $\begingroup$ @Elias, in functional encryption there is always a master secret key, that decrypts every single message. However, I want to make it impossible to decrypt anything if there fewer messages than required. I know, the problem is kind of weird, but it bugs me that I can't find a solution or prove that there is no solution at all. $\endgroup$ – pintor Jan 19 '18 at 13:47
1
$\begingroup$

What's wrong with the obvious solution:

  1. Each party creates a public-private key pair.
  2. The public key is the combination of all public keys.
  3. Encryption is done in a nested fashion to all public keys.
  4. Decryption is done sequentially by all holders of key shares.

If some special property of a symmetric sharing scheme is desired replace the last two with 3. Encryption is done by creating shares according to the symmetric scheme and encrypting each share with a different public key 4. Decryption is performed just as in whatever symmetric sharing scheme was desired

Of course the size of the public key is linear in the number of shares. This is just the obvious solution not a great one.

$\endgroup$
  • $\begingroup$ Well, 1) decryption should be performed by a single entity, 2) you have no idea how many key holders would participate, 3) you should not be able to decrypt a single message, just a product. $\endgroup$ – pintor Jan 19 '18 at 11:59
  • $\begingroup$ Yes, I apparently completely misunderstood what you are asking for. $\endgroup$ – Elias Jan 19 '18 at 12:04
  • $\begingroup$ sorry for the confusion. I hope now the question is more or less clear. I was always thinking about this problem as inverse DKG, which is arguable. $\endgroup$ – pintor Jan 19 '18 at 14:05
  • $\begingroup$ @pintor DKG? Deterministic Key Generation? Daniel Kahn Gillmore? :) $\endgroup$ – Elias Jan 19 '18 at 17:57
  • $\begingroup$ Distributed Key Generation, but never mind. Mmmm Google's first choice is Delta Kappa Gamma :) $\endgroup$ – pintor Jan 22 '18 at 16:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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