Computational irrelevancy: bridging the gap between pseudo- and real randomness in MPC protocols. (English) Zbl 1517.68133
Cheng, Chen-Mou (ed.) et al., Advances in information and computer security. 17th international workshop on security, IWSEC 2022, Tokyo, Japan, August 31 – September 2, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13504, 208-223 (2022).
Summary: 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 [the second author, Lect. Notes Comput. Sci. 12711, 441–468 (2021; Zbl 1517.68135)], 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.
For the entire collection see [Zbl 1503.68013].
For the entire collection see [Zbl 1503.68013].
MSC:
| 68Q10 | Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) |
| 94A60 | Cryptography |
Citations:
Zbl 1517.68135References:
| [1] | Canetti, R.; Goldreich, O.; Halevi, S., The random oracle methodology, revisited, J. ACM, 51, 4, 557-594 (2004) · Zbl 1204.94063 · doi:10.1145/1008731.1008734 |
| [2] | Chor, B., Kushilevitz, E.: A zero-one law for Boolean privacy. In: Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, STOC 1989, New York, NY, USA, pp. 62-72. Association for Computing Machinery (1989) · Zbl 0717.94009 |
| [3] | Dutta, S.; Sakurai, K.; Giri, D.; Ho, ATS; Ponnusamy, S.; Lo, N-W, Theory and application of computationally-independent one-way functions: interactive proof of ability—revisited, Proceedings of the Fifth International Conference on Mathematics and Computing, 97-109 (2021), Singapore: Springer, Singapore · Zbl 07388839 · doi:10.1007/978-981-15-5411-7_7 |
| [4] | Goldreich, O., Foundations of Cryptography (2004), Cambridge: Cambridge University Press, Cambridge · Zbl 1179.94063 · doi:10.1017/CBO9780511721656 |
| [5] | Impagliazzo, R., Rudich, S.: Limits on the provable consequences of one-way permutations. In: Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, STOC 1989, New York, NY, USA, pp. 44-61. Association for Computing Machinery (1989) · Zbl 0718.68042 |
| [6] | Kiltz, E.; Halevi, S.; Rabin, T., Chosen-ciphertext security from tag-based encryption, Theory of Cryptography, 581-600 (2006), Heidelberg: Springer, Heidelberg · Zbl 1113.94008 · doi:10.1007/11681878_30 |
| [7] | Lynn, B.: On the Implementation of Pairing-based Cryptosystems. Ph.D. thesis, Stanford University (2007) |
| [8] | Maurer, U.; Renner, R.; Holenstein, C.; Naor, M., Indifferentiability, impossibility results on reductions, and applications to the random oracle methodology, Theory of Cryptography, 21-39 (2004), Heidelberg: Springer, Heidelberg · Zbl 1197.94196 · doi:10.1007/978-3-540-24638-1_2 |
| [9] | Nuida, K.; Garay, JA, Cryptographic pseudorandom generators can make cryptosystems problematic, Public-Key Cryptography - PKC 2021, 441-468 (2021), Cham: Springer, Cham · Zbl 1517.68135 · doi:10.1007/978-3-030-75248-4_16 |
| [10] | Okamoto, T.; Pointcheval, D.; Kim, K., The gap-problems: a new class of problems for the security of cryptographic schemes, Public Key Cryptography, 104-118 (2001), Heidelberg: Springer, Heidelberg · Zbl 0984.94509 · doi:10.1007/3-540-44586-2_8 |
| [11] | Yao, A.C.: Protocols for secure computations. In: 23rd Annual Symposium on Foundations of Computer Science (SFCS 1982), pp. 160-164 (1982) |
| [12] | Yao, A.C.-C.: How to generate and exchange secrets. In: 27th Annual Symposium on Foundations of Computer Science (SFCS 1986), pp. 162-167 (1986) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
