# What scheme will allow merging and splitting the result of a function?

I am wondering if it's possible to have a scheme as follows.

Here is the scenario:

• we have a set of objects (e.g. strings) {O1, O2, ..., On}
• we have a set of users {U1, U2, ..., Um}
• each user asks to compute a special function f over a subset of the objects
• we have an intermediate (trusted) component A that must be able to merge requests coming from different users into one single request
• we have a third (untrusted) component B that computes f over the objects contained in the request sent by A
• A must be able to split/derive the result of the function for the request of each user

I am looking for a function f that would satisfy this scheme

All requests and results should be encrypted and no key is shared among users.

A is trusted. B is NOT trusted.

By merge I mean that the resulting request should be a request to compute the union of all the subsets contained in the users' requests.

B must not know which request came from which user.

This scheme does not need to be able to handle arbitrary functions.

Here is a practical example:

There are three users U1, U2 and U3 and a set of objects {O1, O2, O3, O4, O5}

• U1 requests to compute f(O1, O2)
• U2 requests to compute f(O1,O2,O3)
• U3 requests to compute f(O1,O4,O5)
• A receives these three requests and creates a new request to compute f(O1,O2,O3,O4,O5) which is the union of the requests sent by users.
• B computes f(O1,O2,O3,O4,O5)
• A receives f(O1,O2,O3,O4,O5) and somehow is able to derive f(O1, O2) for U1, f(O1,O2,O3) for U2 and f(O1,O4,O5) for U3

Is there any scheme which will allow me to achieve what I explained above?

-
Are A,B or the server trusted? –  figlesquidge Nov 21 '13 at 16:03
@user8911 A is trusted. B is NOT trusted. –  pAkY88 Nov 21 '13 at 16:48
what do you mean by merge? Or what is the security goal of the merge? So that B doesn't know which request came from which user? –  mikeazo Nov 21 '13 at 19:16
Does this need to be able to handle arbitrary functions? $\;$ –  Ricky Demer Nov 21 '13 at 23:56
Oh, I see. You should make this clear in your question. At the end of your question you need to say "I am looking for a function f that would satisfy this scheme". –  occulus Nov 25 '13 at 10:09