The universal composability allows one to the analyze security of cryptographic protocols . But it does have some gaps when it comes to analyzing few protocols especially two party cases when there is no honest majority players

Now when it comes to protocols designed for cloud computing, where few parties outsource computations to a service provider. How do we prove the security of such protocols ?

Trivial example is Alice encrypts all her data using FHE schemes and outsources to Sally . Sally should now compute any function on the encrypted data requested by the Alice.

Notice that this simple case is different from two party secure function evaluation.

Now more complex protocols would be when Alice, Bob are two users who wants to execute some function on the shared data outsourced to Sally. So how do we prove security of protocols designed for such functionality?

  • 1
    $\begingroup$ Why is this not obviously equivalent to standard MPC? $\;$ $\endgroup$
    – user991
    Aug 29, 2013 at 19:40
  • $\begingroup$ Well good question, MPC is too pessmestic , no party trusts other. in cloud computing only the server is not trusted . for example: we trust our friends on facebook but not facebook itself ! also in MPC all parties do computation , in CC only server does computation, so computational privacy should be modelled differently. Refer eprint.iacr.org/2013/272 for more such differences $\endgroup$
    – sashank
    Aug 29, 2013 at 22:08
  • 1
    $\begingroup$ It would be helpful if you would specify trust relationships like this in the question, because not always do the two cloud parties trust each other. We also might not trust the cloud to not collude with the other party in all cases. If those are your trust/adversary assumptions, that is fine, but they need to be stated. $\endgroup$
    – mikeazo
    Aug 30, 2013 at 14:04

1 Answer 1


I think it is still possible to use UC in this case.

Recall the setup for the UC framework. We have an ideal world and a real world. There are parties $P_1,\dots,P_n$ in each world and an environment $\mathcal{Z}$ in each. In the real world we have the adversary $\mathcal{A}$ while in the ideal world, we have an ideal functionality $\mathcal{F}$ and a simulator $\mathcal{S}$. In the real world, the parties run some protocol $\pi$ while $\mathcal{F}$ should compute the same functionality as $\pi$ in the ideal world and be secure by definition (basically it is a trusted 3rd party). See the graphic below (taken from Martin Geisler's PhD thesis)

UC framework

So, in your case, you have 3 parties. $P_1=\text{Alice},P_2=\text{Bob},P_3=\text{Sally}$. I'm not going to mess with specifying the protocol $\pi$. In the ideal world we can have a very simple setup. $P_1$ and $P_2$ submit their inputs (in plaintext over a private channel) to $\mathcal{F}$ and $P_3$ issues commands to $\mathcal{F}$ with what to do with those inputs (e.g., "compute the sum", etc).

In the real world $\mathcal{A}$ is basically $P_3$, so we assume that anything $P_3$ knows, $\mathcal{A}$ also knows. That information is then leaked to $\mathcal{Z}$. Then in the ideal world, you'll have to construct $\mathcal{S}$ in such a way that $\mathcal{Z}$ cannot distinguish between the two worlds. How exactly you do this will depend greatly on $\pi$.

As an example, let's say we are just computing the sum of the inputs using Paillier. In $\pi$, $P_1$ and $P_2$ might encrypt their inputs with the Paillier public key (who knows the private key is up to you, but it shouldn't be $P_3$) and send them to $P_3$. Then, if $P_3$ decides to, it will homomorphically sum the values and send the resulting ciphertext back to $P_1$ and $P_2$. To make it general, we'll just let $\mathcal{Z}$ provide $P_1$ and $P_2$ with their inputs and with $P_3$'s choice.

In the ideal world, $P_1$ and $P_2$ pass their inputs (from $\mathcal{Z}$) to $\mathcal{F}$. Then, if $P_3$ tells $\mathcal{F}$ to compute the sum, $\mathcal{F}$ does so. Furthermore, it will leak an encryption (using the paillier public key) of the result to $\mathcal{S}$ who passes that to $\mathcal{Z}$. You can also have $\mathcal{S}$ leak encryptions of the inputs to $\mathcal{Z}$ in a similar manner.

In both worlds, $\mathcal{Z}$ sees encrypted inputs and an encrypted output (if $P_3$ decides to allow the computation). Thus the two worlds are indistinguishable (assuming IND-CPA of the cipher) and the real world is as secure as the ideal world.

  • $\begingroup$ Good start Mike. Intuitively i feel there is some gap , may be in my understanding rather than your explanation. would get back in case more questions $\endgroup$
    – sashank
    Aug 30, 2013 at 23:50
  • $\begingroup$ @mikeazo. Can you give a protocol or a reference where its security is proven under the ideal/real paradigm. I mean to show how this indistinguishability between interaction of real and ideal environments is shown. Like you did but it seems very simplistic. I would expect at some point a reduction to a believed hard problem. For instance how the protocol you provided cannot be secure? Its security doesn't lie whether Paillier is CPA? $\endgroup$
    – curious
    Oct 21, 2013 at 14:49
  • 1
    $\begingroup$ @curious The PHD thesis I link to in the answer has an example. Also, chapter 4 of Ivan Damgard's MPC book has some examples. I do see your point. Typically it will depend on whether or not the cipher is computationally secure or information-theoretically secure. But you are right, for a specific cipher you will take the proven properties and reductions (e.g., ind-cpa assuming quadratic residuosity is hard) to argue the indistinguishability. $\endgroup$
    – mikeazo
    Oct 21, 2013 at 15:28
  • $\begingroup$ @mikeazo so at the end you need a reductionist proof as with game-based proofs...So what's the different? What security definitions conceptually the ideal/real paradigm demonstrates that the game-based proofs does not, if any?To be more specific: Is there any case that even if Paillier is CPA you can end up in an insecure protocol by the security analysis with the ideal/real paradigm? $\endgroup$
    – curious
    Oct 21, 2013 at 17:07
  • 1
    $\begingroup$ @curious, the benefit of this paradigm is in proving complex protocols. Say I have a complex protocol $\pi$ that can be broken up into 3 sub protocols, $\pi_1\circ\pi_2\circ\pi_3$, where $\circ$ is some sort of composition. If I have proved the security of each sub protocol in the UC framework, I can replace them with their ideal functionalities $\mathcal{F}_1,\mathcal{F}_2,\mathcal{F}_3$ in the complex protocol to make proving the complex one easier. I don't believe you get this ability in game-based proofs. $\endgroup$
    – mikeazo
    Oct 21, 2013 at 17:13

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.