[Cryptography] Factorable encryption

[Jerry Leichter]

The recent discussion of "data in use" and how to protect it led me to some speculations.  I'd be curious if anyone has seen anything like it before, and whether any practical algorithms are known.

The idea is to split a computation similarly to the way one splits a secret into shares.  Suppose we have some cleartext C, encrypted to produce E.  We wish to produce the encryption of f(C) for some function of C, but without revealing C to the element that computes f.  Of course, homomorphic encryption is one way to do this, but the known algorithms are too expensive to be practical.

So suppose we could instead split E into n pieces, E1 ... En, and also split f into n pieces f1 ... fn; and also have a combiner g; such that

   g(f1(E1), f2(E2), ..., fn(En)) == Encryption(f(C))

Here's an (insecure) example of how this might work.  Suppose C is a string, the encryption is a stream cipher, but applied in an unusual way:  It's used with two keys, Ke and Ko, where the stream generated by Ke (Ko) is used to encrypt the characters at even (odd) positions in C.  T is a target string, and f(C) is the vector of all indices within C where T can be found.  We produce two splits of E, Eo and Ee, each consisting of every other character, Eo being those characters at odd positions, and Ee of those at even positions.  fe (fo) have access to Ke (Ko) and look for matches at alternating positions within T - starting from the first and second position within Ee or Eo.  Finally, g stitches together matches that actually overlap fully.  (f() returned the actual vector of results, not its encryption, so the split computation does so in the output of g() as well.  The doesn't seem to be a significant limitation.)

One can extend this, but using four splits, to similarly ensure that no one computation element has access to T either.  Or one can use more splits, looking at every k'th character.

Obviously, a very artificial example - and even then its security is limited.  Still, in illustrates that something of this sort might, in principle, be possible given suitable restrictions on the encryption used and the function to be computed.

So ... anything out there?  Any ideas about how to proceed?

                                                        -- Jerry