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, when utilizing cryptographic technology in practice, we have always to rely on imperfect randomness to various extent. For ordinary cryptography (e.g., encryption), if a person misuses a random number generator (e.g., generating a vulnerable ciphertext), then the person him/herself will suffer the damage caused by the misuse (e.g., leakage of his/her sensitive plaintext). In contrast, in this paper we give \emph{a concrete example} of the following serious situation for multiparty (in particular, two-party) computation in the semi-honest model: Imagine that a party replaces the party's (uniform and independent) internal random tape with an output of some random function. Then, even if the original two-party protocol is \emph{statistically} (i.e., almost perfectly) secure and the output of the random function is \emph{statistically} (i.e., almost perfectly) indistinguishable from uniform, \emph{it may still happen} that the party with the replaced random tape can now get \emph{the other party's secret input}. Due to the unavoidable imperfect randomness mentioned above, statistical indistinguishability would be the \lq\lq best possible'' quality of the random tape in practice, but then, our example may mean that the semi-honest security alone of a two-party protocol can guarantee nothing about security for a party's input in real situations. A technical remark is that, the output of the random function in our example depends also on the party's input for our two-party protocol. But the author thinks that the true reason of such a paradoxical phenomenon is at another point. Namely, there is a famous \lq\lq clever'' technique for security proofs of two-party protocols, where a simulator for a party's view emulates a transcript during the protocol first, and then emulates the party's random tape depending consistently on the transcript. This is actually in the opposite order from real, where the transcript does depend on the random tape; and, in fact, we prove that such a problem caused by \lq\lq manipulated'' random tapes is prevented (at least under the two conditions for statistical security mentioned above) \emph{provided the simulator in the original security proof is constructed without this \lq\lq order-reversing'' technique}, even if the output of the random function still depends on the party's local input.