The Hidden Subgroup Problem and Non-interactive Perfect Zero-Knowledge Proofs - Costa, Abner F. B.; Hepp, Henrique; Silva, Murilo V. G. da; Zatesko, Leandro M. (Anais do Encontro de Teoria da Computação (ETC); 2023: Anais do VIII Encontro de Teoria da ComputaçãoDO - 10.5753/etc.2023.230017, 2023)
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 1 (i.e. NIPZK with perfect completeness). As a second contribution, we show that NIPZK 1 has a complete promise problem that is a restricted version of a complete promise problem for the NIPZK class.