The hidden subgroup problem and MKTP. (English) Zbl 1434.68203
Summary: We show that the Hidden Subgroup Problem for group families where products and inverses can be computed efficiently is in \(\mathsf{BPP}^{\mathrm{MKTP}}\) (where MKTP is the Minimum \(\mathsf{KT}\) Problem) using the techniques of E. Allender et al. [SIAM J. Comput. 47, No. 4, 1339–1372 (2018; Zbl 1397.68082)]. We also show that the problem is in \(\mathsf{ZPP}^{\mathrm{MKTP}}\) provided that there is a pac overestimator computable in \(\mathsf{ZPP}^{\mathrm{MKTP}}\) for the logarithm of the order of the input group. This last result implies that for permutation groups, the dihedral group and many types of matrix groups the problem is in \(\mathsf{ZPP}^{\mathrm{MKTP}}\). Lastly, we also show that two decision versions of the problem admit statistical zero knowledge proofs. These results help classify the relative difficulty of the Hidden Subgroup Problem.
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 20B35 | Subgroups of symmetric groups |
| 20E07 | Subgroup theorems; subgroup growth |
| 68Q30 | Algorithmic information theory (Kolmogorov complexity, etc.) |
Keywords:
hidden subgroup problem; NP-intermediate problems; statistical zero-knowledge; time-bounded Kolmogorov complexityCitations:
Zbl 1397.68082References:
| [1] | Allender, E.; Grochow, J.; van Melkebeek, D.; Moore, C.; Morgan, A., Minimum circuit size, graph isomorphism, and related problems, SIAM J. Comput., 47, 1339-1372 (2018) · Zbl 1397.68082 |
| [2] | Ladner, R. E., On the structure of polynomial time reducibility, J. ACM, 22, 155-171 (1975) · Zbl 0322.68028 |
| [3] | Shor, P. W., Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput., 26, 1484-1509 (1997) · Zbl 1005.11065 |
| [4] | Boneh, D.; Lipton, R. J., Quantum cryptanalysis of hidden linear functions, (Advances in Cryptology — CRYPT0’ 95 (1995)), 424-437 · Zbl 0876.94023 |
| [5] | Kempe, J.; Shalev, A., The hidden subgroup problem and permutation group theory, (Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (2005)), 1118-1125 · Zbl 1297.68077 |
| [6] | Roetteler, M., Quantum algorithms for abelian difference sets and applications to dihedral hidden subgroups, (11th Conference on the Theory of Quantum Computation, Communication and Cryptography. 11th Conference on the Theory of Quantum Computation, Communication and Cryptography, Leibniz International Proceedings in Informatics, vol. 61 (2016)), 8:1-8:16 · Zbl 1370.68103 |
| [7] | Kabanets, V.; Cai, J.-Y., Circuit minimization problem, (Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing (2000)), 73-79 · Zbl 1296.94182 |
| [8] | Allender, E.; Das, B., Zero knowledge and circuit minimization, Inf. Comput., 256, 2-8 (2017) · Zbl 1376.68056 |
| [9] | Allender, E.; Buhrman, H.; Koucký, M.; van Melkebeek, D.; Ronneburger, D., Power from random strings, SIAM J. Comput., 35, 1467-1493 (2006) · Zbl 1106.68049 |
| [10] | Rudow, M., Discrete logarithm and minimum circuit size, Inf. Process. Lett., 128, 1-4 (2017) · Zbl 1422.68141 |
| [11] | Vadhan, S. P., A Study of Statistical Zero-knowledge Proofs (1999), Massachusetts Institute of Technology, PhD thesis |
| [12] | Rotman, J., A First Course in Abstract Algebra: With Applications (2006), Pearson Prentice Hall |
| [13] | Goldwasser, S.; Micali, S.; Rackoff, C., The knowledge complexity of interactive proof systems, SIAM J. Comput., 18, 186-208 (1989) · Zbl 0677.68062 |
| [14] | Babai, L.; Szemeredi, E., On the complexity of matrix group problems I, (Proceedings of the 25th Annual Symposium on Foundations of Computer Science (1984)), 229-240 |
| [15] | Babai, L., Local expansion of vertex-transitive graphs and random generation in finite groups, (Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing (1991)), 164-174 |
| [16] | Fenner, S.; Zhang, Y., Quantum algorithms for a set of group theoretic problems, Int. J. Found. Comput. Sci., 26, 255-268 (2015) · Zbl 1322.68078 |
| [17] | Arvind, V.; Das, B., SZK proofs for black-box group problems, Theory Comput. Syst., 43, 100-117 (2008) · Zbl 1148.68020 |
| [18] | Arvind, V.; Vinodchandran, V., Solvable black-box group problems are low for PP, Theor. Comput. Sci., 180, 17-45 (1997) · Zbl 0901.68072 |
| [19] | Seress, Á., Permutation Group Algorithms, Cambridge Tracts in Mathematics (2003), Cambridge University Press · Zbl 1028.20002 |
| [20] | Fenner, S.; Zhang, Y., On the complexity of the hidden subgroup problem, Int. J. Found. Comput. Sci., 24, 1221-1234 (2013) · Zbl 1291.68170 |
| [21] | Babai, L.; Beals, R.; Seress, Á., Polynomial-time theory of matrix groups, (Proceedings of the Forty-First Annual ACM Symposium on Theory of computing (2009)), 55-64 · Zbl 1304.68065 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
