Computational Irrelevancy: Bridging the Gap Between Pseudo- and Real Randomness in MPC Protocols
Computational Irrelevancy: Bridging the Gap Between Pseudo- and Real Randomness in MPC Protocols
复制标题
计算无关性：弥合 MPC 协议中伪随机性和真实随机性之间的差距
DOI：
10.1007/978-3-031-15255-9_11
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Koji Nuida
中科院分区：
文献类型：
--
作者：
Nariyasu Heseri;Koji Nuida
由于经典计算机无法有效地获取随机数，因此通常的做法是根据真实随机数来设计密码系统，然后将其替换为密码安全的伪随机数来具体实现。然而，正如之前的工作（Nuida，PKC 2021）所指出的，由于伪随机生成器（PRG）的种子在 MPC 上下文中对手可见的特性，该技术可能会导致安全多方计算（MPC）协议的安全性受到损害。尽管这项工作建议使用信息论安全协议（与具有高最小熵的 PRG 一起）来缓解该问题，但最好将安全性基于计算假设而不是更强的信息论假设。通过观察上述工作中的人为构造使用彼此密切相关的 MPC 协议和 PRG，我们注意到使用彼此“不相关”的协议和 PRG 可能有助于缓解问题。在本文中，我们提出了一个称为“计算无关性”的概念来形式化术语“不相关”，并在这种情况下提供计算假设下的安全保证。
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 the previous work (Nuida, PKC 2021), this technique may lead to compromise of security in secure multiparty computation (MPC) protocols, due to the property that a seed for a pseudorandom generator (PRG) is visible by an adversary in the context of MPC. Although this work suggested to use information-theoretically secure protocols (together with 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.