Hard Instances of Discrete Logarithm Problem and Cryptographic Applications
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915638668165120 |
|---|---|
| author | Battarbee, Christopher Darbinyan, Arman Kahrobaei, Delaram |
| author_facet | Battarbee, Christopher Darbinyan, Arman Kahrobaei, Delaram |
| contents | Let f be an arbitrary positive integer valued function. The goal of this note is to show that one can construct a finitely generated group in which the discrete log problem is polynomially equivalent to computing the function f. In particular, we provide infinite, but finitely generated groups, in which the discrete logarithm problem is arbitrarily hard. As another application, we construct a family of two-generated groups that have polynomial time word problem and NP-complete discrete log problem. Additionally, using our framework, we propose a generic scheme of cryptographic protocols, which might be of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_08823 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Hard Instances of Discrete Logarithm Problem and Cryptographic Applications Battarbee, Christopher Darbinyan, Arman Kahrobaei, Delaram Group Theory 20K15, 94A60, 03D15 Let f be an arbitrary positive integer valued function. The goal of this note is to show that one can construct a finitely generated group in which the discrete log problem is polynomially equivalent to computing the function f. In particular, we provide infinite, but finitely generated groups, in which the discrete logarithm problem is arbitrarily hard. As another application, we construct a family of two-generated groups that have polynomial time word problem and NP-complete discrete log problem. Additionally, using our framework, we propose a generic scheme of cryptographic protocols, which might be of independent interest. |
| title | Hard Instances of Discrete Logarithm Problem and Cryptographic Applications |
| topic | Group Theory 20K15, 94A60, 03D15 |
| url | https://arxiv.org/abs/2508.08823 |