UZH-Logo

Maintenance Infos

Groups from cyclic infrastructures and Pohlig-Hellman in certain infrastructures


Fontein, F (2008). Groups from cyclic infrastructures and Pohlig-Hellman in certain infrastructures. Advances in Mathematics of Communications, 2(3):293-307.

Abstract

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üller, 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.

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üller, 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.

Citations

4 citations in Web of Science®
3 citations in Scopus®
Google Scholar™

Altmetrics

Downloads

129 downloads since deposited on 23 Oct 2008
21 downloads since 12 months
Detailed statistics

Additional indexing

Item Type:Journal Article, refereed, original work
Communities & Collections:07 Faculty of Science > Institute of Mathematics
Dewey Decimal Classification:510 Mathematics
Language:English
Date:August 2008
Deposited On:23 Oct 2008 15:54
Last Modified:05 Apr 2016 12:28
Publisher:American Institute of Mathematical Sciences
ISSN:1930-5338
Funders:Swiss National Science Foundation, grant no. 107887
Additional Information:First published in Advances in Mathematics of Communication in Volume 2, No. 3, 2008, 293–307, published by the American Institute of Mathematical Sciences and Shandong
Publisher DOI:10.3934/amc.2008.2.293
Official URL:http://aimsciences.org/journals/displayPapers1.jsp?pubID=255
Related URLs:http://arxiv.org/abs/0803.2123
Permanent URL: http://doi.org/10.5167/uzh-3683

Download

[img]
Preview
Filetype: PDF (Verlags-PDF)
Size: 1MB
View at publisher
[img]
Preview
Content: Accepted Version
Filetype: PDF (Accepted manuscript, Version 2)
Size: 244kB
[img]
Preview
Content: Accepted Version
Filetype: PDF (Accepted manuscript, Version 1)
Size: 233kB

TrendTerms

TrendTerms displays relevant terms of the abstract of this publication and related documents on a map. The terms and their relations were extracted from ZORA using word statistics. Their timelines are taken from ZORA as well. The bubble size of a term is proportional to the number of documents where the term occurs. Red, orange, yellow and green colors are used for terms that occur in the current document; red indicates high interlinkedness of a term with other terms, orange, yellow and green decreasing interlinkedness. Blue is used for terms that have a relation with the terms in this document, but occur in other documents.
You can navigate and zoom the map. Mouse-hovering a term displays its timeline, clicking it yields the associated documents.

Author Collaborations