On the Efficiency of Generic, Quantum Cryptographic Constructions

Keita Xagawa

doi:10.62056/a66c0l5vt

On the Efficiency of Generic, Quantum Cryptographic Constructions

Authors

Keita Xagawa

Technology Innovation Institute, Abu Dhabi, United Arab Emirates
keita dot xagawa at tii dot ae

Keywords: Quantum reduction black-box construction efficiency

Abstract

One of the central questions in cryptology is how efficient generic constructions of cryptographic primitives can be. Gennaro, Gertner, Katz, and Trevisan [SIAM J. of Compt., 2005] studied the lower bounds of the number of invocations of a (trapdoor) one-way permutation in order to construct cryptographic schemes, e.g., pseudorandom number generators, digital signatures, and public-key and symmetric-key encryption.

Recently, quantum machines have been explored to _construct_ cryptographic primitives other than quantum key distribution. This paper studies the efficiency of _quantum_ black-box constructions of cryptographic primitives when the communications are _classical_. Following Gennaro et al., we give the lower bounds of the number of invocations of an underlying quantumly-computable quantum-one-way permutation when the _quantum_ construction of pseudorandom number generator and symmetric-key encryption is weakly black-box. Our results show that the quantum black-box constructions of pseudorandom number generator and symmetric-key encryption do not improve the number of invocations of an underlying quantumly-computable quantum-one-way permutation.

References

[AC02]

Mark Adcock and Richard Cleve. A quantum goldreich-levin theorem with cryptographic applications. In Helmut Alt and Afonso Ferreira, editors, STACS 2002, volume 2285 of LNCS, 323–334. Springer, Heidelberg, February 2002. https://doi.org/10.1007/3-540-45841-7_26.

Google Scholar ePrint

[ACC⁺22]

Per Austrin, Hao Chung, Kai-Min Chung, Shiuan Fu, Yao-Ting Lin, and Mohammad Mahmoody. On the impossibility of key agreements from quantum random oracles. In Yevgeniy Dodis and Thomas Shrimpton, editors, CRYPTO 2022, Part II, volume 13508 of LNCS, 165–194. August 2022. Springer, Heidelberg. https://doi.org/10.1007/978-3-031-15979-4_6.

Google Scholar ePrint

[AGQY22]

Prabhanjan Ananth, Aditya Gulati, Luowen Qian, and Henry Yuen. Pseudorandom (function-like) quantum state generators: new definitions and applications. In Eike Kiltz and Vinod Vaikuntanathan, editors, TCC 2022, Part I, volume 13747 of LNCS, 237–265. November 2022. Springer, Heidelberg. https://doi.org/10.1007/978-3-031-22318-1_9.

Google Scholar ePrint

[AIK22]

Scott Aaronson, DeVon Ingram, and William Kretschmer. The acrobatics of BQP. In Shachar Lovett, editor, CCC 2022, volume 234 of LIPIcs, 20:1–20:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. https://doi.org/10.4230/LIPIcs.CCC.2022.20.

Google Scholar ePrint

[Amb02]

Andris Ambainis. Quantum lower bounds by quantum arguments. J. Comput. Syst. Sci., 64(4):750–767, 2002. https://doi.org/10.1006/JCSS.2002.1826.

Google Scholar ePrint

[AQY22]

Prabhanjan Ananth, Luowen Qian, and Henry Yuen. Cryptography from pseudorandom quantum states. In Yevgeniy Dodis and Thomas Shrimpton, editors, CRYPTO 2022, Part I, volume 13507 of LNCS, 208–236. August 2022. Springer, Heidelberg. https://doi.org/10.1007/978-3-031-15802-5_8.

Google Scholar ePrint

[BCKM21a]

James Bartusek, Andrea Coladangelo, Dakshita Khurana, and Fermi Ma. On the round complexity of secure quantum computation. In Tal Malkin and Chris Peikert, editors, CRYPTO 2021, Part I, volume 12825 of LNCS, 406–435. Virtual Event, August 2021. Springer, Heidelberg. https://doi.org/10.1007/978-3-030-84242-0_15.

Google Scholar ePrint

[BCKM21b]

James Bartusek, Andrea Coladangelo, Dakshita Khurana, and Fermi Ma. One-way functions imply secure computation in a quantum world. In Tal Malkin and Chris Peikert, editors, CRYPTO 2021, Part I, volume 12825 of LNCS, 467–496. Virtual Event, August 2021. Springer, Heidelberg. https://doi.org/10.1007/978-3-030-84242-0_17.

