SCIS 2022
2022 Symposium on
Cryptography and Information Security
Osaka, Japan & Online, Jan. 18 – 21, 2022
The Institute of Electronics,
Information and Communication Engineers

Copyright ©2022 The Institute of Electronics,
Information and Communication Engineers

Computational Irrelevancy: Bridging the Gap between Pseudo- andReal Randomness in MPC Protocols
Nariyasu Heseri ∗Koji Nuida †Keywords: secure multiparty computation, MPC, pseudorandom generators, PRG, relativisation

Abstract

Definition 2. Let π be an n-party protocol that issecure against Pi with simulator S. We say S is withraw randomness if ∃T ∈ PPT , s.t. ∀λ ∈ N,

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 (cryptographicallysecure) pseudorandom ones for concrete implementations.
However, as pointed out by [1], this technique maylead to compromise of security in secure multiparty
computation (MPC) protocols. Although this worksuggests using information-theoretically secure protocols and pseudorandom generators (PRGs) with highmin-entropy to alleviate the problem, yet it is preferable to base the security on computational assumptions
rather than the stronger information-theoretical ones.
By observing that the contrived constructions in theaforementioned work use MPC protocols and PRGs
that are closely related to each other, we notice thatit 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 ”computationalirrelevancy” to formalise the term ”unrelated” and under this condition provide a security guarantee undercomputational assumptions.

S(1λ , xi , fi (~x); ri , τi ) = ri , T (1λ , xi , fi (~x), ri ; τi )where the notation hri , yi means that components ofthe tuple (ri , y) are rearranged such that ri corresponds
to the simulated random tape part.
Theorem 3. Let π be an n-party protocol. Let R be a
PRG and IR be its inverter. For i ∈ {1, 2, . . . , n}, if• π is secure against party Pi relative to IR withraw randomness.
• 1 (λ) := |range(R,λ)|is noticeable.
2lout (λ)• R is non-uniformly indistinguishable in its range
relative to IR , i.e. any N UPPT algorithm cannot distinguish between the output of R and theuniform distribution over the range of R’s output
even given oracle access to IR .
then π ◦i R is secure against party Pi relative to IRwith raw randomness.
In this abstract, we only presented the result for themodel of 1 adversary using a PRG, while similar results
can be shown for 1 adversary with several PRGs used aswell as for multiple colluding adversaries with multiple
PRGs. For these results, in addition to the assumptionthat the protocol itself is computationally irrelevant tothe PRGs used, we also added assumptions that PRGs
are pairwise irrelevant or overall irrelevant respectively.
We refer the reader to the full version of this paper for
more detail.

Main Theorems
Definition 1. Let π be an n-party protocol. We say
π is secure against party Pi relative to O = {Oi }i∈I ⊂PT M if ∃S ∈ PPT s.t. ∀D ∈ N UPPT ,hiPr DO S(1λ , xi , fi (~x)), f~(~x) = 1− Pr DO xi , ri , m~ i (1λ , ~x; ~r), π(1λ , ~x; ~r) = 1

References

is negligible where DO means D is given oracle accessto all Oi .

[1] Koji Nuida. “Cryptographic Pseudorandom Generators Can Make Cryptosystems Problematic”. In:
Public-Key Cryptography – PKC 2021. Ed. by Juan
A. Garay. Cham: Springer International Publishing, 2021, pp. 441–468. isbn: 978-3-030-75248-4.

∗ Graduate School of Information Science and Technology, The

University of Tokyo, nariyasu@g.ecc.u-tokyo.ac.jp† Kyushu University / AIST, nuida@imi.kyushu-u.ac.jp1