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
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.


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&lt;n$.
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?