Google Scholar ePrint

[BHMT00]

Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. In Quantum Computation and Information, volume 305 of Contemporary Mathematics, pages 53–74. AMS, 2000. https://doi.org/10.1090/conm/305/05215.

Google Scholar ePrint

[BI20]

Anne Broadbent and Rabib Islam. Quantum encryption with certified deletion. In Rafael Pass and Krzysztof Pietrzak, editors, TCC 2020, Part III, volume 12552 of LNCS, 92–122. November 2020. Springer, Heidelberg. https://doi.org/10.1007/978-3-030-64381-2_4.

Google Scholar ePrint

[BT06]

Andrej Bogdanov and Luca Trevisan. Average-case complexity. Foundations and Trends® in Theoretical Computer Science, 2(1):1–106, 2006. https://doi.org/10.1561/0400000004.

Google Scholar ePrint

[CGLQ20]

Kai-Min Chung, Siyao Guo, Qipeng Liu, and Luowen Qian. Tight quantum time-space tradeoffs for function inversion. In 61st FOCS, 673–684. November 2020. IEEE Computer Society Press. https://doi.org/10.1109/FOCS46700.2020.00068.

Google Scholar ePrint

[CLM23]

Kai-Min Chung, Yao-Ting Lin, and Mohammad Mahmoody. Black-box separations for non-interactive classical commitments in a quantum world. In Carmit Hazay and Martijn Stam, editors, EUROCRYPT 2023, Part I, volume 14004 of LNCS, 144–172. April 2023. Springer, Heidelberg. https://doi.org/10.1007/978-3-031-30545-0_6.

Google Scholar ePrint

[CLQ20]

Kai-Min Chung, Tai-Ning Liao, and Luowen Qian. Lower bounds for function inversion with quantum advice. In Yael Tauman Kalai, Adam D. Smith, and Daniel Wichs, editors, ITC 2020, volume, 8:1–8:15. June 2020. Schloss Dagstuhl. https://doi.org/10.4230/LIPIcs.ITC.2020.8.

Google Scholar ePrint

[DTT10]

Anindya De, Luca Trevisan, and Madhur Tulsiani. Time space tradeoffs for attacks against one-way functions and PRGs. In Tal Rabin, editor, CRYPTO 2010, volume 6223 of LNCS, 649–665. August 2010. Springer, Heidelberg. https://doi.org/10.1007/978-3-642-14623-7_35.

Google Scholar ePrint

[Gen10]

Craig Gentry. Toward basing fully homomorphic encryption on worst-case hardness. In Tal Rabin, editor, CRYPTO 2010, volume 6223 of LNCS, 116–137. August 2010. Springer, Heidelberg. https://doi.org/10.1007/978-3-642-14623-7_7.

Google Scholar ePrint

[GGK03]

Rosario Gennaro, Yael Gertner, and Jonathan Katz. Lower bounds on the efficiency of encryption and digital signature schemes. In 35th ACM STOC, 417–425. June 2003. ACM Press. https://doi.org/10.1145/780542.780604.

Google Scholar ePrint

[GGKT05]

Rosario Gennaro, Yael Gertner, Jonathan Katz, and Luca Trevisan. Bounds on the efficiency of generic cryptographic constructions. SIAM Journal on Computing, 35(1):217–246, 2005. https://doi.org/10.1137/S0097539704443276.

Google Scholar ePrint

[GL89]

Oded Goldreich and Leonid A. Levin. A hard-core predicate for all one-way functions. In 21st ACM STOC, 25–32. May 1989. ACM Press. https://doi.org/10.1145/73007.73010.

Google Scholar ePrint

[GLSV21]

Alex B. Grilo, Huijia Lin, Fang Song, and Vinod Vaikuntanathan. Oblivious transfer is in MiniQCrypt. In Anne Canteaut and François-Xavier Standaert, editors, EUROCRYPT 2021, Part II, volume 12697 of LNCS, 531–561. October 2021. Springer, Heidelberg. https://doi.org/10.1007/978-3-030-77886-6_18.

Google Scholar ePrint

[GT00]

Rosario Gennaro and Luca Trevisan. Lower bounds on the efficiency of generic cryptographic constructions. In 41st FOCS, 305–313. November 2000. IEEE Computer Society Press. https://doi.org/10.1109/SFCS.2000.892119.

Google Scholar ePrint

[HMNY21]

