On Basing One-way Permutations on NP-hard Problems under Quantum Reductions

Nai-Hui Chia; Sean Hallgren; Fang Song

doi:10.22331/q-2020-08-27-312

On Basing One-way Permutations on NP-hard Problems under Quantum Reductions

Nai-Hui Chia¹, Sean Hallgren², and Fang Song³

¹Department of Computer Science, University of Texas at Austin, Austin, TX, 78712, USA.
²Department of Computer Science and Engineering, The Pennsylvania State University, University Park, PA, 16802, USA.
³Department of Computer Science, Portland State University, Portland, OR 97201, USA.

Published:	2020-08-27, volume 4, page 312
Eprint:	arXiv:1804.10309v4
Doi:	https://doi.org/10.22331/q-2020-08-27-312
Citation:	Quantum 4, 312 (2020).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

A fundamental pursuit in complexity theory concerns reducing worst-case problems to average-case problems. There exist complexity classes such as PSPACE that admit worst-case to average-case reductions. However, for many other classes such as NP, the evidence so far is typically negative, in the sense that the existence of such reductions would cause collapses of the polynomial hierarchy(PH). Basing cryptographic primitives, e.g., the average-case hardness of inverting one-way permutations, on NP-completeness is a particularly intriguing instance. As there is evidence showing that classical reductions from NP-hard problems to breaking these primitives result in PH collapses, it seems unlikely to base cryptographic primitives on NP-hard problems. Nevertheless, these results do not rule out the possibilities of the existence of quantum reductions. In this work, we initiate a study of the quantum analogues of these questions. Aside from formalizing basic notions of quantum reductions and demonstrating powers of quantum reductions by examples of separations, our main result shows that if NP-complete problems reduce to inverting one-way permutations using certain types of quantum reductions, then $\textsf{coNP}$ $\subseteq$ $\textsf{QIP}($2$)$.

► BibTeX data

