Cryptology ePrint Archive: Report 2016/1040

Semi-Honest Secure Multiparty Computation Can Be Insecure with Use of Even Almost Uniformly Random Number Generators

Koji Nuida

Abstract: It is widely understood that we are just human beings rather than being almighty; as a result, we have always to rely on \emph{non-ideal} randomness in real-world cryptosystems. In contrast, in a theoretical design of a cryptosystem, it is usually regarded as sufficient to give a security proof assuming the use of \emph{ideal} randomness in the system. This gap between the theory and the real world seems to have not been considered seriously, due to our common beliefs that computationally secure (close-to-ideal) randomness generation must be practically possible and the security of cryptosystems must be preserved when the ideal randomness in theory is replaced by a practical computationally secure pseudorandom generator (PRG). Nevertheless, in this paper we reveal, as opposed to our intuition, that the latter kind of common belief on the security under the use of computationally secure PRGs is NOT true for a general two-party computation protocol. More precisely, we prove as a counterexample that an oblivious transfer protocol proposed by Asharov et al.\ in ACM CCS 2013 in the semi-honest model becomes \emph{insecure} when a party in the protocol uses, to generate his/her internal randomness, an even \emph{statistically} secure PRG constructed in the present paper. Our result implies that, even by using a statistically secure PRG implemented with a best effort by an honest engineer, the security of an implemented two-party protocol is not automatically guaranteed; the author thinks that this fact should be widely recognized in the area of cryptography as well as many other areas where secure multiparty computation is going to be practically applied. It might be an interesting future research topic to study sufficient conditions for two-party protocols that imply the security under a use of a secure PRG, a part of which is also done in this paper.

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

Date: received 4 Nov 2016, last revised 28 Jul 2017

Contact author: k nuida at aist go jp

Available format(s): PDF | BibTeX Citation

Version: 20170728:103914 (All versions of this report)

Short URL: ia.cr/2016/1040

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]