# American Institute of Mathematical Sciences

August  2008, 2(3): 293-307. doi: 10.3934/amc.2008.2.293

## Groups from cyclic infrastructures and Pohlig-Hellman in certain infrastructures

 1 Institut für Mathematik, Universität Zürich, CH-8057, Switzerland

Received  March 2008 Revised  July 2008 Published  July 2008

In discrete logarithm based cryptography, a method by Pohlig and Hellman allows solving the discrete logarithm problem efficiently if the group order is known and has no large prime factors. The consequence is that such groups are avoided. In the past, there have been proposals for cryptography based on cyclic infrastructures. We will show that the Pohlig-Hellman method can be adapted to certain cyclic infrastructures, which similarly implies that certain infrastructures should not be used for cryptography. This generalizes a result by M¨uller, Vanstone and Zuccherato for infrastructures obtained from hyperelliptic function fields.
We recall the Pohlig-Hellman method, define the concept of a cyclic infrastructure and briefly describe how to obtain such infrastructures from certain function fields of unit rank one. Then, we describe how to obtain cyclic groups from discrete cyclic infrastructures and how to apply the Pohlig-Hellman method to compute absolute distances, which is in general a computationally hard problem for cyclic infrastructures. Moreover, we give an algorithm which allows to test whether an infrastructure satisfies certain requirements needed for applying the Pohlig-Hellman method, and discuss whether the Pohlig-Hellman method is applicable in infrastructures obtained from number fields. Finally, we discuss how this influences cryptography based on cyclic infrastructures.
Citation: Felix Fontein. Groups from cyclic infrastructures and Pohlig-Hellman in certain infrastructures. Advances in Mathematics of Communications, 2008, 2 (3) : 293-307. doi: 10.3934/amc.2008.2.293
 [1] Florian Luca, Igor E. Shparlinski. On finite fields for pairing based cryptography. Advances in Mathematics of Communications, 2007, 1 (3) : 281-286. doi: 10.3934/amc.2007.1.281 [2] Laurent Imbert, Michael J. Jacobson, Jr., Arthur Schmidt. Fast ideal cubing in imaginary quadratic number and function fields. Advances in Mathematics of Communications, 2010, 4 (2) : 237-260. doi: 10.3934/amc.2010.4.237 [3] Rakhi Pratihar, Tovohery Hajatiana Randrianarisoa. Constructions of optimal rank-metric codes from automorphisms of rational function fields. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022034 [4] Diego F. Aranha, Ricardo Dahab, Julio López, Leonardo B. Oliveira. Efficient implementation of elliptic curve cryptography in wireless sensors. Advances in Mathematics of Communications, 2010, 4 (2) : 169-187. doi: 10.3934/amc.2010.4.169 [5] Andreas Klein. How to say yes, no and maybe with visual cryptography. Advances in Mathematics of Communications, 2008, 2 (3) : 249-259. doi: 10.3934/amc.2008.2.249 [6] Gerhard Frey. Relations between arithmetic geometry and public key cryptography. Advances in Mathematics of Communications, 2010, 4 (2) : 281-305. doi: 10.3934/amc.2010.4.281 [7] Jintai Ding, Sihem Mesnager, Lih-Chung Wang. Letters for post-quantum cryptography standard evaluation. Advances in Mathematics of Communications, 2020, 14 (1) : i-i. doi: 10.3934/amc.2020012 [8] Gérard Maze, Chris Monico, Joachim Rosenthal. Public key cryptography based on semigroup actions. Advances in Mathematics of Communications, 2007, 1 (4) : 489-507. doi: 10.3934/amc.2007.1.489 [9] Anna-Lena Horlemann-Trautmann, Violetta Weger. Information set decoding in the Lee metric with applications to cryptography. Advances in Mathematics of Communications, 2021, 15 (4) : 677-699. doi: 10.3934/amc.2020089 [10] Lidong Chen, Dustin Moody. New mission and opportunity for mathematics researchers: Cryptography in the quantum era. Advances in Mathematics of Communications, 2020, 14 (1) : 161-169. doi: 10.3934/amc.2020013 [11] Javier de la Cruz, Ricardo Villanueva-Polanco. Public key cryptography based on twisted dihedral group algebras. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022031 [12] Alar Leibak. On the number of factorizations of $t$ mod $N$ and the probability distribution of Diffie-Hellman secret keys for many users. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021029 [13] Ramprasad Sarkar, Mriganka Mandal, Sourav Mukhopadhyay. Quantum-safe identity-based broadcast encryption with provable security from multivariate cryptography. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022026 [14] Martin Swaczyna, Petr Volný. Uniform motions in central fields. Journal of Geometric Mechanics, 2017, 9 (1) : 91-130. doi: 10.3934/jgm.2017004 [15] Leonardo Câmara, Bruno Scárdua. On the integrability of holomorphic vector fields. Discrete and Continuous Dynamical Systems, 2009, 25 (2) : 481-493. doi: 10.3934/dcds.2009.25.481 [16] Jifeng Chu, Zhaosheng Feng, Ming Li. Periodic shadowing of vector fields. Discrete and Continuous Dynamical Systems, 2016, 36 (7) : 3623-3638. doi: 10.3934/dcds.2016.36.3623 [17] Yuri Latushkin, Alim Sukhtayev. The Evans function and the Weyl-Titchmarsh function. Discrete and Continuous Dynamical Systems - S, 2012, 5 (5) : 939-970. doi: 10.3934/dcdss.2012.5.939 [18] J. William Hoffman. Remarks on the zeta function of a graph. Conference Publications, 2003, 2003 (Special) : 413-422. doi: 10.3934/proc.2003.2003.413 [19] H. N. Mhaskar, T. Poggio. Function approximation by deep networks. Communications on Pure and Applied Analysis, 2020, 19 (8) : 4085-4095. doi: 10.3934/cpaa.2020181 [20] Hassan Emamirad, Philippe Rogeon. Semiclassical limit of Husimi function. Discrete and Continuous Dynamical Systems - S, 2013, 6 (3) : 669-676. doi: 10.3934/dcdss.2013.6.669

2020 Impact Factor: 0.935