Abstract
The random oracle model (ROM) is an idealized model where hash functions are modeled as random functions that are only accessible as oracles. Although the ROM has been used for proving many cryptographic schemes, it has (at least) two problems. First, the ROM does not capture quantum adversaries. Second, it does not capture non-uniform adversaries that perform preprocessings. To deal with these problems, Boneh et al. (Asiacrypt’11) proposed using the quantum ROM (QROM) to argue post-quantum security, and Unruh (CRYPTO’07) proposed the ROM with auxiliary input (ROM-AI) to argue security against preprocessing attacks. However, to the best of our knowledge, no work has dealt with the above two problems simultaneously.
In this paper, we consider a model that we call the QROM with (classical) auxiliary input (QROM-AI) that deals with the above two problems simultaneously and study security of cryptographic primitives in the model. That is, we give security bounds for one-way functions, pseudorandom generators, (post-quantum) pseudorandom functions, and (post-quantum) message authentication codes in the QROM-AI.
We also study security bounds in the presence of quantum auxiliary inputs. In other words, we show a security bound for one-wayness of random permutations (instead of random functions) in the presence of quantum auxiliary inputs. This resolves an open problem posed by Nayebi et al. (QIC’15). In a context of complexity theory, this implies \( \mathsf {NP}\cap \mathsf {coNP} \not \subseteq \mathsf {BQP/qpoly}\) relative to a random permutation oracle, which also answers an open problem posed by Aaronson (ToC’05).
This work was done in part while the first author was conducting an internship program in NTT Secure Platform Laboratories, Japan.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
“pq” stands for “post-quantum”.
- 2.
More precisely, if both S and T are polynomial in the security parameter and (appropriate parts of) domains and ranges of the random oracle are exponentially large then our bounds become negligibly small.
- 3.
They claim that their security bound is \(\widetilde{O}(ST^2/N)\). However, their definition of one-wayness is weaker than ours, and if we use our definition, then the quadratic security loss naturally occurs. See the full version for more detailed discussion.
- 4.
Since the compression lemma works for unbounded-time encoders and decoders, we can assume that the decoder has an unbounded computational power to simulate quantum computations.
- 5.
Since the decoder has unbounded computational power, it can control the randomness for measurements in executions of the quantum algorithm \(\mathcal A\).
- 6.
In the actual proof, we rely on the semi-classical one-way to hiding theorem recently given by Ambainis, Hamburg, and Unruh [AHU19].
- 7.
More precisely, since an auxiliary input cannot depend on x, we consider the partial truth table of \(\mathcal {O}\) that gives the first \(i-1\) bits of \(\mathcal {O}(x)\) for all x as a part of the auxiliary input.
- 8.
Nayebi et al. [NABT15] also studied Yao’s box problem. However, they only considered the worst case, so their result is not applicable for our purpose.
- 9.
Recall that this is a review of the classical case, and thus this condition is well-defined.
- 10.
Though the encoding does not contain the description of G, the decoder can recover it from R.
- 11.
A similar idea was used by Aaronson [Aar05] to show limitations of quantum one-way communication and algorithms with quantum advice.
- 12.
In an actual simulation, the randomness should be approximated by a rational number up to a sufficient precision. We just think of the randomness as a real number for simplicity.
- 13.
Looking ahead, this is used in the proof of Claim 2.
- 14.
Specifically, \(R_2\) consists of independent random coins \(r_2(a,y)\) for each \((a,y) \in [K]\times [M]\) to simulate
.
- 15.
More concretely, \(\varepsilon ^6>CST^2\log ^6 M (1+\log KN)/KN\) for sufficiently large C implies contradiction.
- 16.
Looking ahead, this is used in the proof of Claim 3.
- 17.
References
Aaronson, S.: Limitations of quantum advice and one-way communication. Theory Comput. 1(1), 1–28 (2005)
Ambainis, A., Hamburg, M., Unruh, D.: Quantum security proofs using semi-classical oracles. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019, Part II. LNCS, vol. 11693, pp. 269–295. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26951-7_10
Aaronson, S., Rothblum, G.: Gentle measurement of quantum states and differential privacy. In: STOC 2019, pp. 322–333 (2019)
Boneh, D., Dagdelen, Ö., Fischlin, M., Lehmann, A., Schaffner, C., Zhandry, M.: Random oracles in a quantum world. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 41–69. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25385-0_3
Brassard, G., Hoyer, P., Mosca, M., Tapp, A.: Quantum amplitude amplification and estimation. Quantum Comput. Quantum Inf. 305, 53–74 (2002)
Brassard, G., Høyer, P., Tapp, A.: Quantum cryptanalysis of hash and claw-free functions. SIGACT News 28(2), 14–19 (1997)
Bernstein, D.J., Lange, T.: Non-uniform cracks in the concrete: the power of free precomputation. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013, Part II. LNCS, vol. 8270, pp. 321–340. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-42045-0_17
Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: ACM CCS 1993, pp. 62–73 (1993)
Bellare, M., Rogaway, P.: Optimal asymmetric encryption. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 92–111. Springer, Heidelberg (1995). https://doi.org/10.1007/BFb0053428
Boneh, D., Zhandry, M.: Quantum-secure message authentication codes. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 592–608. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38348-9_35
Czajkowski, J., Groot Bruinderink, L., Hülsing, A., Schaffner, C., Unruh, D.: Post-quantum security of the sponge construction. In: Lange, T., Steinwandt, R. (eds.) PQCrypto 2018. LNCS, vol. 10786, pp. 185–204. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-79063-3_9
Coretti, S., Dodis, Y., Guo, S.: Non-uniform bounds in the random-permutation, ideal-cipher, and generic-group models. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018, Part I. LNCS, vol. 10991, pp. 693–721. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96884-1_23
Coretti, S., Dodis, Y., Guo, S., Steinberger, J.: Random oracles and non-uniformity. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018, Part I. LNCS, vol. 10820, pp. 227–258. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78381-9_9
Corrigan-Gibbs, H., Kogan, D.: The discrete-logarithm problem with preprocessing. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018, Part II. LNCS, vol. 10821, pp. 415–447. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78375-8_14
Don, J., Fehr, S., Majenz, C., Schaffner, C.: Security of the fiat-shamir transformation in the quantum random-oracle model. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019, Part II. LNCS, vol. 11693, pp. 356–383. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26951-7_13
Dodis, Y., Guo, S., Katz, J.: Fixing cracks in the concrete: random oracles with auxiliary input, revisited. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017, Part II. LNCS, vol. 10211, pp. 473–495. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56614-6_16
De, A., Trevisan, L., Tulsiani, M.: Time space tradeoffs for attacks against one-way functions and PRGs. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 649–665. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14623-7_35
Eaton, E., Song, F.: Making existential-unforgeable signatures strongly unforgeable in the quantum random-oracle model. In: TQC 2015, pp. 147–162 (2015). https://eprint.iacr.org/2015/878
Fiat, A., Naor, M.: Rigorous time/space trade-offs for inverting functions. SIAM J. Comput. 29(3), 790–803 (1999)
Gennaro, R., Gertner, Y., Katz, J., Trevisan, L.: Bounds on the efficiency of generic cryptographic constructions. SIAM J. Comput. 35(1), 217–246 (2005)
Grover, L.K.: A fast quantum mechanical algorithm for database search. In: STOC 1996, pp. 212–219 (1996)
Gennaro, R., Trevisan, L.: Lower bounds on the efficiency of generic cryptographic constructions. In: FOCS 2000, pp. 305–313 (2000)
Garg, S., Yuen, H., Zhandry, M.: New security notions and feasibility results for authentication of quantum data. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017, Part II. LNCS, vol. 10402, pp. 342–371. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63715-0_12
Hellman, M.E.: A cryptanalytic time-memory trade-off. IEEE Trans. Inf. Theory 26(4), 401–406 (1980)
Holevo, A.S.: Bounds for the quantity of information transmitted by a quantum communication channel. Probl. Peredachi Informatsii 9(3), 3–11 (1973)
Hosoyamada, A., Yamakawa, T.: Finding collisions in a quantum world: quantum black-box separation of collision-resistance and one-wayness. Cryptology ePrint Archive, Report 2018/1066 (2018)
Hülsing, A., Rijneveld, J., Song, F.: Mitigating multi-target attacks in hash-based signatures. In: Cheng, C.-M., Chung, K.-M., Persiano, G., Yang, B.-Y. (eds.) PKC 2016, Part I. LNCS, vol. 9614, pp. 387–416. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49384-7_15
Jiang, H., Zhang, Z., Chen, L., Wang, H., Ma, Z.: IND-CCA-secure key encapsulation mechanism in the quantum random oracle model, revisited. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018, Part III. LNCS, vol. 10993, pp. 96–125. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96878-0_4
Kiltz, E., Lyubashevsky, V., Schaffner, C.: A concrete treatment of fiat-shamir signatures in the quantum random-oracle model. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018, Part III. LNCS, vol. 10822, pp. 552–586. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78372-7_18
Katsumata, S., Yamada, S., Yamakawa, T.: Tighter security proofs for GPV-IBE in the quantum random oracle model. In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018, Part II. LNCS, vol. 11273, pp. 253–282. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03329-3_9
Liu, Q., Zhandry, M.: Revisiting post-quantum fiat-shamir. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019, Part II. LNCS, vol. 11693, pp. 326–355. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26951-7_12
Nayebi, A., Aaronson, S., Belovs, A., Trevisan, L.: Quantum lower bound for inverting a permutation with advice. Quantum Inf. Comput. 15(11–12), 901–913 (2015)
Nayak, A.: Optimal lower bounds for quantum automata and random access codes. In: FOCS 1999, pp. 369–376 (1999)
Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information, vol. 2. Cambridge University Press, Cambridge (2000)
Nayak, A., Salzman, J.: Limits on the ability of quantum states to convey classical messages. J. ACM 53(1), 184–206 (2006)
Nishimura, H., Yamakami, T.: Polynomial time quantum computation with advice. Inf. Process. Lett. 90(4), 195–204 (2004)
Saito, T., Xagawa, K., Yamakawa, T.: Tightly-secure key-encapsulation mechanism in the quantum random oracle model. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018, Part III. LNCS, vol. 10822, pp. 520–551. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78372-7_17
Targhi, E.E., Unruh, D.: Post-quantum security of the fujisaki-okamoto and OAEP transforms. In: Hirt, M., Smith, A. (eds.) TCC 2016, Part II. LNCS, vol. 9986, pp. 192–216. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53644-5_8
Unruh, D.: Random oracles and auxiliary input. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 205–223. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74143-5_12
Unruh, D.: Non-interactive zero-knowledge proofs in the quantum random oracle model. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015, Part II. LNCS, vol. 9057, pp. 755–784. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46803-6_25
Winter, A.: Coding theorem and strong converse for quantum channels. IEEE Trans. Inf. Theory 45(7), 2481–2485 (1999)
Yao, A.C.-C.: Theory and applications of trapdoor functions. In: FOCS 1982, pp. 80–91 (1982)
Yao, A.C.-C.: Coherent functions and program checkers. In: STOC 1990, pp. 84–94 (1990)
Zhandry, M.: How to construct quantum random functions. In: FOCS 2012, pp. 679–687 (2012)
Zhandry, M.: Secure identity-based encryption in the quantum random oracle model. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 758–775. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32009-5_44
Acknowledgment
We thank anonymous reviewers of Asiacrypt 2019 and Andreas Hülsing for their helpful comments. Minki Hhan was partially supported by the Institute for Information & Communications Technology Promotion (IITP) Grant through the Korean Government (MSIT), (Development of lattice-based post-quantum public-key cryptographic schemes), under Grant 2017-0-00616 and by the Samsung Research Funding Center of Samsung Electronics under Project SRFC-TB1403-52.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 International Association for Cryptologic Research
About this paper
Cite this paper
Hhan, M., Xagawa, K., Yamakawa, T. (2019). Quantum Random Oracle Model with Auxiliary Input. In: Galbraith, S., Moriai, S. (eds) Advances in Cryptology – ASIACRYPT 2019. ASIACRYPT 2019. Lecture Notes in Computer Science(), vol 11921. Springer, Cham. https://doi.org/10.1007/978-3-030-34578-5_21
Download citation
DOI: https://doi.org/10.1007/978-3-030-34578-5_21
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-34577-8
Online ISBN: 978-3-030-34578-5
eBook Packages: Computer ScienceComputer Science (R0)