The classic multiparty computation protocols are defined around " Untrusted parties trying to compute something together".

But is there a cryptographic abstraction for, "Trusted parties trying to compute together in presence of untrusted server"?

Basically, I am looking for something like multi-player homomorphic encryption for cloud based services. Current homomorphic encryption schemes are two player setup (just a client and server), where client wants to outsource her computation to an untrusted server , but this abstraction does not stretch for most of the cloud based applications, say privacy preserving Facebook or tax processing cloud application where multiple people are involved using a cloud server.

There is a surge in research of functional encryption and its variants (IBE,PBE,ABE, etc.), but they reveal the end-result in plain text.

  • 1
    $\begingroup$ Does it have to use homomorphic encryption? There are other techniques for multi party computation (garbled circuits and secret sharing based schemes). $\endgroup$
    – mikeazo
    Jul 18, 2012 at 0:47
  • $\begingroup$ Well, all of smc are about "untrusted parties trying to compute something" but what i have mentioned is "trusted parties trying to compute something in presence of untrusted server" there is a difference ! For example : i trust my friends but wont trust facebook , i trust my insurer but not amazon's server where health records being processed, hope u got it ! but in SMC , the participating parties wont trust each other in contrary $\endgroup$
    – sashank
    Jul 18, 2012 at 1:31
  • $\begingroup$ But does the server trust the other parties? Typically no, which is why you need something secure in the malicious model; to protect the server. $\endgroup$
    – mikeazo
    Jul 18, 2012 at 1:34
  • $\begingroup$ ok for now , iam not worried about bidirectional privacy,I dont care for server privacy, there are economical reasons for that , if the revenue is through advertisements (posed by reading our mail ) the service is free but if its pay service all the server needs to do is blind computation , it need not know what its doing in a truely outsourced computation ! $\endgroup$
    – sashank
    Jul 18, 2012 at 2:18
  • $\begingroup$ Ok, so clearly a multi-party computation in the malicious model meets your needs, but it seems like you are trying to get some performance gains by relaxing the requirements. Correct? $\endgroup$
    – mikeazo
    Jul 18, 2012 at 10:02

1 Answer 1


There are roughly two common techniques for multi-party computation, garbled circuits and secret sharing. Either may work for your situation, so I've detailed some info and recommendations about each below.

Garbled Circuits
GC is most often applied to the 2 party case. It can be made to be secure against malicious adversaries and can be fairly efficient (a single execution of AES in 1 sec on a massively parallel machine). Against a semi-honest (or honest-but-curious) adversary, a single execution of AES takes about 0.2 seconds (this is on a single thread/process).

Secret Sharing
There are many secret sharing based protocols out there. They typically aim for as many parties as desired (with a cost of extra communication & computation per party). They also can be made to work in the malicious model. Any secret sharing technique can theoretically be used, but the most efficient protocols have used (somewhat) homomorphic encryption.

The SPDZ protocol was recently used to compute an execution of AES in less than half a second with up to 10 parties. The timing result only takes into account the online phase. There is a preprocessing phase which takes more time (haven't been able to find exact numbers), but still appears to be manageable.

Fully Homomorphic Encryption
Fully-homomorphic encryption can easily be used to compute on encrypted data, in the malicious model. But, it comes with its tradeoffs. The communication complexity is much less than any of the other protocols, but (currently) the computation complexities are too large to be practical. For example, homomorphic evaluation of AES was shown to take a few days using the best of the best available FHE systems.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.