nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

The Hidden Subgroup Problem and Post-quantum Group-Based Cryptography

verfasst von : Kelsey Horan, Delaram Kahrobaei

Erschienen in: Mathematical Software – ICMS 2018

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In this paper we discuss the Hidden Subgroup Problem (HSP) in relation to post-quantum cryptography. We review the relationship between HSP and other computational problems, discuss an optimal solution method, and review results about the quantum complexity of HSP. We also overview some platforms for group-based cryptosystems. Notably, efficient algorithms for solving HSP in the proposed infinite group platforms are not yet known.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel 3BA: A Border Bases Solver with a SAT Extension

Nächstes Kapitel Questions on Orbital Graphs

Childs, A.: Lecture notes on quantum algorithms (2017)

Hart, D., et al.: A practical cryptanalysis of WalnutDSA\(^{\text{ TM }}\). In: Abdalla, M., Dahab, R. (eds.) PKC 2018. LNCS, vol. 10769, pp. 381–406. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-76578-5_13CrossRef

Anshel, I., Atkins, D., Goldfeld, D., Gunnells, P.: WalnutDSA(TM): a quantum resistant group theoretic digital signature algorithm. IACR Cryptology ePrint Archive (2017)

Wang, L., Wang, L.: Conjugate searching problem vs. hidden subgroup problem. In: The Third International Workshop on Post-Quantum Cryptography, Recent Results Session (2010)

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–536 (2010)MathSciNetCrossRef

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–219 (1996)

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–36. Springer, Heidelberg (1985). https://doi.org/10.1007/3-540-39568-7_3CrossRef

Flores, R., Kahrobaei, D.: Cryptography with right-angled artin groups. Theoret. Appl. Inform. 28, 8–16 (2016)

Flores, R., Kahrobaei, D., Koberda, T.: Algorithmic problems in right-angled artin groups: complexity and applications. arXiv preprint arXiv:1802.04870 (2018)

10.

Eick, B., Kahrobaei, D.: Polycyclic groups: a new platform for cryptology? arXiv preprint math/0411077 (2004)

11.

Gryak, J., Kahrobaei, D.: The status of polycyclic group-based cryptography: a survey and open problems. Groups Complex. Cryptology 8(2), 171–186 (2016)MathSciNetCrossRef

12.

Kahrobaei, D., Koupparis, C.: On-commutative digital signatures using non-commutative groups. Groups Complexity Cryptology, pp. 377–384 (2012)

13.

Kahrobaei, D., Khan, B.: A non-commutative generalization of ELGamal key exchange using polycyclic groups. In: IEEE Global Telecommunications Conference 2006, pp. 1–5 (2006)

14.

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–486. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38980-1_30CrossRef

15.

Shpilrain, V., Ushakov, A.: Thompson’s group and public key cryptography. In: Ioannidis, J., Keromytis, A., Yung, M. (eds.) ACNS 2005. LNCS, vol. 3531, pp. 151–163. Springer, Heidelberg (2005). https://doi.org/10.1007/11496137_11CrossRefMATH

16.

Chatterji, I., Kahrobaei, D., Lu, N.Y.: Cryptosystems using subgroup distortion. Theoret. Appl. Inform. 29, 14–24 (2017)

17.

Shpilrain, V., Zapata, G.: Combinatorial group theory and public key cryptography. Appl. Algebra Eng. Commun. Comput. 17(3–4), 291–302 (2006)MathSciNetCrossRef

18.

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–141. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-40189-8_14CrossRefMATH

19.

Baumslag, G., Fine, B., Xu, X.: Cryptosystems using linear groups. Appl. Algebra Eng. Commun. Comput. 17(3–4), 205–217 (2006)MathSciNetCrossRef

20.

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–244. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-40974-8_19CrossRef

21.

Grigoriev, D., Ponomarenko, I.: Homomorphic public-key cryptosystems over groups and rings. arXiv preprint cs/0309010 (2003)

22.