Taiga Hiroka, Tomoyuki Morimae, Ryo Nishimaki, and Takashi Yamakawa. Quantum encryption with certified deletion, revisited: public key, attribute-based, and classical communication. In Mehdi Tibouchi and Huaxiong Wang, editors, ASIACRYPT 2021, Part I, volume 13090 of LNCS, 606–636. December 2021. Springer, Heidelberg. https://doi.org/10.1007/978-3-030-92062-3_21.

Google Scholar ePrint

[HS12]

Thomas Holenstein and Makrand Sinha. Constructing a pseudorandom generator requires an almost linear number of calls. In 53rd FOCS, 698–707. October 2012. IEEE Computer Society Press. https://doi.org/10.1109/FOCS.2012.51.

Google Scholar ePrint

[HXY19]

Minki Hhan, Keita Xagawa, and Takashi Yamakawa. Quantum random oracle model with auxiliary input. In Steven D. Galbraith and Shiho Moriai, editors, ASIACRYPT 2019, Part I, volume 11921 of LNCS, 584–614. December 2019. Springer, Heidelberg. https://doi.org/10.1007/978-3-030-34578-5_21.

Google Scholar ePrint

[HY20]

Akinori Hosoyamada and Takashi Yamakawa. Finding collisions in a quantum world: quantum black-box separation of collision-resistance and one-wayness. In Shiho Moriai and Huaxiong Wang, editors, ASIACRYPT 2020, Part I, volume 12491 of LNCS, 3–32. December 2020. Springer, Heidelberg. https://doi.org/10.1007/978-3-030-64837-4_1.

Google Scholar ePrint

[IL89]

Russell Impagliazzo and Michael Luby. One-way functions are essential for complexity based cryptography (extended abstract). In 30th FOCS, 230–235. October / November 1989. IEEE Computer Society Press. https://doi.org/10.1109/SFCS.1989.63483.

Google Scholar ePrint

[Imp95]

Russell Impagliazzo. Hard-core distributions for somewhat hard problems. In 36th FOCS, 538–545. October 1995. IEEE Computer Society Press. https://doi.org/10.1109/SFCS.1995.492584.

Google Scholar ePrint

[JLS18]

Zhengfeng Ji, Yi-Kai Liu, and Fang Song. Pseudorandom quantum states. In Hovav Shacham and Alexandra Boldyreva, editors, CRYPTO 2018, Part III, volume 10993 of LNCS, 126–152. August 2018. Springer, Heidelberg. https://doi.org/10.1007/978-3-319-96878-0_5.

Google Scholar ePrint

[KL20]

Jonathan Katz and Yehuda Lindell. Introduction to Modern Cryptography. Chapman & Hall/CRC, third edition, 2020.

Google Scholar ePrint

[KQST23]

William Kretschmer, Luowen Qian, Makrand Sinha, and Avishay Tal. Quantum cryptography in algorithmica. In Barna Saha and Rocco A. Servedio, editors, STOC 2023, 1589–1602. ACM, 2023. https://doi.org/10.1145/3564246.3585225.

Google Scholar ePrint

[Kre21]

William Kretschmer. Quantum Pseudorandomness and Classical Complexity. In Min-Hsiu Hsieh, editor, 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021), volume 197 of Leibniz International Proceedings in Informatics (LIPIcs), 2:1–2:20. Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.TQC.2021.2.

Google Scholar ePrint

[KST99]

Jeong Han Kim, Daniel R. Simon, and Prasad Tetali. Limits on the efficiency of one-way permutation-based hash functions. In 40th FOCS, 535–542. October 1999. IEEE Computer Society Press. https://doi.org/10.1109/SFFCS.1999.814627.

Google Scholar ePrint

[KY10]

Akinori Kawachi and Tomoyuki Yamakami. Quantum hardcore functions by complexity-theoretical quantum list decoding. SIAM Journal on Computing, 39(7):2941–2969, 2010. https://doi.org/10.1137/080716840.

Google Scholar ePrint

[Liu23]

Qipeng Liu. Non-uniformity and quantum advice in the quantum random oracle model. In Carmit Hazay and Martijn Stam, editors, EUROCRYPT 2023, Part I, volume 14004 of LNCS, 117–143. April 2023. Springer, Heidelberg. https://doi.org/10.1007/978-3-031-30545-0_5.

Google Scholar ePrint

[NABT15]

Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, and Luca Trevisan. Quantum lower bound for inverting a permutation with advice. Quantum Information & Computation, 15(11&12):901–913, 2015. https://doi.org/10.26421/QIC15.11-12-1.

