Paper 2010/511

On the complexity of Decomposition Attack

Koh-ichi Nagao

Abstract

In recent researches, it is discovered that index calculus is useful for solving the discrete logarithm problems (DLP) of the groups of the Jacobian of curves (including elliptic curve) over finite field, which are widely used to cryptosystems. In these cases, the probability that an element of the group is written by the summation of N elements of large primes and factor bases is O(1) where N is some pre-fixed constant. So the situation is little different to the normal index calculus and it is proposed that it should be called another name, ”decomposition attack”. In decomposition attack, first, some relations are collected and the graph, whose vertexes are the set of large primes and whose edges are the relations, is considered and the elimination of large prime is done by using this graph. However, in the proposed algorithm, the randomness of the graph, which is difficult to define, is needed. In this paper, we first formulate the decomposition attack and next propose a new algorithm, which does not require the randomness of the graph and its worst complexity can be estimated.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
Discrete logarithm problem
Contact author(s)
nagao @ kanto-gakuin ac jp
History
2010-12-11: revised
2010-10-07: received
See all versions
Short URL
https://ia.cr/2010/511
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/511,
      author = {Koh-ichi Nagao},
      title = {On the complexity of Decomposition Attack},
      howpublished = {Cryptology {ePrint} Archive, Paper 2010/511},
      year = {2010},
      url = {https://eprint.iacr.org/2010/511}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.