# Algorithm for n-of-m keys with partial results

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
• what kind of en/decryption are you thinking? Symmetric or Asymmetric? May 7, 2015 at 11:58
• 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.
– fgrieu
May 7, 2015 at 11:58
• @mikeazo I'm interested in symmetric only. May 7, 2015 at 12:20
• Who should get the output of the encryption/decryption operation? May 7, 2015 at 12:59
• 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. May 7, 2015 at 13:23

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$.
• @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$. May 7, 2015 at 15:55