4
$\begingroup$

Is there any known and proven algorithm which allows n-of-m keys en/decryption, but doesn't require the keys to be in one location? That is, it allows the plaintext (or ciphertext) to be encrypted (or decrypted) with one part of the secret, then passed on to another party, until n parties processed it.

Practically I'm looking for a solution to secret sharing where nobody is trusted to hold the complete key - even temporarily. It sounds like an area of homomorphic encryption, but I couldn't find any obvious software / papers.

Edit: The scenario here is: 3 parties: plaintext generator, storage service, extractor.

The only allowed operations are:

  • generator stores an encrypted message, can encrypt together with storage service
  • extractor and storage service together (agreed by offline action) decrypt all messages stored by generator (at this time all messages can be deleted) - extractor learns the plaintext, but storage service must not

Explicitly forbidden scenarios:

  • storage service or extractor decrypting, or encrypting messages individually
  • storage service cannot learn the plaintext when generator is storing then
Improve this question
$\endgroup$
7
  • $\begingroup$ what kind of en/decryption are you thinking? Symmetric or Asymmetric? $\endgroup$
    – mikeazo
    May 7, 2015 at 11:58
  • 1
    $\begingroup$ If " nobody is trusted to hold the complete key " in the question rules out that a trusted party (not among those holding a key share) holds the complete key, it's going to be critical to specify what the complete key is supposed to allow. $\endgroup$
    – fgrieu ♦
    May 7, 2015 at 11:58
  • $\begingroup$ @mikeazo I'm interested in symmetric only. $\endgroup$
    – viraptor
    May 7, 2015 at 12:20
  • 1
    $\begingroup$ Who should get the output of the encryption/decryption operation? $\endgroup$
    – mikeazo
    May 7, 2015 at 12:59
  • 1
    $\begingroup$ For asymmetric crypto this sounds very much like a so called Threshold Encryption scheme en.wikipedia.org/wiki/Threshold_cryptosystem. However, I am not sure such a thing exists for symmetric crypto. $\endgroup$
    – Guut Boy
    May 7, 2015 at 13:23

1 Answer 1

Reset to default
2
$\begingroup$

The way I see it, you have a few options. The right one will depend on the details of the application, which are sparse in the question.

  1. Use a stream cipher (or stream-like mode). Each party has a separate key and encrypts/decrypts with their individual key. With this you only get n-out-of-n, not m-out-of-n where $m<n$.
  2. Use MPC. You can evaluate the AES encryption/decryption circuit via MPC. It is fairly fast based on the numbers I've seen recently. Unfortunately, I don't think there is any good publicly released software out there to do this. Under this paradigm, each party would hold a share of the secret key and they would cooperatively work to do the encryption/decryption. The work I cited requires all n parties, but if the secret were originally shared with an m-out-of-n sharing scheme (like Shamir), you could convert that to an additive sharing (see this paper for a method of doing the conversion).

Some things to think about:

  • Who generates the key initially?
  • Who is suppose to receive the output of the operations?
Improve this answer
$\endgroup$
3
  • $\begingroup$ "Use a stream cipher (...) Each party has a separate key and encrypts/decrypts with their individual key." - Could you list some specific names here? I can't recall any multi-key stream ciphers. Or am I missing something simple? (You're not suggesting individual keks for a master key, right?) $\endgroup$
    – viraptor
    May 7, 2015 at 15:12
  • 2
    $\begingroup$ @viraptor to encrypt with a stream cipher, you use XOR. XOR is commutative and you can do it many times. So for message $m$ you can do $c=m\oplus k_1\oplus k_2$. To decrypt, do $c\oplus k_1 \oplus k_2$ or even $c\oplus k_2\oplus k_1$. $\endgroup$
    – mikeazo
    May 7, 2015 at 15:55
  • $\begingroup$ Obviously! I knew I missed something :-) $\endgroup$
    – viraptor
    May 8, 2015 at 0:21

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.