American Institute of Mathematical Sciences

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] 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 [4] 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 [5] 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 [6] 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 [7] Yuri Latushkin, Alim Sukhtayev. The Evans function and the Weyl-Titchmarsh function. Discrete & Continuous Dynamical Systems - S, 2012, 5 (5) : 939-970. doi: 10.3934/dcdss.2012.5.939 [8] Martin Swaczyna, Petr Volný. Uniform motions in central fields. Journal of Geometric Mechanics, 2017, 9 (1) : 91-130. doi: 10.3934/jgm.2017004 [9] Leonardo Câmara, Bruno Scárdua. On the integrability of holomorphic vector fields. Discrete & Continuous Dynamical Systems - A, 2009, 25 (2) : 481-493. doi: 10.3934/dcds.2009.25.481 [10] Jifeng Chu, Zhaosheng Feng, Ming Li. Periodic shadowing of vector fields. Discrete & Continuous Dynamical Systems - A, 2016, 36 (7) : 3623-3638. doi: 10.3934/dcds.2016.36.3623 [11] 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 [12] Hassan Emamirad, Philippe Rogeon. Semiclassical limit of Husimi function. Discrete & Continuous Dynamical Systems - S, 2013, 6 (3) : 669-676. doi: 10.3934/dcdss.2013.6.669 [13] Ken Ono. Parity of the partition function. Electronic Research Announcements, 1995, 1: 35-42. [14] Tomasz Downarowicz, Yonatan Gutman, Dawid Huczek. Rank as a function of measure. Discrete & Continuous Dynamical Systems - A, 2014, 34 (7) : 2741-2750. doi: 10.3934/dcds.2014.34.2741 [15] Rainer Buckdahn, Ingo Bulla, Jin Ma. Pathwise Taylor expansions for Itô random fields. Mathematical Control & Related Fields, 2011, 1 (4) : 437-468. doi: 10.3934/mcrf.2011.1.437 [16] BronisŁaw Jakubczyk, Wojciech Kryński. Vector fields with distributions and invariants of ODEs. Journal of Geometric Mechanics, 2013, 5 (1) : 85-129. doi: 10.3934/jgm.2013.5.85 [17] Rafael Ayala, Jose Antonio Vilches, Gregor Jerše, Neža Mramor Kosta. Discrete gradient fields on infinite complexes. Discrete & Continuous Dynamical Systems - A, 2011, 30 (3) : 623-639. doi: 10.3934/dcds.2011.30.623 [18] Jürgen Scheurle, Stephan Schmitz. A criterion for asymptotic straightness of force fields. Discrete & Continuous Dynamical Systems - B, 2010, 14 (2) : 777-792. doi: 10.3934/dcdsb.2010.14.777 [19] Alexander Gorodnik. Open problems in dynamics and related fields. Journal of Modern Dynamics, 2007, 1 (1) : 1-35. doi: 10.3934/jmd.2007.1.1 [20] Giovanni Colombo, Khai T. Nguyen. On the minimum time function around the origin. Mathematical Control & Related Fields, 2013, 3 (1) : 51-82. doi: 10.3934/mcrf.2013.3.51

2017 Impact Factor: 0.564