Paper 2016/1040

Semi-Honest Secure Multiparty Computation Can Be Insecure by Using Secure Pseudorandom Generators

Koji Nuida

Abstract

It is widely understood that we are just human beings rather than being almighty; hence using ideally random numbers in practice, as supposed in usual theoretical designs of cryptographic protocols, is beyond our ability or at least too expensive. For this point, a standard solution in implementation is to use secure pseudorandom generators (PRGs); ordinary cryptographers' intuition tells that the security of cryptographic protocols should not be lost when applying a secure PRG though no general proof for this is known. In this paper, as opposed to the intuition, we give two examples (under certain, different computational assumptions) of a pair of a secure two-party computation protocol in the semi-honest model (one of which is essentially a practical protocol proposed in ACM CCS 2013, not just an artificially constructed one) and a secure PRG satisfying that the security is lost when the PRG is applied. This phenomenon comes mainly from the fact that, in the security model for two-party protocols the seed for a PRG will be visible by a corrupted party him/herself, while the security notion for PRGs assumes that the seed is not visible. On the other hand, as an affirmative result, we give a sufficient condition for a two-party protocol and a PRG to ensure that the security is preserved when the PRG is applied.

Note: The content has been merged to Report 2018/718