Anzeige
Erschienen in:
2014 | OriginalPaper | Buchkapitel
A Generic Algorithm for Small Weight Discrete Logarithms in Composite Groups
verfasst von : Alexander May, Ilya Ozerov
Erschienen in: Selected Areas in Cryptography -- SAC 2014
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Let \((\mathbb {G},\cdot )\) be an arbitrary cyclic group of composite order \(N\) with \(\mathbb {G}\simeq \mathbb {G}_1 \times \mathbb {G}_2\). We present a generic algorithm for solving the discrete logarithm problem in \(\mathbb {G}\) with Hamming weight \(\delta \log N\), \(\delta \in (0,1)\), in time \(\widetilde{O}(\sqrt{p} + \sqrt{|\mathbb {G}_2|}^{H(\delta )})\), where \(p\) is the largest prime divisor in \(\mathbb {G}_1\) and \(H(\cdot )\) is the binary entropy function.
Our algorithm improves on the running time of Silver-Pohlig-Hellman’s algorithm whenever \(\delta \not = \frac{1}{2}\). Moreover, it improves on the Meet-in-the-Middle type algorithms of Heiman, Odlyzko and Coppersmith with running time \(\widetilde{O}(\sqrt{|\mathbb {G}|}^{H(\delta )})\) whenever \(p < |\mathbb {G}|^{H(\delta )}\).