@article{Chia2020basingoneway,
  doi = {10.22331/q-2020-08-27-312},
  url = {https://doi.org/10.22331/q-2020-08-27-312},
  title = {On {B}asing {O}ne-way {P}ermutations on {NP}-hard {P}roblems under {Q}uantum {R}eductions},
  author = {Chia, Nai-Hui and Hallgren, Sean and Song, Fang},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {4},
  pages = {312},
  month = aug,
  year = {2020}
}

► References

[1] Mark Adcock and Richard Cleve. A quantum goldreich-levin theorem with cryptographic applications. In STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, volume 2285, pages 323–334. Springer, 2002. 10.1007/3-540-45841-7_26.
https://doi.org/10.1007/3-540-45841-7_26

[2] M. Ajtai. Generating hard instances of lattice problems (extended abstract). In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’96, pages 99–108, 1996. 10.1145/237814.237838.
https://doi.org/10.1145/237814.237838

[3] Miklós Ajtai and Cynthia Dwork. A public-key cryptosystem with worst-case/average-case equivalence. In Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing, STOC '97, pages 284–293, 1997. 10.1145/258533.258604.
https://doi.org/10.1145/258533.258604

[4] Adi Akavia, Oded Goldreich, Shafi Goldwasser, and Dana Moshkovitz. On basing one-way functions on np-hardness. In Proceedings of the Thirty-eighth Annual ACM Symposium on Theory of Computing, STOC '06, pages 701–710, 2006. 10.1145/1132516.1132614.
https://doi.org/10.1145/1132516.1132614

[5] Dave Bacon, Andrew M. Childs, and Wim van Dam. Optimal measurements for the dihedral hidden subgroup problem. Chicago J. Theor. Comput. Sci., 2006, 2006.

[6] Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. Strengths and weaknesses of quantum computing. SIAM J. Comput., 26 (5): 1510–1523, 1997. 10.1137/S0097539796300933.
https://doi.org/10.1137/S0097539796300933

[7] Andrej Bogdanov and Christina Brzuska. On basing size-verifiable one-way functions on np-hardness. In Theory of Cryptography Conference, pages 1–6. Springer, 2015. 10.1007/978-3-662-46494-6_1.
https://doi.org/10.1007/978-3-662-46494-6_1

[8] Andrej Bogdanov and Chin Ho Lee. Limits of Provable Security for Homomorphic Encryption, pages 111–128. Springer Berlin Heidelberg, 2013. 10.1007/978-3-642-40041-4_7.
https://doi.org/10.1007/978-3-642-40041-4_7

[9] Andrej Bogdanov and Luca Trevisan. On worst-case to average-case reductions for NP problems. SIAM Journal on Computing, 36 (4): 1119–1159, 2006. 10.1137/S0097539705446974.
https://doi.org/10.1137/S0097539705446974

[10] Gilles Brassard. Relativized cryptography. 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, (undefined): 383–391, 1979. ISSN 0272-5428. 10.1109/TIT.1983.1056754.
https://doi.org/10.1109/TIT.1983.1056754

[11] Joan Feigenbaum and Lance Fortnow. Random-self-reducibility of complete sets. SIAM Journal on Computing, 22 (5): 994–1005, 1993. 10.1137/0222061.
https://doi.org/10.1137/0222061

[12] Joan Feigenbaum, Sampath Kannan, and Noam Nisan. Lower bounds on random-self-reducibility. In Proceedings of Fifth Annual Structure in Complexity Theory Conference, pages 100–109. IEEE, 1990. 10.1109/SCT.1990.113959.
https://doi.org/10.1109/SCT.1990.113959

[13] Lance Fortnow and Michael Sipser. Are there interactive protocols for co-np languages? Information Processing Letters, 28: 249–251, 1988. 10.1016/0020-0190(88)90199-8.
https://doi.org/10.1016/0020-0190(88)90199-8

[14] Shafi Goldwasser and Michael Sipser. Private coins versus public coins in interactive proof systems. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing, pages 59–68. ACM, 1986. 10.1145/12130.12137.
https://doi.org/10.1145/12130.12137

[15] Patrick M. Hayden, Kevin Milner, and Mark M. Wilde. Two-message quantum interactive proofs and the quantum separability problem. Quantum Inf. Comput., 14 (5-6): 384–416, 2014.

[16] Rahul Jain, Sarvagya Upadhyay, and John Watrous. Two-message quantum interactive proofs are in PSPACE. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, pages 534–543, 2009. 10.1109/FOCS.2009.30.
https://doi.org/10.1109/FOCS.2009.30

[17] Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, and John Watrous. QIP= PSPACE. Journal of the ACM (JACM), 58 (6): 30, 2011. 10.1145/2049697.2049704.
https://doi.org/10.1145/2049697.2049704

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

[19] Alexei Kitaev and John Watrous. Parallelization, amplification, and exponential time simulation of quantum interactive proof systems. In Proceedings of the Thirty-second Annual ACM Symposium on Theory of Computing, STOC '00, pages 608–617, 2000. 10.1145/335305.335387.
https://doi.org/10.1145/335305.335387

[20] Hirotada Kobayashi, François Le Gall, and Harumichi Nishimura. Generalized quantum arthur-merlin games. In Proceedings of the 30th Conference on Computational Complexity, pages 488–511, 2015. 10.4230/LIPIcs.CCC.2015.488.
https://doi.org/10.4230/LIPIcs.CCC.2015.488

[21] Tianren Liu and Vinod Vaikuntanathan. On basing private information retrieval on np-hardness. In Eyal Kushilevitz and Tal Malkin, editors, Theory of Cryptography - 13th International Conference, TCC 2016-A, volume 9562 of Lecture Notes in Computer Science, pages 372–386. Springer, 2016. 10.1007/978-3-662-49096-9_16.
https://doi.org/10.1007/978-3-662-49096-9_16

[22] Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On ideal lattices and learning with errors over rings. Journal of the ACM (JACM), 60 (6): 43, 2013. 10.1145/2535925.
https://doi.org/10.1145/2535925

[23] Daniele Micciancio. Almost perfect lattices, the covering radius problem, and applications to Ajtai's connection factor. SIAM Journal on Computing, 34 (1): 118–169, 2004. 10.1137/S0097539703433511. Preliminary version in STOC 2002.
https://doi.org/10.1137/S0097539703433511

[24] Daniele Micciancio and Oded Regev. Worst-case to average-case reductions based on gaussian measures. SIAM J. Comput., 37 (1): 267–302, 2007. ISSN 0097-5397. 10.1137/S0097539705447360.
https://doi.org/10.1137/S0097539705447360

[25] Maris Ozols, Martin Roetteler, and Jérémie Roland. Quantum rejection sampling. ACM Trans. Comput. Theory, 5 (3): 11:1–11:33, August 2013. ISSN 1942-3454. 10.1145/2493252.2493256.
https://doi.org/10.1145/2493252.2493256

[26] Oded Regev. Quantum computation and lattice problems. SIAM J. Comput., 33 (3): 738–760, 2004a. 10.1137/S0097539703440678.
https://doi.org/10.1137/S0097539703440678

[27] Oded Regev. New lattice-based cryptographic constructions. J. ACM, 51 (6): 899–942, 2004b. ISSN 0004-5411. 10.1145/1039488.1039490.
https://doi.org/10.1145/1039488.1039490

[28] Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing, STOC '05, pages 84–93. ACM, 2005. 10.1145/1060590.1060603.
https://doi.org/10.1145/1060590.1060603

[29] Bill Rosgen. Computational distinguishability of degradable and antidegradable channels. Quantum Inf. Comput., 10 (9&10): 735–746, 2010.

[30] Benjamin Schumacher. Sending entanglement through noisy quantum channels. Physical Review A, 54 (4): 2614, 1996. 10.1103/PhysRevA.54.2614.
https://doi.org/10.1103/PhysRevA.54.2614

[31] Daniel R Simon. On the power of quantum computation. SIAM journal on computing, 26 (5): 1474–1483, 1997. 10.1137/S0097539796298637.
https://doi.org/10.1137/S0097539796298637

[32] Wim Van Dam, Sean Hallgren, and Lawrence Ip. Quantum algorithms for some hidden shift problems. SIAM Journal on Computing, 36 (3): 763–778, 2006. 10.1137/S009753970343141X.
https://doi.org/10.1137/S009753970343141X

Cited by

On Crossref's cited-by service no data on citing works was found (last attempt 2023-05-29 21:52:32). On SAO/NASA ADS no data on citing works was found (last attempt 2023-05-29 21:52:32).

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.