{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T00:51:33Z","timestamp":1740099093317,"version":"3.37.3"},"publisher-location":"Cham","reference-count":47,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319964171"},{"type":"electronic","value":"9783319964188"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-96418-8_26","type":"book-chapter","created":{"date-parts":[[2018,7,13]],"date-time":"2018-07-13T06:57:13Z","timestamp":1531465033000},"page":"218-226","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["The Hidden Subgroup Problem and Post-quantum Group-Based Cryptography"],"prefix":"10.1007","author":[{"given":"Kelsey","family":"Horan","sequence":"first","affiliation":[]},{"given":"Delaram","family":"Kahrobaei","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,7,14]]},"reference":[{"key":"26_CR1","unstructured":"Childs, A.: Lecture notes on quantum algorithms (2017)"},{"key":"26_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1007\/978-3-319-76578-5_13","volume-title":"Public-Key Cryptography \u2013 PKC 2018","author":"D Hart","year":"2018","unstructured":"Hart, D., et al.: A practical cryptanalysis of WalnutDSA$$^{\\text{ TM }}$$TM. In: Abdalla, M., Dahab, R. (eds.) PKC 2018. LNCS, vol. 10769, pp. 381\u2013406. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-76578-5_13"},{"key":"26_CR3","unstructured":"Anshel, I., Atkins, D., Goldfeld, D., Gunnells, P.: WalnutDSA(TM): a quantum resistant group theoretic digital signature algorithm. IACR Cryptology ePrint Archive (2017)"},{"key":"26_CR4","unstructured":"Wang, L., Wang, L.: Conjugate searching problem vs. hidden subgroup problem. In: The Third International Workshop on Post-Quantum Cryptography, Recent Results Session (2010)"},{"issue":"3","key":"26_CR5","doi-asserted-by":"publisher","first-page":"524","DOI":"10.1007\/s11432-010-0046-4","volume":"53","author":"L Wang","year":"2010","unstructured":"Wang, L., Wang, L., Cao, Z., Yang, Y., Niu, X.: Conjugate adjoining problem in braid groups and new design of braid-based signatures. Sci. China Inf. Sci. 53(3), 524\u2013536 (2010)","journal-title":"Sci. China Inf. Sci."},{"key":"26_CR6","doi-asserted-by":"crossref","unstructured":"Grover, L.: A fast quantum mechanical algorithm for database search. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, pp. 212\u2013219 (1996)","DOI":"10.1145\/237814.237866"},{"key":"26_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/3-540-39568-7_3","volume-title":"Advances in Cryptology","author":"NR Wagner","year":"1985","unstructured":"Wagner, N.R., Magyarik, M.R.: A public-key cryptosystem based on the word problem. In: Blakley, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 19\u201336. Springer, Heidelberg (1985). https:\/\/doi.org\/10.1007\/3-540-39568-7_3"},{"key":"26_CR8","first-page":"8","volume":"28","author":"R Flores","year":"2016","unstructured":"Flores, R., Kahrobaei, D.: Cryptography with right-angled artin groups. Theoret. Appl. Inform. 28, 8\u201316 (2016)","journal-title":"Theoret. Appl. Inform."},{"key":"26_CR9","doi-asserted-by":"crossref","unstructured":"Flores, R., Kahrobaei, D., Koberda, T.: Algorithmic problems in right-angled artin groups: complexity and applications. arXiv preprint arXiv:1802.04870 (2018)","DOI":"10.1016\/j.jalgebra.2018.10.023"},{"key":"26_CR10","unstructured":"Eick, B., Kahrobaei, D.: Polycyclic groups: a new platform for cryptology? arXiv preprint math\/0411077 (2004)"},{"issue":"2","key":"26_CR11","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1515\/gcc-2016-0013","volume":"8","author":"J Gryak","year":"2016","unstructured":"Gryak, J., Kahrobaei, D.: The status of polycyclic group-based cryptography: a survey and open problems. Groups Complex. Cryptology 8(2), 171\u2013186 (2016)","journal-title":"Groups Complex. Cryptology"},{"key":"26_CR12","doi-asserted-by":"crossref","unstructured":"Kahrobaei, D., Koupparis, C.: On-commutative digital signatures using non-commutative groups. Groups Complexity Cryptology, pp. 377\u2013384 (2012)","DOI":"10.1515\/gcc-2012-0019"},{"key":"26_CR13","doi-asserted-by":"crossref","unstructured":"Kahrobaei, D., Khan, B.: A non-commutative generalization of ELGamal key exchange using polycyclic groups. In: IEEE Global Telecommunications Conference 2006, pp. 1\u20135 (2006)","DOI":"10.1109\/GLOCOM.2006.290"},{"key":"26_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1007\/978-3-642-38980-1_30","volume-title":"Applied Cryptography and Network Security","author":"M Habeeb","year":"2013","unstructured":"Habeeb, M., Kahrobaei, D., Koupparis, C., Shpilrain, V.: Public key exchange using semidirect product of (semi)groups. In: Jacobson, M., Locasto, M., Mohassel, P., Safavi-Naini, R. (eds.) ACNS 2013. LNCS, vol. 7954, pp. 475\u2013486. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-38980-1_30"},{"key":"26_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/11496137_11","volume-title":"Applied Cryptography and Network Security","author":"V Shpilrain","year":"2005","unstructured":"Shpilrain, V., Ushakov, A.: Thompson\u2019s group and public key cryptography. In: Ioannidis, J., Keromytis, A., Yung, M. (eds.) ACNS 2005. LNCS, vol. 3531, pp. 151\u2013163. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11496137_11"},{"key":"26_CR16","first-page":"14","volume":"29","author":"I Chatterji","year":"2017","unstructured":"Chatterji, I., Kahrobaei, D., Lu, N.Y.: Cryptosystems using subgroup distortion. Theoret. Appl. Inform. 29, 14\u201324 (2017)","journal-title":"Theoret. Appl. Inform."},{"issue":"3\u20134","key":"26_CR17","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/s00200-006-0006-9","volume":"17","author":"V Shpilrain","year":"2006","unstructured":"Shpilrain, V., Zapata, G.: Combinatorial group theory and public key cryptography. Appl. Algebra Eng. Commun. Comput. 17(3\u20134), 291\u2013302 (2006)","journal-title":"Appl. Algebra Eng. Commun. Comput."},{"key":"26_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1007\/978-3-319-40189-8_14","volume-title":"Pursuit of the Universal","author":"D Kahrobaei","year":"2016","unstructured":"Kahrobaei, D., Shpilrain, V.: Using semidirect product of (semi)groups in public key cryptography. In: Beckmann, A., Bienvenu, L., Jonoska, N. (eds.) CiE 2016. LNCS, vol. 9709, pp. 132\u2013141. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-40189-8_14"},{"issue":"3\u20134","key":"26_CR19","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/s00200-006-0003-z","volume":"17","author":"G Baumslag","year":"2006","unstructured":"Baumslag, G., Fine, B., Xu, X.: Cryptosystems using linear groups. Appl. Algebra Eng. Commun. Comput. 17(3\u20134), 205\u2013217 (2006)","journal-title":"Appl. Algebra Eng. Commun. Comput."},{"key":"26_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1007\/978-3-540-40974-8_19","volume-title":"Cryptography and Coding","author":"G Petrides","year":"2003","unstructured":"Petrides, G.: Cryptanalysis of the public key cryptosystem based on the word problem on the Grigorchuk groups. In: Paterson, K.G. (ed.) Cryptography and Coding 2003. LNCS, vol. 2898, pp. 234\u2013244. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/978-3-540-40974-8_19"},{"key":"26_CR21","unstructured":"Grigoriev, D., Ponomarenko, I.: Homomorphic public-key cryptosystems over groups and rings. arXiv preprint cs\/0309010 (2003)"},{"key":"26_CR22","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0333-9","volume-title":"The Graph Isomorphism Problem: Its Structural Complexity","author":"J Kobler","year":"2012","unstructured":"Kobler, J., Sch\u00f6ning, U., Tor\u00e1n, J.: The Graph Isomorphism Problem: Its Structural Complexity. Springer Science & Business Media, New York (2012). https:\/\/doi.org\/10.1007\/978-1-4612-0333-9"},{"key":"26_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1007\/3-540-44750-4_34","volume-title":"Advances in Cryptology \u2014 CRYPT0 1995","author":"D Boneh","year":"1995","unstructured":"Boneh, D., Lipton, R.J.: Quantum cryptanalysis of hidden linear functions. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 424\u2013437. Springer, Heidelberg (1995). https:\/\/doi.org\/10.1007\/3-540-44750-4_34"},{"issue":"1\u20132","key":"26_CR24","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/S0304-3975(96)00188-0","volume":"180","author":"D Grigoriev","year":"1997","unstructured":"Grigoriev, D.: Testing shift-equivalence of polynomials by deterministic, probabilistic and quantum machines. Theoret. Comput. Sci. 180(1\u20132), 217\u2013228 (1997)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"26_CR25","doi-asserted-by":"publisher","first-page":"738","DOI":"10.1137\/S0097539703440678","volume":"33","author":"O Regev","year":"2004","unstructured":"Regev, O.: Quantum computation and lattice problems. SIAM J. Comput. 33(3), 738\u2013760 (2004)","journal-title":"SIAM J. Comput."},{"key":"26_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/978-3-319-56617-7_3","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2017","author":"G Alagic","year":"2017","unstructured":"Alagic, G., Russell, A.: Quantum-secure symmetric-key cryptography based on hidden shifts. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10212, pp. 65\u201393. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-56617-7_3"},{"issue":"5","key":"26_CR27","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)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"26_CR28","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1137\/S0036144598347011","volume":"41","author":"P Shor","year":"1999","unstructured":"Shor, P.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Rev. 41(2), 303\u2013332 (1999)","journal-title":"SIAM Rev."},{"issue":"6","key":"26_CR29","doi-asserted-by":"publisher","first-page":"1191","DOI":"10.1070\/RM1997v052n06ABEH002155","volume":"52","author":"A Kitaev","year":"1997","unstructured":"Kitaev, A.: Quantum computations: algorithms and error correction. Russ. Math. Surv. 52(6), 1191\u20131249 (1997)","journal-title":"Russ. Math. Surv."},{"key":"26_CR30","doi-asserted-by":"crossref","unstructured":"Brassard, G., Hoyer, P.: An exact quantum polynomial-time algorithm for Simon\u2019s problem. In: Proceedings of the Fifth Israeli Symposium on Theory of Computing and Systems, pp. 12\u201323. IEEE (1997)","DOI":"10.1109\/ISTCS.1997.595153"},{"key":"26_CR31","doi-asserted-by":"crossref","unstructured":"Grigni, M., Schulman, L., Vazirani, M., Vazirani, U.: Quantum mechanical algorithms for the nonabelian hidden subgroup problem. In: Proceedings of the thirty-third annual ACM Symposium on Theory of Computing, pp. 68\u201374 (2001)","DOI":"10.1145\/380752.380769"},{"issue":"3","key":"26_CR32","first-page":"229","volume":"4","author":"D Gavinsky","year":"2004","unstructured":"Gavinsky, D.: Quantum solution to the hidden subgroup problem for poly-near-hamiltonian groups. Quantum Inf. Comput. 4(3), 229\u2013235 (2004)","journal-title":"Quantum Inf. Comput."},{"issue":"05","key":"26_CR33","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1142\/S0129054103001996","volume":"14","author":"G Ivanyos","year":"2003","unstructured":"Ivanyos, G., Magniez, F., Santha, M.: Efficient quantum algorithms for some instances of the non-abelian hidden subgroup problem. Int. J. Found. Comput. Sci. 14(05), 723\u2013739 (2003)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"1","key":"26_CR34","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)","journal-title":"SIAM J. Comput."},{"key":"26_CR35","doi-asserted-by":"crossref","unstructured":"Hallgren, S., Russell, A., Ta-Shma, A.: Normal subgroup reconstruction and quantum computation using group representations. In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, pp. 627\u2013635 (2000)","DOI":"10.1145\/335305.335392"},{"issue":"4","key":"26_CR36","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1515\/jmc-2013-0038","volume":"8","author":"A Childs","year":"2014","unstructured":"Childs, A., Ivanyos, G.: Quantum computation of discrete logarithms in semigroups. J. Math. Cryptology 8(4), 405\u2013416 (2014)","journal-title":"J. Math. Cryptology"},{"issue":"1","key":"26_CR37","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)","journal-title":"SIAM J. Comput."},{"key":"26_CR38","unstructured":"Regev, O.: A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space. arXiv preprint quant-ph\/0406151 (2004)"},{"key":"26_CR39","unstructured":"Roetteler, M., Beth, T.: Polynomial-time solution to the hidden subgroup problem for a class of non-abelian groups. arXiv preprint quant-ph\/9812070 (1998)"},{"key":"26_CR40","doi-asserted-by":"crossref","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. 1\u20139 (2003)","DOI":"10.1145\/780542.780544"},{"key":"26_CR41","unstructured":"Moore, C., Rockmore, D., Russell, A., Schulman, L.: The power of basis selection in Fourier sampling: hidden subgroup problems in affine groups. In: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1113\u20131122 (2004)"},{"key":"26_CR42","unstructured":"Inui, Y., Le Gall, F.: An efficient algorithm for the hidden subgroup problem over a class of semi-direct product groups. Technical report (2004)"},{"key":"26_CR43","unstructured":"Gon\u00e7alves, D., Portugal, R.: Solution to the hidden subgroup problem for a class of noncommutative groups. arXiv preprint arXiv:1104.1361 (2011)"},{"issue":"2","key":"26_CR44","doi-asserted-by":"publisher","first-page":"215","DOI":"10.5540\/tema.2017.018.02.0215","volume":"18","author":"D Gon\u00e7alves","year":"2017","unstructured":"Gon\u00e7alves, D., Fernandes, T., Cosme, C.: An efficient quantum algorithm for the hidden subgroup problem over some non-abelian groups. TEMA (S\u00e3o Carlos) 18(2), 215\u2013223 (2017)","journal-title":"TEMA (S\u00e3o Carlos)"},{"issue":"1","key":"26_CR45","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/j.ipl.2004.01.024","volume":"91","author":"M Ettinger","year":"2004","unstructured":"Ettinger, M., H\u00f8yer, P., Knill, E.: The quantum query complexity of the hidden subgroup problem is polynomial. Inf. Process. Lett. 91(1), 43\u201348 (2004)","journal-title":"Inf. Process. Lett."},{"key":"26_CR46","unstructured":"Kissinger, A., Gogioso, S.: Fully graphical treatment of the quantum algorithm for the hidden subgroup problem. arXiv preprint quant-ph 1701.08669 (2017)"},{"key":"26_CR47","doi-asserted-by":"crossref","unstructured":"Eisentr\u00e4ger, K., Hallgren, S., Kitaev, A., Song, F.: A quantum algorithm for computing the unit group of an arbitrary degree number field. In: Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, pp. 293\u2013302 (2014)","DOI":"10.1145\/2591796.2591860"}],"container-title":["Lecture Notes in Computer Science","Mathematical Software \u2013 ICMS 2018"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-96418-8_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,20]],"date-time":"2019-10-20T15:36:03Z","timestamp":1571585763000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-96418-8_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319964171","9783319964188"],"references-count":47,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-96418-8_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]}}}