6
$\begingroup$

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.

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

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 bitlength is polynomial in the security parameter), and thus allowing the distinguisher to decrypt?

This is up to your security model. For example in a protocol that is designed to provide forward secrecy, yes, you would need a method in the proof that allows the adversary to get the private key. After that, they would be able to distinguish between encryptions of 0 and the real encryptions, so something else must be done in the proof to handle this situation. Look around for examples of composability proofs in the forward secrecy model for guidance on how to do this.

If, on the other hand, your security model is not designed to handle key leakage, then you don't really have to handle it in the proof since that is impossible in both the simulation and the "real" protocol execution.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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