Skip to main content
SpringerLink
Log in

Tight Adaptive Reprogramming in the QROM

  • Conference paper
  • First Online:
Advances in Cryptology – ASIACRYPT 2021 (ASIACRYPT 2021)

Part of the book series: Lecture Notes in Computer Science ((LNSC,volume 13090))

Abstract

The random oracle model (ROM) enjoys widespread popularity, mostly because it tends to allow for tight and conceptually simple proofs where provable security in the standard model is elusive or costly. While being the adequate replacement of the ROM in the post-quantum security setting, the quantum-accessible random oracle model (QROM) has thus far failed to provide these advantages in many settings. In this work, we focus on adaptive reprogrammability, a feature of the ROM enabling tight and simple proofs in many settings. We show that the straightforward quantum-accessible generalization of adaptive reprogramming is feasible by proving a bound on the adversarial advantage in distinguishing whether a random oracle has been reprogrammed or not. We show that our bound is tight by providing a matching attack. We go on to demonstrate that our technique recovers the mentioned advantages of the ROM in three QROM applications: 1) We give a tighter proof of security of the message compression routine as used by XMSS. 2) We show that the standard ROM proof of chosen-message security for Fiat-Shamir signatures can be lifted to the QROM, straightforwardly, achieving a tighter reduction than previously known. 3) We give the first QROM proof of security against fault injection and nonce attacks for the hedged Fiat-Shamir transform.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
eBook
USD 84.99
Price excludes VAT (USA)
Softcover Book
USD 109.99
Price excludes VAT (USA)

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    Unless, of course, a standard model proof is available.

  2. 2.

    As a matter of fact, the inapplicability of the history-free reduction from [26], that was used in [16] to give a full reduction for Fiat Shamir signatures (starting with a quantum-extractable identification scheme) was initially overlooked by the Picnic Team. The Picnic team has acknowledged that, and is working on a revision of the Picnic submission to the NIST standardization process for post-quantum cryptographic schemes that will use our reduction.

  3. 3.

    While this increases the signature size, the increase is mild in typical post-quantum Fiat-Shamir based digital signature schemes. As an example, suppose Dilithium-1024x768, which has a signature size of 2044 bytes, had zero commitment entropy (it actually has quite some, see remarks in [26]). To ensure that about \(2^{128}\) hash queries are necessary to make the term in our security bound that depends on the commitment entropy equal 1, about 32 bytes would need to be added, an increase of about 1.6% (assuming \(2^{64}\) signing queries).

  4. 4.

    Intuitively, an identification scheme is called subset-revealing if its responses do not depend on the secret key. Dilithium computes its responses as \(z:= y + c\cdot s_1\), where \(s_1\) is part of the secret key.

  5. 5.

    This is a corrected bound from [23], see discussion in Sect. 2.

  6. 6.

    Note that this basic superposition oracle does not provide an efficient simulation of a quantum-accessible random oracle, which is fine for proving a query lower bound that holds without assumptions about time complexity.

  7. 7.

    This can be seen by employing the Stinespring dilation theorem, or by using standard techniques to delay measurement and discard operations until the end of a quantum algorithm.

  8. 8.

    Note that the partial trace expression yields a positive semidefinite matrix due to the cyclicity of the trace and the fact that is a projector and hence Hermitian.

  9. 9.

    Formally, S, \(\varPi _0\) and \(\varPi _1\) are functions of \(x^*\) but we omit this dependence for simplicity, since we can assume that \(x^*\) is fixed.

