# 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? – mikeazo May 7 '15 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 '15 at 11:58
• @mikeazo I'm interested in symmetric only. – viraptor May 7 '15 at 12:20
• Who should get the output of the encryption/decryption operation? – mikeazo May 7 '15 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. – Guut Boy May 7 '15 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$. – mikeazo May 7 '15 at 15:55