{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T11:27:11Z","timestamp":1740137231472,"version":"3.37.3"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2024,5,13]],"date-time":"2024-05-13T00:00:00Z","timestamp":1715558400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,5,13]],"date-time":"2024-05-13T00:00:00Z","timestamp":1715558400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100012166","name":"National Key Research and Development Program of China","doi-asserted-by":"publisher","award":["2022YFB2702701"],"award-info":[{"award-number":["2022YFB2702701"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61972050"],"award-info":[{"award-number":["61972050"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Inf Process"],"DOI":"10.1007\/s11128-024-04387-w","type":"journal-article","created":{"date-parts":[[2024,5,13]],"date-time":"2024-05-13T09:02:49Z","timestamp":1715590969000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Post-quantum $$\\kappa $$-to-1 trapdoor claw-free functions from extrapolated dihedral cosets"],"prefix":"10.1007","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9147-6554","authenticated-orcid":false,"given":"Xingyu","family":"Yan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Licheng","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lize","family":"Gu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ziyi","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jingwen","family":"Suo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,5,13]]},"reference":[{"key":"4387_CR1","doi-asserted-by":"publisher","unstructured":"Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings 35th annual symposium on foundations of computer science. pp. 124\u2013134. IEEE (1994). https:\/\/doi.org\/10.1109\/SFCS.1994.365700","DOI":"10.1109\/SFCS.1994.365700"},{"issue":"25","key":"4387_CR2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.130.250801","volume":"130","author":"L Zhou","year":"2023","unstructured":"Zhou, L., Lin, J., Xie, Y.M., Lu, Y.S., Jing, Y., Yin, H.L., Yuan, Z.: Experimental quantum communication overcomes the rate-loss limit without global phase tracking. Phys. Rev. Lett. 130(25), 250801 (2023). https:\/\/doi.org\/10.1103\/PhysRevLett.130.250801","journal-title":"Phys. Rev. Lett."},{"issue":"2","key":"4387_CR3","doi-asserted-by":"publisher","DOI":"10.1103\/PRXQuantum.3.020315","volume":"3","author":"YM Xie","year":"2022","unstructured":"Xie, Y.M., Lu, Y.S., Weng, C.X., Cao, X.Y., Jia, Z.Y., Bao, Y., Wang, Y., Fu, Y., Yin, Y., Chen, H.L., Chen, Z.B.: Breaking the rate-loss bound of quantum key distribution with asynchronous two-photon interference. PRX Quantum 3(2), 020315 (2022). https:\/\/doi.org\/10.1103\/PRXQuantum.3.020315","journal-title":"PRX Quantum"},{"issue":"4","key":"4387_CR4","doi-asserted-by":"publisher","first-page":"nwac228","DOI":"10.1093\/nsr\/nwac228","volume":"10","author":"HL Yin","year":"2023","unstructured":"Yin, H.L., Fu, Y., Li, C.L., Weng, C.X., Li, B.H., Gu, J., Lu, Y.S., Huang, S., Chen, Z.B.: Experimental quantum secure network with digital signatures and encryption. Natl. Sci. Rev. 10(4), nwac228 (2023). https:\/\/doi.org\/10.1093\/nsr\/nwac228","journal-title":"Natl. Sci. Rev."},{"issue":"2","key":"4387_CR5","doi-asserted-by":"publisher","first-page":"3258","DOI":"10.1126\/sciadv.adk3258","volume":"10","author":"XY Cao","year":"2024","unstructured":"Cao, X.Y., Li, B.H., Wang, Y., Fu, Y., Yin, H.L., Chen, Z.B.: Experimental quantum e-commerce. Sci. Adv. 10(2), 3258 (2024). https:\/\/doi.org\/10.1126\/sciadv.adk3258","journal-title":"Sci. Adv."},{"issue":"3","key":"4387_CR6","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevResearch.5.033077","volume":"5","author":"CL Li","year":"2023","unstructured":"Li, C.L., Fu, Y., Liu, W.B., Xie, Y.M., Li, B.H., Zhou, M.G., Yin, H.L., Chen, Z.B.: Breaking the rate-distance limitation of measurement-device-independent quantum secret sharing. Phys. Rev. Res. 5(3), 033077 (2023). https:\/\/doi.org\/10.1103\/PhysRevResearch.5.033077","journal-title":"Phys. Rev. Res."},{"issue":"1","key":"4387_CR7","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1038\/s42005-023-01238-5","volume":"6","author":"CL Li","year":"2023","unstructured":"Li, C.L., Fu, Y., Liu, W.B., Xie, Y.M., Li, B.H., Zhou, M.G., Yin, H.L., Chen, Z.B.: Breaking universal limitations on quantum conference key agreement without quantum memory. Commun. Phys. 6(1), 122 (2023). https:\/\/doi.org\/10.1038\/s42005-023-01238-5","journal-title":"Commun. Phys."},{"issue":"7671","key":"4387_CR8","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1038\/nature23461","volume":"549","author":"DJ Bernstein","year":"2017","unstructured":"Bernstein, D.J., Lange, T.: Post-quantum cryptography. Nature 549(7671), 188\u2013194 (2017). https:\/\/doi.org\/10.1038\/nature23461","journal-title":"Nature"},{"key":"4387_CR9","doi-asserted-by":"publisher","unstructured":"Castryck, W., Decru, T.: An efficient key recovery attack on SIDH. In: Hazay, C., Stam, M. (eds) Advances in Cryptology - EUROCRYPT 2023. Lecture Notes in Computer Science, vol 14008. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-30589-4_15","DOI":"10.1007\/978-3-031-30589-4_15"},{"key":"4387_CR10","doi-asserted-by":"publisher","unstructured":"Alagic, G., Apon, D., Cooper, D., et al.: Status report on the third round of the NIST post-quantum cryptography standardization process. US Department of Commerce, NIST (2022). https:\/\/doi.org\/10.6028\/NIST.IR.8413","DOI":"10.6028\/NIST.IR.8413"},{"issue":"6","key":"4387_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3292548","volume":"51","author":"H Nejatollahi","year":"2019","unstructured":"Nejatollahi, H., Dutt, N., Ray, S., Regazzoni, F., Banerjee, I., Cammarota, R.: Post-quantum lattice-based cryptography implementations: a survey. ACM Comput. Surv. 51(6), 1\u201341 (2019). https:\/\/doi.org\/10.1145\/3292548","journal-title":"ACM Comput. Surv."},{"issue":"2","key":"4387_CR12","doi-asserted-by":"publisher","DOI":"10.1103\/RevModPhys.94.025008","volume":"94","author":"C Portmann","year":"2022","unstructured":"Portmann, C., Renner, R.: Security in quantum cryptography. Rev. Mod. Phys. 94(2), 025008 (2022). https:\/\/doi.org\/10.1103\/RevModPhys.94.025008","journal-title":"Rev. Mod. Phys."},{"key":"4387_CR13","doi-asserted-by":"publisher","unstructured":"Aaronson, S., Cojocaru, A., Gheorghiu, A., Kashefi, E.: Complexity-theoretic limitations on blind delegated quantum computation. In: 46th International colloquium on automata, languages, and programming (ICALP), 132, pp. 6:1-6:13, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2019.6","DOI":"10.4230\/LIPIcs.ICALP.2019.6"},{"key":"4387_CR14","doi-asserted-by":"publisher","unstructured":"Gheorghiu, A., Vidick, T.: Computationally-secure and composable remote state preparation. In: 2019 IEEE 60th annual symposium on foundations of computer science (FOCS). pp. 1024\u20131033. IEEE (2019). https:\/\/doi.org\/10.1109\/FOCS.2019.00066","DOI":"10.1109\/FOCS.2019.00066"},{"key":"4387_CR15","doi-asserted-by":"publisher","unstructured":"Brakerski, Z., Christiano, P., Mahadev, U., Vazirani, U., Vidick, T.: A cryptographic test of quantumness and certifiable randomness from a single quantum device. In: 2018 IEEE 59th annual symposium on foundations of computer science (FOCS). pp. 320\u2013331. IEEE Computer Society (2018). https:\/\/doi.org\/10.1109\/FOCS.2018.00038","DOI":"10.1109\/FOCS.2018.00038"},{"key":"4387_CR16","doi-asserted-by":"publisher","unstructured":"Mahadev, U.: Classical homomorphic encryption for quantum circuits. In: 2018 IEEE 59th Annual symposium on foundations of computer science (FOCS). pp. 332\u2013338. IEEE Computer Society (2018). https:\/\/doi.org\/10.1109\/FOCS.2018.00039","DOI":"10.1109\/FOCS.2018.00039"},{"key":"4387_CR17","doi-asserted-by":"publisher","unstructured":"Mahadev, U.: Classical verification of quantum computations. In: 2018 IEEE 59th annual symposium on foundations of computer science (FOCS). pp. 259\u2013267. IEEE (2018) https:\/\/doi.org\/10.1109\/FOCS.2018.00033","DOI":"10.1109\/FOCS.2018.00033"},{"key":"4387_CR18","doi-asserted-by":"publisher","unstructured":"Radian, R.: Semi-quantum money. In: Proceedings of the 1st ACM conference on advances in financial technologies. pp. 132\u2013146 (2019). https:\/\/doi.org\/10.1145\/3318041.3355462","DOI":"10.1145\/3318041.3355462"},{"issue":"1","key":"4387_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00145-020-09372-x","volume":"34","author":"M Zhandry","year":"2021","unstructured":"Zhandry, M.: Quantum lightning never strikes the same state twice or: quantum money from cryptographic assumptions. J. Cryptol. 34(1), 1\u201356 (2021). https:\/\/doi.org\/10.1007\/s00145-020-09372-x","journal-title":"J. Cryptol."},{"key":"4387_CR20","doi-asserted-by":"publisher","unstructured":"Brakerski, Z., Koppula, V., Vazirani, U., Vidick, T.: Simpler proofs of quantumness. arXiv preprint arXiv:2005.04826 (2020). doi: https:\/\/doi.org\/10.48550\/arXiv.2005.04826","DOI":"10.48550\/arXiv.2005.04826"},{"key":"4387_CR21","doi-asserted-by":"publisher","first-page":"807","DOI":"10.22331\/q-2022-09-19-807","volume":"6","author":"Z Liu","year":"2022","unstructured":"Liu, Z., Gheorghiu, A.: Depth-efficient proofs of quantumness. Quantum 6, 807 (2022). https:\/\/doi.org\/10.22331\/q-2022-09-19-807","journal-title":"Quantum"},{"issue":"8","key":"4387_CR22","doi-asserted-by":"publisher","first-page":"918","DOI":"10.1038\/s41567-022-01643-7","volume":"18","author":"GD Kahanamoku-Meyer","year":"2022","unstructured":"Kahanamoku-Meyer, G.D., Choi, S., Vazirani, U.V., Yao, N.Y.: Classically verifiable quantum advantage from a computational bell test. Nat. Phys. 18(8), 918\u2013924 (2022). https:\/\/doi.org\/10.1038\/s41567-022-01643-7","journal-title":"Nat. Phys."},{"key":"4387_CR23","doi-asserted-by":"publisher","unstructured":"Alamati, N., Malavolta, G., Rahimi, A.: Candidate Trapdoor Claw-Free Functions from Group Actions with Applications to Quantum Protocols. In: Kiltz, E., Vaikuntanathan, V. (eds) Theory of Cryptography. TCC 2022. Lecture Notes in Computer Science, vol 13747. Springer, Cham (2022). doi: https:\/\/doi.org\/10.1007\/978-3-031-22318-1_10","DOI":"10.1007\/978-3-031-22318-1_10"},{"key":"4387_CR24","doi-asserted-by":"publisher","unstructured":"Alagic, G., Childs, A.M., Grilo, A.B., Hung, S.H.: Non-interactive classical verification of quantum computation. In: Theory of cryptography conference. pp. 153\u2013180. Springer (2020). https:\/\/doi.org\/10.1007\/978-3-030-64381-2_6","DOI":"10.1007\/978-3-030-64381-2_6"},{"key":"4387_CR25","doi-asserted-by":"publisher","unstructured":"Mahadev, U., Vazirani, U., Vidick, T.: Efficient certifiable randomness from a single quantum device. arXiv preprint arXiv:2204.11353 (2022). https:\/\/doi.org\/10.48550\/arXiv.2204.11353","DOI":"10.48550\/arXiv.2204.11353"},{"key":"4387_CR26","doi-asserted-by":"publisher","first-page":"544","DOI":"10.22331\/q-2021-09-16-544","volume":"5","author":"T Metger","year":"2021","unstructured":"Metger, T., Vidick, T.: Self-testing of a single quantum device under computational assumptions. Quantum 5, 544 (2021). https:\/\/doi.org\/10.22331\/q-2021-09-16-544","journal-title":"Quantum"},{"key":"4387_CR27","doi-asserted-by":"publisher","unstructured":"Brakerski, Z., Kirshanova, E., Stehl\u00e9, D., Wen, W.: Learning with errors and extrapolated dihedral cosets. In: IACR international workshop on public key cryptography. pp. 702\u2013727. Springer (2018).https:\/\/doi.org\/10.1007\/978-3-319-76581-5_24","DOI":"10.1007\/978-3-319-76581-5_24"},{"key":"4387_CR28","doi-asserted-by":"publisher","unstructured":"Poremba, A.: Quantum proofs of deletion for learning with errors. arXiv preprint arXiv:2203.01610 (2022). https:\/\/doi.org\/10.48550\/arXiv.2203.01610","DOI":"10.48550\/arXiv.2203.01610"},{"key":"4387_CR29","doi-asserted-by":"publisher","unstructured":"Grover, L., Rudolph, T.: Creating superpositions that correspond to efficiently integrable probability distributions. arXiv preprint quant-ph\/0208112 (2002). https:\/\/doi.org\/10.48550\/arXiv.quant-ph\/0208112","DOI":"10.48550\/arXiv.quant-ph\/0208112"},{"issue":"6","key":"4387_CR30","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1568318.1568324","volume":"56","author":"O Regev","year":"2009","unstructured":"Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56(6), 1\u201340 (2009). https:\/\/doi.org\/10.1145\/1568318.1568324","journal-title":"J. ACM"},{"key":"4387_CR31","doi-asserted-by":"publisher","unstructured":"Micciancio, D., Peikert, C.: Trapdoors for lattices: simpler, tighter, faster, smaller. In: Annual international conference on the theory and applications of cryptographic techniques. pp. 700\u2013718. Springer (2012). https:\/\/doi.org\/10.1007\/978-3-642-29011-4_41","DOI":"10.1007\/978-3-642-29011-4_41"},{"issue":"5","key":"4387_CR32","doi-asserted-by":"publisher","first-page":"1474","DOI":"10.1137\/S0097539796298637","volume":"26","author":"DR Simon","year":"1997","unstructured":"Simon, D.R.: On the power of quantum computation. SIAM J. Comput. 26(5), 1474\u20131483 (1997). https:\/\/doi.org\/10.1137\/S0097539796298637","journal-title":"SIAM J. Comput."},{"issue":"1","key":"4387_CR33","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1103\/RevModPhys.82.1","volume":"82","author":"AM Childs","year":"2010","unstructured":"Childs, A.M., Van Dam, W.: Quantum algorithms for algebraic problems. Rev. Mod. Phys. 82(1), 1 (2010). https:\/\/doi.org\/10.1103\/RevModPhys.82.1","journal-title":"Rev. Mod. Phys."},{"issue":"3","key":"4387_CR34","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1006\/aama.2000.0699","volume":"25","author":"M Ettinger","year":"2000","unstructured":"Ettinger, M., H\u00f8yer, P.: On quantum algorithms for noncommutative hidden subgroups. Adv. Appl. Math. 25(3), 239\u2013251 (2000). https:\/\/doi.org\/10.1006\/aama.2000.0699","journal-title":"Adv. Appl. Math."},{"key":"4387_CR35","doi-asserted-by":"publisher","unstructured":"Regev, O.: Quantum computation and lattice problems. In: Proceedings of the 43rd symposium on foundations of computer science. pp. 520\u2013529 (2002). https:\/\/doi.org\/10.1137\/S0097539703440678","DOI":"10.1137\/S0097539703440678"},{"key":"4387_CR36","doi-asserted-by":"publisher","unstructured":"Chen, Y., Liu, Q., Zhandry, M.: Quantum algorithms for variants of average-case lattice problems via filtering. In: Annual international conference on the theory and applications of cryptographic techniques. pp. 372\u2013401. Springer (2022). https:\/\/doi.org\/10.1007\/978-3-031-07082-2_14","DOI":"10.1007\/978-3-031-07082-2_14"},{"key":"4387_CR37","doi-asserted-by":"publisher","unstructured":"Bacon, D., Childs, A.M., van Dam, W.: Optimal measurements for the dihedral hidden subgroup problem. arXiv preprint quant-ph\/0501044 (2005). https:\/\/doi.org\/10.4086\/cjtcs.2006.002","DOI":"10.4086\/cjtcs.2006.002"},{"issue":"1","key":"4387_CR38","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1137\/S0097539703436345","volume":"35","author":"G Kuperberg","year":"2005","unstructured":"Kuperberg, G.: A subexponential-time quantum algorithm for the dihedral hidden subgroup problem. SIAM J. Comput. 35(1), 170\u2013188 (2005). https:\/\/doi.org\/10.1137\/S0097539703436345","journal-title":"SIAM J. Comput."},{"key":"4387_CR39","doi-asserted-by":"publisher","unstructured":"Regev, O.: A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space. arXiv preprint quant-ph\/0406151 (2004). https:\/\/doi.org\/10.48550\/arXiv.quant-ph\/0406151","DOI":"10.48550\/arXiv.quant-ph\/0406151"},{"key":"4387_CR40","doi-asserted-by":"publisher","unstructured":"Kuperberg, G.: Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem. arXiv preprint arXiv:1112.3333 (2011). https:\/\/doi.org\/10.48550\/arXiv.1112.3333","DOI":"10.48550\/arXiv.1112.3333"},{"key":"4387_CR41","doi-asserted-by":"publisher","unstructured":"Friedl, K., Ivanyos, G., Magniez, F., Santha, M., Sen, P.: Hidden translation and orbit coset in quantum computing. In: Proceedings of the thirty-fifth annual ACM symposium on theory of computing. pp.\u00a01\u20139 (2003). https:\/\/doi.org\/10.1145\/780542.780544","DOI":"10.1145\/780542.780544"},{"issue":"1","key":"4387_CR42","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/130907203","volume":"43","author":"K Friedl","year":"2014","unstructured":"Friedl, K., Ivanyos, G., Magniez, F., Santha, M., Sen, P.: Hidden translation and translating coset in quantum computing. SIAM J. Comput. 43(1), 1\u201324 (2014). https:\/\/doi.org\/10.1137\/130907203","journal-title":"SIAM J. Comput."},{"key":"4387_CR43","unstructured":"Ivanyos, G., Prakash, A., Santha, M.: On learning linear functions from subset and its applications in quantum computing. In: 26th Annual European symposium on algorithms (ESA 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2018). http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2018\/9529"},{"key":"4387_CR44","doi-asserted-by":"publisher","unstructured":"Gentry, C.: A fully homomorphic encryption scheme. Stanford university (2009). https:\/\/doi.org\/10.5555\/1834954","DOI":"10.5555\/1834954"}],"container-title":["Quantum Information Processing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-024-04387-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11128-024-04387-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-024-04387-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,28]],"date-time":"2024-05-28T18:52:21Z","timestamp":1716922341000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11128-024-04387-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,13]]},"references-count":44,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2024,5]]}},"alternative-id":["4387"],"URL":"https:\/\/doi.org\/10.1007\/s11128-024-04387-w","relation":{},"ISSN":["1573-1332"],"issn-type":[{"type":"electronic","value":"1573-1332"}],"subject":[],"published":{"date-parts":[[2024,5,13]]},"assertion":[{"value":"30 May 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 April 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 May 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"188"}}