Paper 2022/1305 Original: eprint.iacr.org/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.
Metadata
- Available format(s)
PDF- Category
- Foundations
- Publication info
- Preprint.
- History
- 2022-10-01: last updated
- 2022-10-01: published
- Short URL
- https://ia.cr/2022/1305
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}