Designing Secure Multi-Party Computation Sub-Protocols Based on Homomorphic Encryption

When designing SMPC protocols using secret-sharing, it is a common approach to compose a protocol from several sub-protocols (each proven secure under the formal definition of security w.r.t. semi-honest or malicious adversaries) by applying the sequential composition theorem. These sub-protocols obtain shared input and provide shared output.

When designing SMPC protocols (independent of a specific framework) using a (semantically secure, probabilistic) homomorphic cryptosystem, e.g., Paillier, it is desirable to modularly compose protocols, too. In order to prevent the leakage of intermediate computation results, usually it is necessary to define sub-protocols in such a way that they get (homomorphically) encrypted input and provide (homomorphically) encrypted output. In some of these sub-protocols, ciphertexts $c$ are computed (e.g., the encrypted result of a multiplication of two encrypted integers) which can not be simulated by generating ciphertext $c’$ of the same plaintext (i.e., $\text{Decrypt}(c) = \text{Decrypt}(c’)$) from simulator's input only. Some authors which propose such kind of sub-protocols let the simulator simulate such ciphertext by an arbitrary ciphertext or a random encryption of $0$ (under the corresponding public key) and refer to the semantic security of the underlying cryptosystem in the corresponding security proof when arguing that the simulated view is computationally indistinguishable from the view of a (real) protocol execution.

The question is whether it is correct to simulate such ciphertext by a random ciphertext or a random encryption of $0$? Since the keys are fixed from beginning (the sub-protocols input are ciphertexts), isn't it possible to give the secret key to the (non-uniform) distinguisher as an extra advice (the only restrictions for the advice is that its bit-length is polynomial in the security parameter), and thus allowing the distinguisher to decrypt? With the ability to decrypt, the distinguisher would be able distinguish between a random ciphertext (or a random encrypted of $0$) in the simulation and a ciphertext of the correct plaintext in the (real) protocol execution.

• Could you please mention some papers that provide security proofs in this way?
– Mhy
Jul 23 '16 at 11:05