International Association
for Cryptologic Research

It has been half a century since the first several NP-complete problems were discovered by Cook, Karp and Levin in the early 1970s. Till today, thousands of NP-complete problems have been found. Most of them are of combinatorial flavor. We discover new possibilities in purer mathematics and introduce more structures to the theory of computation. We propose a family of abstract problems related to the subset product problem. To describe hardness of abstract problems, we propose a new hardness notion called global-case hardness, which is stronger than worst-case hardness and incomparable with average-case hardness. It is about whether all prespecified subproblems of a problem are NP-hard. We prove that our problems are generally NP-hard in all/a wide range of unique factorization domains with efficient multiplication or all/a wide range of ideal class groups of Dedekind domains with efficient ideal multiplication.