Towards factoring in SL(2,2n

Christophe Petit*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

The security of many cryptographic protocols relies on the hardness of some computational problems. Besides discrete logarithm or integer factorization, other problems are regularly proposed as potential hard problems. The factorization problem in finite groups is one of them. Given a finite group G, a set of generators generators for this group and an element g ∈ G, the factorization problem asks for a "short" representation of g as a product of the generators. The problem is related to a famous conjecture of Babai on the diameter of Cayley graphs. It is also motivated by the preimage security of Cayley hash functions, a particular kind of cryptographic hash functions. The problem has been solved for a few particular generator sets, but essentially nothing is known for generic generator sets. In this paper, we make significant steps towards a solution of the factorization problem in the group G: = SL(2,2n, a particularly interesting group for cryptographic applications. To avoid considering all generator sets separately, we first give a new reduction tool that allows focusing on some generator sets with a "nice" special structure. We then identify classes of trapdoor matrices for these special generator sets, such that the factorization of a single one of these matrices would allow efficiently factoring any element in the group. Finally, we provide a heuristic subexponential time algorithm that can compute subexponential length factorizations of any element for any pair of generators of SL(2,2n. Our results do not yet completely remove the factorization problem in SL(2,2nfrom the list of potential hard problems useful for cryptography. However, we believe that each one of our individual results is a significant step towards a polynomial time algorithm for factoring in SL(2,2n.

Original languageEnglish
Pages (from-to)409-431
Number of pages23
JournalDesigns, Codes, and Cryptography
Volume71
Issue number3
DOIs
Publication statusPublished - Jun 2014

Bibliographical note

Funding Information:
Christophe Petit is a Postdoctoral Research Fellow of the Belgian Fund for Scientific Research (F.R.S.-FNRS) at Université catholique de Louvain (UCL), crypto group.

Keywords

  • Algorithmic group theory/number theory
  • Babai's conjecture
  • Cryptographic hash functions

ASJC Scopus subject areas

  • Computer Science Applications
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Towards factoring in SL(2,2n'. Together they form a unique fingerprint.

Cite this