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.

Improve this question
$\endgroup$
9
  • $\begingroup$ So, you want to share-split the private key right? Because splitting a public key does not make sense. $\endgroup$
    – Elias
    Jan 19, 2018 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, 2018 at 11:53
  • $\begingroup$ @Elias, you are right. The question is confusing. I've changed it. $\endgroup$
    – pintor
    Jan 19, 2018 at 11:56
  • 1
    $\begingroup$ So you want functional encryption? en.wikipedia.org/wiki/Functional_encryption $\endgroup$
    – Elias
    Jan 19, 2018 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, 2018 at 13:47

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
5
  • $\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, 2018 at 11:59
  • $\begingroup$ Yes, I apparently completely misunderstood what you are asking for. $\endgroup$
    – Elias
    Jan 19, 2018 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, 2018 at 14:05
  • $\begingroup$ @pintor DKG? Deterministic Key Generation? Daniel Kahn Gillmore? :) $\endgroup$
    – Elias
    Jan 19, 2018 at 17:57
  • $\begingroup$ Distributed Key Generation, but never mind. Mmmm Google's first choice is Delta Kappa Gamma :) $\endgroup$
    – pintor
    Jan 22, 2018 at 16:08

Your Answer

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

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