Paper 2012/593

Factor-4 and 6 (De)compression for Values of Pairings using Trace Maps

Tomoko Yonemura, Taichi Isogai, Hirofumi Muratani, and Yoshikazu Hanatani

Abstract

The security of pairing-based cryptosystems relies on the hardness of the discrete logarithm problems in elliptic curves and in finite fields related to the curves, namely, their embedding fields. Public keys and ciphertexts in the pairing-based cryptosystems are composed of points on the curves or values of pairings. Although the values of the pairings belong to the embedding fields, the representation of the field is inefficient in size because the size of the embedding fields is usually larger than the size of the elliptic curves. We show factor-4 and 6 compression and decompression for the values of the pairings with the supersingular elliptic curves of embedding degrees 4 and 6, respectively. For compression, we use the fact that the values of the pairings belong to algebraic tori that are multiplicative subgroups of the embedding fields. The algebraic tori can be expressed by the affine representation or the trace representation. Although the affine representation allows decompression maps, decompression maps for the trace representation has not been known. In this paper, we propose a trace representation with decompression maps for the characteristics 2 and 3. We first construct efficient decompression maps for trace maps by adding extra information to the trace representation. Our decompressible trace representation with additional information is as efficient as the affine representation is in terms of the costs of compression, decompression and exponentiation, and the size.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Pairing 2012
Keywords
discrete logarithm problemalgebraic toricompressiondecompression
Contact author(s)
tomoko yonemura @ toshiba co jp
History
2012-10-25: received
Short URL
https://ia.cr/2012/593
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/593,
      author = {Tomoko Yonemura and Taichi Isogai and Hirofumi Muratani and Yoshikazu Hanatani},
      title = {Factor-4 and 6 (De)compression for Values of Pairings using Trace Maps},
      howpublished = {Cryptology ePrint Archive, Paper 2012/593},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/593}},
      url = {https://eprint.iacr.org/2012/593}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.