Google Scholar ePrint

[OTU00]

Tatsuaki Okamoto, Keisuke Tanaka, and Shigenori Uchiyama. Quantum public-key cryptosystems. In Mihir Bellare, editor, CRYPTO 2000, volume 1880 of LNCS, 147–165. August 2000. Springer, Heidelberg. https://doi.org/10.1007/3-540-44598-6_9.

Google Scholar ePrint

[RTV04]

Omer Reingold, Luca Trevisan, and Salil P. Vadhan. Notions of reducibility between cryptographic primitives. In Moni Naor, editor, TCC 2004, volume 2951 of LNCS, 1–20. February 2004. Springer, Heidelberg. https://doi.org/10.1007/978-3-540-24638-1_1.

Google Scholar ePrint

[WC81]

Mark K. Wegman and J. Lawrence Carter. New hash functions and their use in authentication and set equality. Journal of Computer and System Sciences, 22(3):265–279, June 1981. https://doi.org/10.1016/0022-0000(81)90033-7.

Google Scholar ePrint

[Yue14]

Henry Yuen. A quantum lower bound for distinguishing random functions from random permutations. Quantum Inf. Comput., 14(13-14):1089–1097, 2014. https://doi.org/10.26421/QIC14.13-14-2.

Google Scholar ePrint

[Zha12a]

Mark Zhandry. How to construct quantum random functions. In 53rd FOCS, 679–687. October 2012. IEEE Computer Society Press. https://doi.org/10.1109/FOCS.2012.37.

Google Scholar ePrint

[Zha12b]

Mark Zhandry. Secure identity-based encryption in the quantum random oracle model. In Reihaneh Safavi-Naini and Ran Canetti, editors, CRYPTO 2012, volume 7417 of LNCS, 758–775. August 2012. Springer, Heidelberg. https://doi.org/10.1007/978-3-642-32009-5_44.

Google Scholar ePrint

[Zha15]

Marc Zhandry. A note on the quantum collision and set equality problems. Quantum Information & Computation, 15(7&8):557–567, 2015. https://doi.org/10.26421/QIC15.7-8-2.

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/a66c0l5vt

History

Submitted: 2024-01-04
Accepted: 2024-03-05
Published: 2024-04-09

How to cite

Keita Xagawa, "On the Efficiency of Generic, Quantum Cryptographic Constructions," IACR Communications in Cryptology, vol. 1, no. 1, Apr 09, 2024, doi: 10.62056/a66c0l5vt.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.

@article{CiC-1-1-8,
    author = "Xagawa, Keita",
    journal = "{IACR} {C}ommunications in {C}ryptology",
    publisher = "{I}nternational {A}ssociation for {C}ryptologic {R}esearch",
    title = "On the Efficiency of Generic, Quantum Cryptographic Constructions",
    volume = "1",
    number = "1",
    date = "2024-04-09",
    year = "2024",
    issn = "3006-5496",
    doi = "10.62056/a66c0l5vt"
}

TY - JOUR
AU - Xagawa, Keita
PY  - 2024
TI  - On the Efficiency of Generic, Quantum Cryptographic Constructions
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 1
IS  - 1
DO  - 10.62056/a66c0l5vt
UR  - https://doi.org/10.62056/a66c0l5vt
AB  - <p>One of the central questions in cryptology is how efficient generic constructions of cryptographic primitives can be. Gennaro, Gertner, Katz, and Trevisan [SIAM J. of Compt., 2005] studied the lower bounds of the number of invocations of a (trapdoor) one-way permutation in order to construct cryptographic schemes, e.g., pseudorandom number generators, digital signatures, and public-key and symmetric-key encryption.</p><p>Recently, quantum machines have been explored to _construct_ cryptographic primitives other than quantum key distribution. This paper studies the efficiency of _quantum_ black-box constructions of cryptographic primitives when the communications are _classical_. Following Gennaro et al., we give the lower bounds of the number of invocations of an underlying quantumly-computable quantum-one-way permutation when the _quantum_ construction of pseudorandom number generator and symmetric-key encryption is weakly black-box. Our results show that the quantum black-box constructions of pseudorandom number generator and symmetric-key encryption do not improve the number of invocations of an underlying quantumly-computable quantum-one-way permutation. </p>
ER  -

Keita Xagawa, "On the Efficiency of Generic, Quantum Cryptographic Constructions," IACR Communications in Cryptology, vol. 1, no. 1, Apr 09, 2024, doi: 10.62056/a66c0l5vt.