Implementation of Cryptosystems Based on Tate Pairing
Tóm tắt
Tate pairings over elliptic curves are important in cryptography since they can be used to construct efficient identity-based cryptosystems, and their implementation dominantly determines the efficiencies of the cryptosystems. In this paper, the implementation of a cryptosystem is provided based on the Tate pairing over a supersingular elliptic curve of MOV degree 3. The implementation is primarily designed to re-use low-level codes developed in implementation of usual elliptic curve cryptosystems. The paper studies how to construct the underlying ground field and its extension to accelerate the finite field arithmetic, and presents a technique to speedup the time-consuming powering in the Tate pairing algorithm.
Tài liệu tham khảo
Shamir A. Identity based cryptosystems and signature schemes. In Advance in Cryptology-Crypto’84, Blakley GR, Chaum D (eds.), Berlin/Heidelberg: Springer-Verlag, 1985, pp.47–53.
Boneh D, Franklin M. Identity based encryption from the Weil pairing. In Advance in Cryptology-Crypto’2001, Kilian J (ed.), Berlin/Heidelberg: Springer-Verlag, 2001, pp.213–229.
Tao R, Chen S. An implementation of identity-based cryptosystems and signature schemes by finite automation public key cryptosystems. In Advance in Cryptology-Chinacrypt’92, Tao R, Li X, Pei D (eds.), Beijing: Science Press, 1992, pp.87–104. (in Chinese)
Sakai R, Ohgishi K, Kasahara M. Cryptosystems based on pairing. In Symposium on Cryptography and Information Security-SCIS’2000, Okinawa, Japan, Jan. 2000, pp.26–28.
Joux A. A one-round protocol for tripartite diffie-hellman. In Algorithm Number Theory Symposium-ANTS-IV, Bosma W (ed.), Berlin/Heidelberg: Springer-Verlag, 2000, pp.385–394.
Boneh D, Silverberg A. Applications of multilinear forms to cryptography. In Topics in Algebraic and Noncommutative Geometry–Proceedings in Memory of Ruth Michler, Melles G, Brasselet J, Kennedy G et al. (eds.), Contemporary Mathematics Series of American Mathematical Society, 2003, 324: 71–90.
Menezes A J, Okamoto T, Vanstone S A. Reducing elliptic curve logarithms to logarithms in a finite field. IEEE Trans. Information Theory, 1993, 39(5): 1639–1646.
Frey G, Ruck H G. A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves. Mathematics of Computation, 1994, 62(206): 865–874.
Miyaji A, Nakabayashi M, Takano S. New explicit conditions of elliptic curve traces for FR-reduction. IEICE Trans. Fundamentals, 2001, E84-A(5): 1234–1243.
Dupont R, Enge A, Morain F. Building curves with arbitrary small MOV degree over finite prime fields. Available at http://ePrint.iacr.org/2002/094 (Cryptology ePrint Archive, Report 2002/094).
Barreto P S L M, Lynn B, Scott M. Constructing elliptic curves with prescribed embedding degrees. In Third Workshop on Security in Communication Networks—SCN’2002, Yung M (ed.), Lecture Notes in Computer Science 2576, Springer-Verlag, 2003, pp.257–267.
Barreto P S L M, Kim H, Lynn B, Scott M. Efficient algorithms for pairing based cryptosystems. In Advance in Cryptology-Crypto’2002, Yung M (ed.), Berlin/Heidelberg: Springer-Verlag, 2002, pp.354–368.
Galbraith S D, Harrison K, Soldera D. Implementing the Tate pairing. In Algorithm Number Theory Symposium-ANTS-V, Kohel D R (ed.), Berlin/Heidelberg: Springer-Verlag, 2002, pp.324–337.
Harasawa R, Shikata J, Suzuki J, Imai H. Comparing the MOV and FR reductions in elliptic curve cryptography. In Advance in Cryptology-Eurocrypto’97, Fumy W (ed.), Berlin/Heidelberg, Springer-Verlag, 1997, pp.190–205.
Verheul E R. Evidence that XTR is more secure than supersingular elliptic curve cryptosystems. In Advance in Cryptology-Eurocrypt’2001, Pfitzmann B (ed.), Berlin/Heidelberg: Springer-Verlag, 2001, pp.195–210.
Joux A. The Weil and Tate pairings as building blocks for public key cryptosystems. In Algorithm Number Theory Symposium-ANTS-V, Kohel D R (ed.), Berlin/Heidelberg: Springer-Verlag, 2002, pp.20–32.
Miller V. Short programs for functions on curves. Unpublished manuscript, 1986. Available at http://crypto. stanford.edu.cn/miller/miller.pdf