Cryptology ePrint Archive: Report 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 \emph{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 \emph{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.

Category / Keywords: foundations / two-party computation, randomness, pseudorandom generator

Date: received 4 Nov 2016, last revised 21 Jul 2018

Contact author: nuida at mist i u-tokyo ac jp

Available format(s): PDF | BibTeX Citation

Version: 20180721:083850 (All versions of this report)

Short URL: ia.cr/2016/1040


[ Cryptology ePrint archive ]