Universal reductions: reductions relative to stateful oracles. (English) Zbl 1519.94079
Kiltz, Eike (ed.) et al., Theory of cryptography. 20th international conference, TCC 2022, Chicago, IL, USA, November 7–10, 2022. Proceedings. Part III. Cham: Springer. Lect. Notes Comput. Sci. 13749, 151-180 (2023).
Summary: We define a framework for analyzing the security of cryptographic protocols that makes minimal assumptions about what a “realistic model of computation is”. In particular, whereas classical models assume that the attacker is a (perhaps non-uniform) probabilistic polynomial-time algorithm, and more recent definitional approaches also consider quantum polynomial-time algorithms, we consider an approach that is more agnostic to what computational model is physically realizable.
Our notion of universal reductions models attackers as PPT algorithms having access to some arbitrary unbounded stateful Nature that cannot be rewound or restarted when queried multiple times. We also consider a more relaxed notion of universal reductions w.r.t. time-evolving, \(k\)-window, Natures that makes restrictions on Nature – roughly speaking, Nature’s behavior may depend on number of messages it has received and the content of the last \(k(\lambda )\)-messages (but not on “older” messages).
We present both impossibility results and general feasibility results for our notions, indicating to what extent the extended Church-Turing hypotheses are needed for a well-founded theory of Cryptography.
For the entire collection see [Zbl 1517.94010].
Our notion of universal reductions models attackers as PPT algorithms having access to some arbitrary unbounded stateful Nature that cannot be rewound or restarted when queried multiple times. We also consider a more relaxed notion of universal reductions w.r.t. time-evolving, \(k\)-window, Natures that makes restrictions on Nature – roughly speaking, Nature’s behavior may depend on number of messages it has received and the content of the last \(k(\lambda )\)-messages (but not on “older” messages).
We present both impossibility results and general feasibility results for our notions, indicating to what extent the extended Church-Turing hypotheses are needed for a well-founded theory of Cryptography.
For the entire collection see [Zbl 1517.94010].
MSC:
| 94A60 | Cryptography |
References:
| [1] | Adcock, M.; Cleve, R.; Alt, H.; Ferreira, A., A quantum Goldreich-Levin Theorem with cryptographic applications, STACS 2002, 323-334 (2002), Heidelberg: Springer, Heidelberg · Zbl 1054.68054 · doi:10.1007/3-540-45841-7_26 |
| [2] | Ambainis, A., Rosmanis, A., Unruh, D.: Quantum attacks on classical proof systems: the hardness of quantum rewinding. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pp. 474-483. IEEE (2014) |
| [3] | Baecher, P.; Brzuska, C.; Fischlin, M.; Sako, K.; Sarkar, P., Notions of black-box reductions, revisited, Advances in Cryptology - ASIACRYPT 2013, 296-315 (2013), Heidelberg: Springer, Heidelberg · Zbl 1327.94029 · doi:10.1007/978-3-642-42033-7_16 |
| [4] | Bitansky, N., Brakerski, Z., Kalai, Y.T.: Constructive post-quantum reductions. IACR Cryptol. ePrint Archive, p. 298 (2022) · Zbl 1527.81038 |
| [5] | Boneh, D.; Dagdelen, Ö.; Fischlin, M.; Lehmann, A.; Schaffner, C.; Zhandry, M.; Lee, DH; Wang, X., Random oracles in a quantum world, Advances in Cryptology - ASIACRYPT 2011, 41-69 (2011), Heidelberg: Springer, Heidelberg · Zbl 1227.94033 · doi:10.1007/978-3-642-25385-0_3 |
| [6] | Barak, B.; Goldreich, O., Universal arguments and their applications, SIAM J. Comput., 38, 5, 1661-1694 (2008) · Zbl 1180.94047 · doi:10.1137/070709244 |
| [7] | Bitansky, N., Shmueli, O.: Post-quantum zero knowledge in constant rounds. In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pp. 269-279 (2020) · Zbl 07298247 |
| [8] | Canetti, R.: Universally composable security: a new paradigm for cryptographic protocols. In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pp. 136-145. IEEE (2001) |
| [9] | Chan, B., Freitag, C., Pass, R.: Universal reductions: Reductions relative to stateful oracles (2022). https://ia.cr/2022/156 · Zbl 1519.94079 |
| [10] | Chiesa, A., Ma, F., Spooner, N., Zhandry, M.: Post-quantum succinct arguments: breaking the quantum rewinding barrier. In: FOCS, pp. 49-58. IEEE (2021) |
| [11] | Dieks, DGBJ, Communication by EPR devices, Phys. Lett. A, 92, 6, 271-272 (1982) · doi:10.1016/0375-9601(82)90084-6 |
| [12] | Dwork, C.; Naor, M., Zaps and their applications, SIAM J. Comput., 36, 6, 1513-1543 (2007) · Zbl 1125.94019 · doi:10.1137/S0097539703426817 |
| [13] | Feige, U., Shamir, A.: Witness indistinguishable and witness hiding protocols. In: Proceedings of the Twenty-second Annual ACM Symposium on Theory of Computing, pp. 416-426 (1990) |
| [14] | Goldreich, O.; Goldwasser, S.; Micali, S., How to construct random functions, J. ACM, 33, 4, 792-807 (1986) · Zbl 0596.65002 · doi:10.1145/6490.6503 |
| [15] | Goldreich, O., Levin, L.A.: A hard-core predicate for all one-way functions. In: Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, pp. 25-32 (1989) |
| [16] | Goldwasser, S.; Micali, S.; Rackoff, C., The knowledge complexity of interactive proof systems, SIAM J. Comput., 18, 1, 186-208 (1989) · Zbl 0677.68062 · doi:10.1137/0218012 |
| [17] | Goldreich, O.; Micali, S.; Wigderson, A., Proofs that yield nothing but their validity for all languages in NP have zero-knowledge proof systems, J. ACM, 38, 3, 691-729 (1991) · Zbl 0799.68101 · doi:10.1145/116825.116852 |
| [18] | Goldreich, O.: Foundations of Cryptography, vol. 1, Basic Tools. Cambridge University Press, Cambridge (2007) · Zbl 1141.94009 |
| [19] | Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing, pp. 212-219 (1996) · Zbl 0922.68044 |
| [20] | Hofheinz, D., Possibility and impossibility results for selective decommitments, J. Cryptol., 24, 3, 470-516 (2011) · Zbl 1258.94038 · doi:10.1007/s00145-010-9066-x |
| [21] | 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, pp. 44-61 1989 (1995) · Zbl 0718.68042 |
| [22] | Lamport, L.: Constructing digital signatures from a one-way function. Technical report (1979) |
| [23] | Lin, H.; Trevisan, L.; Wee, H.; Kilian, J., On hardness amplification of one-way functions, Theory of Cryptography, 34-49 (2005), Heidelberg: Springer, Heidelberg · Zbl 1079.94559 · doi:10.1007/978-3-540-30576-7_3 |
| [24] | Mahadev, U.: Classical verification of quantum computations. In: FOCS, pp. 259-267. IEEE Computer Society (2018) |
| [25] | Maurer, U.; Knudsen, LR, Indistinguishability of random systems, Advances in Cryptology — EUROCRYPT 2002, 110-132 (2002), Heidelberg: Springer, Heidelberg · Zbl 1055.94021 · doi:10.1007/3-540-46035-7_8 |
| [26] | Maurer, U.; Mödersheim, S.; Palamidessi, C., Constructive cryptography – a new paradigm for security definitions and proofs, Theory of Security and Applications, 33-56 (2012), Heidelberg: Springer, Heidelberg · Zbl 1378.94055 · doi:10.1007/978-3-642-27375-9_3 |
| [27] | Maurer, U.; Pietrzak, K.; Naor, M., Composition of random systems: when two weak make one strong, Theory of Cryptography, 410-427 (2004), Heidelberg: Springer, Heidelberg · Zbl 1197.94195 · doi:10.1007/978-3-540-24638-1_23 |
| [28] | Maurer, U.; Pietrzak, K.; Renner, R.; Menezes, A., Indistinguishability amplification, Advances in Cryptology - CRYPTO 2007, 130-149 (2007), Heidelberg: Springer, Heidelberg · Zbl 1215.94062 · doi:10.1007/978-3-540-74143-5_8 |
| [29] | Maurer, U., Renner, R.: Abstract cryptography. In: Innovations in Computer Science, Citeseer (2011) |
| [30] | Naor, M., Bit commitment using pseudorandomness, J. Cryptol., 4, 2, 151-158 (1991) · Zbl 0731.68033 · doi:10.1007/BF00196774 |
| [31] | Popper, K., The Logic of Scientific Discovery (2005), London: Routledge, London · Zbl 0083.24104 · doi:10.4324/9780203994627 |
| [32] | Rogaway, P.; Nguyen, PQ, Formalizing human ignorance, Progress in Cryptology - VIETCRYPT 2006, 211-228 (2006), Heidelberg: Springer, Heidelberg · Zbl 1295.94138 · doi:10.1007/11958239_14 |
| [33] | Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings 35th Annual Symposium on Foundations of Computer Science, pp. 124-134. IEEE (1994) |
| [34] | Unruh, D.; Pointcheval, D.; Johansson, T., Quantum proofs of knowledge, Advances in Cryptology - EUROCRYPT 2012, 135-152 (2012), Heidelberg: Springer, Heidelberg · Zbl 1298.81059 · doi:10.1007/978-3-642-29011-4_10 |
| [35] | Unruh, D.; Fischlin, M.; Coron, J-S, Computationally binding quantum commitments, Advances in Cryptology - EUROCRYPT 2016, 497-527 (2016), Heidelberg: Springer, Heidelberg · Zbl 1371.94660 · doi:10.1007/978-3-662-49896-5_18 |
| [36] | Watrous, J., Zero-knowledge against quantum attacks, SIAM J. Comput., 39, 1, 25-58 (2009) · Zbl 1186.81048 · doi:10.1137/060670997 |
| [37] | Wootters, WK; Zurek, WH, A single quantum cannot be cloned, Nature, 299, 5886, 802-803 (1982) · Zbl 1369.81022 · doi:10.1038/299802a0 |
| [38] | Yao, A.C.: Theory and application of trapdoor functions. In: 23rd Annual Symposium on Foundations of Computer Science (SFCS 1982), pp. 80-91. IEEE (1982) |
| [39] | Zhandry, M.: How to construct quantum random functions. In: FOCS, pp. 679-687. IEEE Computer Society (2012) |
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.
