Cryptology ePrint Archive: Report 2021/1687

Computational Irrelevancy: Bridging the Gap between Pseudo- and Real Randomness in MPC Protocols

Nariyasu Heseri and Koji Nuida

Abstract: Due to the fact that classical computers cannot efficiently obtain random numbers, it is common practice to design cryptosystems in terms of real random numbers and then replace them with (cryptographically secure) pseudorandom ones for concrete implementations. However, as pointed out by [Nuida, PKC 2021], this technique may lead to compromise of security in secure multiparty computation (MPC) protocols. Although this work suggests using information-theoretically secure protocols and pseudorandom generators (PRGs) with high min-entropy to alleviate the problem, yet it is preferable to base the security on computational assumptions rather than the stronger information-theoretic ones. By observing that the contrived constructions in the aforementioned work use MPC protocols and PRGs that are closely related to each other, we notice that it may help to alleviate the problem by using protocols and PRGs that are "unrelated" to each other. In this paper, we propose a notion called "computational irrelevancy" to formalise the term "unrelated" and under this condition provide a security guarantee under computational assumptions.

Category / Keywords: foundations / secure multiparty computation, pseudorandom generators, relativisation

Date: received 23 Dec 2021, last revised 20 Jan 2022

Contact author: nariyasu at g ecc u-tokyo ac jp, nuida at imi kyushu-u ac jp

Available format(s): PDF | BibTeX Citation

Version: 20220120:122828 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]