What question did this study set out to answer?

The aim is to investigate the Self-Exponent Problem (SEP) and its computational hardness compared to other problems.

January 27, 20260 citationsOpen Access

The Self-Exponent Problem: A New Computationally Hard Problem

Key Points

The aim is to investigate the Self-Exponent Problem (SEP) and its computational hardness compared to other problems.
Defined the Self-Exponent Problem within the context of cyclic groups.
Proved that SEP needs Ω(N) group operations in the Generic Group Model.
Analyzed resistance of SEP to various known attacks such as Baby-Step Giant-Step and Index Calculus.
SEP is √N harder than the discrete logarithm problem.
Demonstrated strong resistance to standard cryptographic attacks, enhancing security for applications.
Discussed potential implications for proof-of-work systems in cryptography.

Abstract

We introduce the Self-Exponent Problem (SEP): given a cyclic group G = ⟨g⟩ of order N and a target value b ∈ ℤN, find a ∈ ℤN such that a·gᵃ ≡ b (mod N). We prove that SEP requires Ω (N) group operations in the Generic Group Model, making it √N harder than the discrete logarithm problem. We systematically analyze resistance to known attacks including Baby-Step Giant-Step, Pohlig-Hellman, Index Calculus, and lattice methods. Applications to proof-of-work systems are discussed.

问 AI

Bookmark

View Full Paper

Cite This Study

Aliaksei Naboko (Sun,) studied this question.

synapsesocial.com/papers/69785538ccb046adae517726 https://doi.org/https://doi.org/10.5281/zenodo.18368423