DLP in semigroups: Algorithms and lower bounds
The discrete logarithm problem (DLP) in semigroups has attracted some interests and serves as the foundation of many cryptographic schemes. In this work, we study algorithms and lower bounds for DLP in semigroups. First, we propose a variant of the deterministic algorithm for solving the cycle lengt...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
De Gruyter
2022-10-01
|
| Series: | Journal of Mathematical Cryptology |
| Subjects: | |
| Online Access: | https://doi.org/10.1515/jmc-2021-0049 |
| _version_ | 1828160471289561088 |
|---|---|
| author | Han Jiao Zhuang Jincheng |
| author_facet | Han Jiao Zhuang Jincheng |
| author_sort | Han Jiao |
| collection | DOAJ |
| description | The discrete logarithm problem (DLP) in semigroups has attracted some interests and serves as the foundation of many cryptographic schemes. In this work, we study algorithms and lower bounds for DLP in semigroups. First, we propose a variant of the deterministic algorithm for solving the cycle length of torsion elements and show the lower bound of computing the DLP in a semigroup. Then, we propose an algorithm for solving the multiple discrete logarithm (MDL) problem in the semigroup and give the lower bound for solving the MDL problem by considering the MDL problem in the generic semigroup model. Besides, we solve the multidimensional DLP and product DLP in the semigroup. |
| first_indexed | 2024-04-12T00:21:16Z |
| format | Article |
| id | doaj.art-74c44e5eef4a4b14b7b72a733e101b07 |
| institution | Directory Open Access Journal |
| issn | 1862-2984 |
| language | English |
| last_indexed | 2024-04-12T00:21:16Z |
| publishDate | 2022-10-01 |
| publisher | De Gruyter |
| record_format | Article |
| series | Journal of Mathematical Cryptology |
| spelling | doaj.art-74c44e5eef4a4b14b7b72a733e101b072022-12-22T03:55:43ZengDe GruyterJournal of Mathematical Cryptology1862-29842022-10-0116127828810.1515/jmc-2021-0049DLP in semigroups: Algorithms and lower boundsHan Jiao0Zhuang Jincheng1School of Cyber Science and Technology, Shandong University, Qingdao 266237, ChinaSchool of Cyber Science and Technology, Shandong University, Qingdao 266237, ChinaThe discrete logarithm problem (DLP) in semigroups has attracted some interests and serves as the foundation of many cryptographic schemes. In this work, we study algorithms and lower bounds for DLP in semigroups. First, we propose a variant of the deterministic algorithm for solving the cycle length of torsion elements and show the lower bound of computing the DLP in a semigroup. Then, we propose an algorithm for solving the multiple discrete logarithm (MDL) problem in the semigroup and give the lower bound for solving the MDL problem by considering the MDL problem in the generic semigroup model. Besides, we solve the multidimensional DLP and product DLP in the semigroup.https://doi.org/10.1515/jmc-2021-0049discrete logarithm problemsemigroupstorsion elementscycle lengthlower bounds11t7111y16 |
| spellingShingle | Han Jiao Zhuang Jincheng DLP in semigroups: Algorithms and lower bounds Journal of Mathematical Cryptology discrete logarithm problem semigroups torsion elements cycle length lower bounds 11t71 11y16 |
| title | DLP in semigroups: Algorithms and lower bounds |
| title_full | DLP in semigroups: Algorithms and lower bounds |
| title_fullStr | DLP in semigroups: Algorithms and lower bounds |
| title_full_unstemmed | DLP in semigroups: Algorithms and lower bounds |
| title_short | DLP in semigroups: Algorithms and lower bounds |
| title_sort | dlp in semigroups algorithms and lower bounds |
| topic | discrete logarithm problem semigroups torsion elements cycle length lower bounds 11t71 11y16 |
| url | https://doi.org/10.1515/jmc-2021-0049 |
| work_keys_str_mv | AT hanjiao dlpinsemigroupsalgorithmsandlowerbounds AT zhuangjincheng dlpinsemigroupsalgorithmsandlowerbounds |