Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.