Kobler, J., Schöning, U., Torán, J.: The Graph Isomorphism Problem: Its Structural Complexity. Springer Science & Business Media, New York (2012). https://doi.org/10.1007/978-1-4612-0333-9CrossRefMATH

23.

Boneh, D., Lipton, R.J.: Quantum cryptanalysis of hidden linear functions. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 424–437. Springer, Heidelberg (1995). https://doi.org/10.1007/3-540-44750-4_34CrossRef

24.

Grigoriev, D.: Testing shift-equivalence of polynomials by deterministic, probabilistic and quantum machines. Theoret. Comput. Sci. 180(1–2), 217–228 (1997)MathSciNetCrossRef

25.

Regev, O.: Quantum computation and lattice problems. SIAM J. Comput. 33(3), 738–760 (2004)MathSciNetCrossRef

26.

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–93. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56617-7_3CrossRef

27.

Simon, D.R.: On the power of quantum computation. SIAM J. Comput. 26(5), 1474–1483 (1997)MathSciNetCrossRef

28.

Shor, P.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Rev. 41(2), 303–332 (1999)MathSciNetCrossRef

29.

Kitaev, A.: Quantum computations: algorithms and error correction. Russ. Math. Surv. 52(6), 1191–1249 (1997)MathSciNetCrossRef

30.

Brassard, G., Hoyer, P.: An exact quantum polynomial-time algorithm for Simon’s problem. In: Proceedings of the Fifth Israeli Symposium on Theory of Computing and Systems, pp. 12–23. IEEE (1997)

31.

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–74 (2001)

32.

Gavinsky, D.: Quantum solution to the hidden subgroup problem for poly-near-hamiltonian groups. Quantum Inf. Comput. 4(3), 229–235 (2004)MathSciNetMATH

33.

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–739 (2003)MathSciNetCrossRef

34.

Friedl, K., Ivanyos, G., Magniez, F., Santha, M., Sen, P.: Hidden translation and translating coset in quantum computing. SIAM J. Comput. 43(1), 1–24 (2014)MathSciNetCrossRef

35.

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–635 (2000)

36.

Childs, A., Ivanyos, G.: Quantum computation of discrete logarithms in semigroups. J. Math. Cryptology 8(4), 405–416 (2014)MathSciNetCrossRef

37.

Kuperberg, G.: A subexponential-time quantum algorithm for the dihedral hidden subgroup problem. SIAM J. Comput. 35(1), 170–188 (2005)MathSciNetCrossRef

38.

Regev, O.: A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space. arXiv preprint quant-ph/0406151 (2004)

39.

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)

40.

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–9 (2003)

41.

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–1122 (2004)

42.

Inui, Y., Le Gall, F.: An efficient algorithm for the hidden subgroup problem over a class of semi-direct product groups. Technical report (2004)

43.

Gonçalves, D., Portugal, R.: Solution to the hidden subgroup problem for a class of noncommutative groups. arXiv preprint arXiv:1104.1361 (2011)

44.

Gonçalves, D., Fernandes, T., Cosme, C.: An efficient quantum algorithm for the hidden subgroup problem over some non-abelian groups. TEMA (São Carlos) 18(2), 215–223 (2017)MathSciNetCrossRef

45.

Ettinger, M., Høyer, P., Knill, E.: The quantum query complexity of the hidden subgroup problem is polynomial. Inf. Process. Lett. 91(1), 43–48 (2004)MathSciNetCrossRef

46.

Kissinger, A., Gogioso, S.: Fully graphical treatment of the quantum algorithm for the hidden subgroup problem. arXiv preprint quant-ph 1701.08669 (2017)

47.

Eisenträger, 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–302 (2014)

Titel: The Hidden Subgroup Problem and Post-quantum Group-Based Cryptography
verfasst von: Kelsey Horan
Delaram Kahrobaei
Verlag: Springer International Publishing
Buch: Mathematical Software – ICMS 2018
Print ISBN: 978-3-319-96417-1

Electronic ISBN: 978-3-319-96418-8

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-96418-8_26

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner