Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

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.

share|improve this question
Does it have to use homomorphic encryption? There are other techniques for multi party computation (garbled circuits and secret sharing based schemes). – mikeazo Jul 18 '12 at 0:47
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 – sashank Jul 18 '12 at 1:31
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. – mikeazo Jul 18 '12 at 1:34
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 ! – sashank Jul 18 '12 at 2:18
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? – mikeazo Jul 18 '12 at 10:02
up vote 6 down vote accepted

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.

share|improve this answer

Your Answer


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

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