You are looking at a specific version 20170728:103914 of this paper. See the latest version.

Paper 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
two-party computationrandomnesspseudorandom generator
Contact author(s)
k nuida @ aist go jp
History
2021-02-24: withdrawn
2016-11-06: received
See all versions
Short URL
https://ia.cr/2016/1040
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.