A More Compact Representation of XTR Cryptosystem

Masaaki SHIRASE  Dong-Guk HAN  Yasushi HIBINO  Howon KIM  Tsuyoshi TAKAGI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E91-A   No.10   pp.2843-2850
Publication Date: 2008/10/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e91-a.10.2843
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Information Theory and Its Applications)
Category: Cryptography and Information Security
cryptography,  XTR cryptosystem,  finite field,  efficient implementation,  compact representation,  

Full Text: PDF(263.2KB)>>
Buy this Article

XTR is one of the most efficient public-key cryptosystems that allow us to compress the communication bandwidth of their ciphertext. The compact representation can be achieved by deploying a subgroup Fq2 of extension field Fq6, so that the compression ratio of XTR cryptosystem is 1/3. On the other hand, Dijk et al. proposed an efficient public-key cryptosystem using a torus over Fq30 whose compression ratio is 4/15. It is an open problem to construct an efficient public-key cryptosystem whose compression ratio is smaller than 4/15. In this paper we propose a new variant of XTR cryptosystem over finite fields with characteristic three whose compression ratio is 1/6. The key observation is that there exists a trace map from Fq6 to Fq in the case of characteristic three. Moreover, the cost of compression and decompression algorithm requires only about 1% overhead compared with the original XTR cryptosystem. Therefore, the proposed variant of XTR cryptosystem is one of the fastest public-key cryptosystems with the smallest compression ratio.