References

  1. Abdalla, M., Fouque, P.-A., Lyubashevsky, V., Tibouchi, M.: Tightly-secure signatures from lossy identification schemes. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 572–590. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_34

    Chapter  Google Scholar 

  2. Alagic, G., Majenz, C., Russell, A.: Efficient simulation of random states and random unitaries. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12107, pp. 759–787. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45727-3_26

    Chapter  Google Scholar 

  3. Alagic, G., Majenz, C., Russell, A., Song, F.: Quantum-access-secure message authentication via blind-unforgeability. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12107, pp. 788–817. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45727-3_27

    Chapter  Google Scholar 

  4. Ambainis, A., Hamburg, M., Unruh, D.: Quantum security proofs using semi-classical oracles. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11693, pp. 269–295. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26951-7_10

    Chapter  Google Scholar 

  5. Aranha, D.F., Orlandi, C., Takahashi, A., Zaverucha, G.: Security of hedged Fiat–Shamir signatures under fault attacks. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12105, pp. 644–674. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45721-1_23

    Chapter  Google Scholar 

  6. Beals, R., Buhrman, H., Cleve, R., Mosca, M., Wolf, R.: Quantum lower bounds by polynomials. In: 39th FOCS, pp. 352–361 (1998)

    Google Scholar 

  7. Bindel, N., Hamburg, M., Hövelmanns, K., Hülsing, A., Persichetti, E.: Tighter proofs of CCA security in the quantum random oracle model. In: Hofheinz, D., Rosen, A. (eds.) TCC 2019. LNCS, vol. 11892, pp. 61–90. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-36033-7_3

    Chapter  MATH  Google Scholar 

  8. 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

    Chapter  MATH  Google Scholar 

  9. Bos, J.W., Hülsing, A., Renes, J., van Vredendaal, C.: Rapidly Verifiable XMSS Signatures. Cryptology ePrint Archive, Report 2020/898 (2020). https://eprint.iacr.org/2020/898

  10. Broadbent, A., Lord, S.: Uncloneable quantum encryption via oracles. In: Flammia, S.T. (ed.) TQC 2020, LIPIcs, pp. 4:1–4:22. Dagstuhl, Germany (2020)

    Google Scholar 

  11. Buchmann, J., Dahmen, E., Hülsing, A.: XMSS - a practical forward secure signature scheme based on minimal security assumptions. In: Yang, B.-Y. (ed.) PQCrypto 2011. LNCS, vol. 7071, pp. 117–129. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25405-5_8

    Chapter  Google Scholar 

  12. Chase, M., et al.: Post-quantum zero-knowledge and signatures from symmetric-key primitives. In: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS 2017, pp. 1825–1842. Association for Computing Machinery, New York (2017)

    Google Scholar 

  13. Chen, M.-S., Hülsing, A., Rijneveld, J., Samardjiska, S., Schwabe, P.: From 5-Pass \(\cal{MQ}\)-based identification to \(\cal{MQ}\)-based signatures. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016. LNCS, vol. 10032, pp. 135–165. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53890-6_5

    Chapter  Google Scholar 

  14. Coladangelo, A., Majenz, C., Poremba, A.: Quantum copy-protection of compute-and-compare programs in the quantum random oracle model. arXiv:2009.13865 (2020)

  15. Don, J., Fehr, S., Majenz, C.: The measure-and-reprogram technique 2.0: multi-round Fiat-Shamir and more. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12172, pp. 602–631. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56877-1_21

    Chapter  Google Scholar 

  16. 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. LNCS, vol. 11693, pp. 356–383. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26951-7_13

    Chapter  MATH  Google Scholar 

  17. Eaton, E., Song, F.: Making existential-unforgeable signatures strongly unforgeable in the quantum random-oracle model. In: TQC 2015, LIPIcs (2015)

    Google Scholar 

  18. Fujisaki, E., Okamoto, T.: Secure integration of asymmetric and symmetric encryption schemes. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 537–554. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48405-1_34

    Chapter  Google Scholar 

  19. Fujisaki, E., Okamoto, T.: Secure integration of asymmetric and symmetric encryption schemes. J. Cryptol. 26(1), 80–101 (2013)

    Article  MathSciNet  Google Scholar 

  20. Hofheinz, D., Hövelmanns, K., Kiltz, E.: A modular analysis of the Fujisaki-Okamoto transformation. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017. LNCS, vol. 10677, pp. 341–371. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70500-2_12

    Chapter  MATH  Google Scholar 

  21. Hövelmanns, K., Kiltz, E., Schäge, S., Unruh, D.: Generic authenticated key exchange in the quantum random oracle model. In: Kiayias, A., Kohlweiss, M., Wallden, P., Zikas, V. (eds.) PKC 2020. LNCS, vol. 12111, pp. 389–422. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45388-6_14

    Chapter  Google Scholar 

  22. Hülsing, A., Butin, D., Gazdag, S.-L., Rijneveld, J., Mohaisen, A.: XMSS: Extended Hash-Based Signatures. RFC 8391 (2018)

    Google Scholar 

  23. 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. LNCS, vol. 9614, pp. 387–416. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49384-7_15

    Chapter  Google Scholar 

  24. 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. LNCS, vol. 10993, pp. 96–125. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96878-0_4

    Chapter  Google Scholar 

  25. Jiang, H., Zhang, Z., Ma, Z.: Key encapsulation mechanism with explicit rejection in the quantum random oracle model. In: Lin, D., Sako, K. (eds.) PKC 2019. LNCS, vol. 11443, pp. 618–645. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17259-6_21

    Chapter  Google Scholar 

  26. 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. LNCS, vol. 10822, pp. 552–586. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78372-7_18

    Chapter  MATH  Google Scholar 

  27. Kuchta, V., Sakzad, A., Stehlé, D., Steinfeld, R., Sun, S.-F.: Measure-rewind-measure: tighter quantum random oracle model proofs for one-way to hiding and CCA security. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12107, pp. 703–728. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45727-3_24

    Chapter  Google Scholar 

  28. Liu, Q., Zhandry, M.: Revisiting post-quantum Fiat-Shamir. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11693, pp. 326–355. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26951-7_12

    Chapter  Google Scholar 

  29. Lyubashevsky, V.: Fiat-Shamir with aborts: applications to lattice and factoring-based signatures. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 598–616. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-10366-7_35

    Chapter  Google Scholar 

  30. Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information, 10th Anniversary edn. Cambridge University Press, Cambridge (2010)

    Google Scholar 

  31. NIST. National institute for standards and technology. postquantum crypto project (2017). http://csrc.nist.gov/groups/ST/post-quantum-crypto/

  32. NIST. Status report on the second round of the NIST post-quantum cryptography standardization process. NISTIR 8309 (2020). https://doi.org/10.6028/NIST.IR.8309

  33. 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. LNCS, vol. 10822, pp. 520–551. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78372-7_17

    Chapter  MATH  Google Scholar 

  34. Unruh, D.: Quantum position verification in the random oracle model. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8617, pp. 1–18. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44381-1_1

    Chapter  Google Scholar 

  35. Unruh, D.: Revocable quantum timed-release encryption. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 129–146. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-55220-5_8

    Chapter  Google Scholar 

  36. Unruh, D.: Non-interactive zero-knowledge proofs in the quantum random oracle model. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 755–784. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46803-6_25

    Chapter  MATH  Google Scholar 

  37. Unruh, D.: Post-quantum security of Fiat-Shamir. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10624, pp. 65–95. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70694-8_3

    Chapter  Google Scholar 

  38. Yamakawa, T., Zhandry, M.: A note on separating classical and quantum random oracles. Cryptology ePrint Archive, Report 2020/787 (2020). https://eprint.iacr.org/2020/787

  39. Zhandry, M.: How to record quantum queries, and applications to quantum indifferentiability. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11693, pp. 239–268. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26951-7_9

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Sorbonne Université, CNRS, LIP6, Paris, France

    Alex B. Grilo

  2. Ruhr-Universität Bochum, Bochum, Germany

    Kathrin Hövelmanns

  3. Eindhoven University of Technology, Eindhoven, The Netherlands

    Kathrin Hövelmanns & Andreas Hülsing

  4. Technical University of Denmark, Lyngby, Denmark

    Christian Majenz

  5. Centrum Wiskunde & Informatica and QuSoft, Amsterdam, The Netherlands

    Christian Majenz

Authors
  1. Alex B. Grilo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Kathrin Hövelmanns
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Andreas Hülsing
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Christian Majenz
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to Alex B. Grilo , Kathrin Hövelmanns , Andreas Hülsing or Christian Majenz .

Editor information

Editors and Affiliations

  1. NTT Corporation, Tokyo, Japan

    Mehdi Tibouchi

  2. Nanyang Technological University, Singapore, Singapore

    Huaxiong Wang

Rights and permissions

Reprints and permissions

Copyright information

© 2021 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Grilo, A.B., Hövelmanns, K., Hülsing, A., Majenz, C. (2021). Tight Adaptive Reprogramming in the QROM. In: Tibouchi, M., Wang, H. (eds) Advances in Cryptology – ASIACRYPT 2021. ASIACRYPT 2021. Lecture Notes in Computer Science(), vol 13090. Springer, Cham. https://doi.org/10.1007/978-3-030-92062-3_22

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-92062-3_22

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-92061-6

  • Online ISBN: 978-3-030-92062-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

Search

Navigation