Paper 2022/1305
Subset Product with Errors over Unique Factorization Domains and Ideal Class Groups of Dedekind Domains
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
-
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},
url = {https://eprint.iacr.org/2022/1305}
}
