Paper 2022/1305

Subset Product with Errors over Unique Factorization Domains and Ideal Class Groups of Dedekind Domains

Trey Li
Abstract

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.

Note: This is the 1st paper of the series.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
Subset product with errors Global-case hardness General NP-hardness Gaussian-predictability Embedding Reduction
Contact author(s)
treyquantum @ gmail com
History
2022-10-03: approved
2022-10-01: received
See all versions
Short URL
https://ia.cr/2022/1305
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1305,
      author = {Trey Li},
      title = {Subset Product with Errors over Unique Factorization Domains and Ideal Class Groups of Dedekind Domains},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1305},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1305}},
      url = {https://eprint.iacr.org/2022/1305}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.