Paper 2022/1344
Discrete Exponential Equations and Noisy Systems
Abstract
The history of equations dates back to thousands of years ago, though the equals sign "=" was only invented in 1557. We formalize the processes of "decomposition" and "restoration" in mathematics and physics by defining "discrete exponential equations" and "noisy equation systems" over an abstract structure called a "land", which is more general than fields, rings, groups, and monoids. Our abstract equations and systems provide general languages for many famous computational problems such as integer factorization, ideal factorization, isogeny factorization, learning parity with noise, learning with errors, learning with rounding, etc. From the abstract equations and systems we deduce a list of new decomposition problems and noisy learning problems. We also give algorithms for discrete exponential equations and systems over algebraic integers. Our motivations are to develop a theory of decomposition and restoration; to unify the scattered studies of decomposition problems and noisy learning problems; and to further permeate the ideas of decomposition and restoration into all possible branches of mathematics. A direct application is a methodology for finding new hardness assumptions for cryptography.
Note: This is the 8th paper of the series.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- Discrete exponential equation Noisy system Noisy problem Decomposition Factorization Inverse problem Cryptography
- Contact author(s)
- treyquantum @ gmail com
- History
- 2022-10-14: approved
- 2022-10-08: received
- See all versions
- Short URL
- https://ia.cr/2022/1344
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/1344,
author = {Trey Li},
title = {Discrete Exponential Equations and Noisy Systems},
howpublished = {Cryptology ePrint Archive, Paper 2022/1344},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/1344}},
url = {https://eprint.iacr.org/2022/1344}
}
