The Hidden Subgroup Problem and Non-interactive Perfect Zero-Knowledge Proofs

• Abner F. B. Costa UFPR
• Henrique Hepp UFPR
• Murilo V. G. da Silva UFPR
• Leandro M. Zatesko UTFPR

DOI: https://doi.org/10.5753/etc.2023.230017

Resumo

The Hidden Subgroup Problem (HSP) generalises many problems that are candidates to be NP-intermediate. It was shown that the decision version of HSP belongs to the zero-knowledge complexity class HVPZK and that, if the size of the group is known, it also belongs to NISZK. We show that whenever we can sample uniformly at random elements of the group and of a set, with the same size of the group, that contains the image of the function that hides the subgroup, the problem is in NIPZK₁ (i.e. NIPZK with perfect completeness). As a second contribution, we show that NIPZK₁ has a complete promise problem that is a restricted version of a complete promise problem for the NIPZK class.

Referências

Arora, S. and Barak, B. (2009). Computational complexity: a modern approach. Cambridge University Press.

Babai, L. and Szemerédi, E. (1984). On the complexity of matrix group problems I. In 25th Annual Symposium on Foundations of Computer Science, 1984, pages 229–240. IEEE.

Dixon, P., Gayen, S., Pavan, A., and Vinodchandran, N. (2020). Perfect zero knowledge: New upperbounds and relativized separations. In Theory of Cryptography: 18th International Conference, TCC 2020, Durham, NC, USA, November 16–19, 2020, Proceedings, Part I, pages 684–704. Springer.

Ettinger, M., Høyer, P., and Knill, E. (2004). The quantum query complexity of the hidden subgroup problem is polynomial. Information Processing Letters, 91(1):43–48.

Hayashi, M., Kawachi, A., and Kobayashi, H. (2008). Quantum measurements for hidden subgroup problems with optimal sample complexity. Quantum Information & Computation, 8(3):345–358.

Herstein, I. N. (1991). Topics in algebra. John Wiley & Sons.

Jozsa, R. (2001). Quantum factoring, discrete logarithms, and the hidden subgroup problem. Computing in science & engineering, 3(2):34–43.

Malka, L. (2008). How to achieve perfect simulation and a complete problem for non-interactive perfect zero-knowledge. In Theory of Cryptography: Fifth Theory of Cryptography Conference, TCC 2008, New York, USA, March 19-21, 2008. Proceedings 5, pages 89–106. Springer.

Regev, O. (2004). Quantum computation and lattice problems. SIAM Journal on Computing, 33(3):738–760.

Sdroievski, N. M., da Silva, M. V., and Vignatti, A. L. (2019). The hidden subgroup problem and MKTP. Theoretical Computer Science, 795:204–212.

Seress, Á. (2003). Permutation group algorithms. Number 152. Cambridge University Press.

Shor, P. W. (1994). Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th annual symposium on foundations of computer science, pages 124–134. IEEE.