zbMATH — the first resource for mathematics

A comparison of MNT curves and supersingular curves. (English) Zbl 1134.94377
Summary: We compare both the security and performance issues related to the choice of MNT curves against supersingular curves in characteristic three, for pairing based systems. We pay particular attention to equating the relevant security levels and comparing not only computational performance and bandwidth performance. The paper focuses on the BLS signature scheme and the Boneh-Franklin encryption scheme, but a similar analysis can be applied to many other pairing based schemes.

94A62 Authentication, digital signatures and secret sharing
68P25 Data encryption (aspects in computer science)
14G50 Applications to coding theory and cryptography of arithmetic geometry
Full Text: DOI
[1] Al-Riyami, S.S., Malone-Lee, J., Smart, N.P.: Escrow-free encryption supporting cryptographic workflow. To appear Int. J. Inf. Sec. (to appear) · Zbl 1312.94027
[2] Barreto, P.S.L.M., Naehrig, M.: Pairing-friendly elliptic curves of prime order. In: Selected Areas in Cryptography – SAC 2005, pp. 319–331. Springer-Verlag LNCS 3897 (2006) · Zbl 1151.94479
[3] Barreto, P.S.L.M., Kim, H.Y., Lynn, B., Scott, M.: Efficient algorithms for pairing-based cryptosystems. In: Advances in Cryptology – CRYPTO 2002, pp. 354–369. Springer LNCS 2442 (2002) · Zbl 1026.94520
[4] Barreto, P.S.L.M., Lynn, B., Scott, M.: On the Selection of Pairing-Friendly Groups. In: Selected Areas in Cryptography – SAC 2004, pp. 17–25. Springer-Verlag LNCS 3006 (2004) · Zbl 1081.94016
[5] Boneh, D., Boyen, X.: Short signatures without random oracles. In: Advances in Cryptology – EUROCRYPT 2004, pp. 56–73. Springer LNCS 3027 (2001) · Zbl 1122.94354
[6] Boneh, D., Franklin, M.: Identity based encryption from the Weil pairing. In: Advances in Cryptology – CRYPTO 2001, pp. 213–229. Springer LNCS 2139 (2001) · Zbl 1002.94023
[7] Boneh, D., Lynn, B., Shacham, H.: Short signatures from the Weil pairing. In: Advances in Cryptology – ASIACRYPT 2001, pp. 514–532. Springer LNCS 2248 (2001) · Zbl 1064.94554
[8] Boneh, D., Boyen, X., Shacham, H.: Short group signatures. In: Advances in Cryptology – CRYPTO 2004, pp. 41–55. Springer LNCS 3152 (2004) · Zbl 1104.94044
[9] Coppersmith, D.: Evaluating logarithms in GF(2 n ). In: STOC 1984, pp. 201–207 (1983)
[10] Duursma, I., Lee, H.-S.: Tate pairing implementation for hyperelliptic curves y 2 = x p x + d. In: Advances in Cryptology – ASIACRYPT 2003, pp. 111–222. Springer LNCS 2894 (2003) · Zbl 1189.11056
[11] Galbraith, S., Harrison, K., Soldera, S.: Implementing the Tate pairing. In: Algorithmic Number Theory Symposium – ANTS V, pp. 324–337. Springer LNCS 2369 (2002) · Zbl 1058.11072
[12] Granger, R., Holt, A., Page, D., Smart, N.P., Vercauteren, F.: Function field sieve in Characteristic three.In: Algorithmic Number Theory Symposium - ANTS VI, pp. 223–234. Springer LNCS 3076 (2004) · Zbl 1125.11358
[13] Harrison, K., Page, D., Smart, N.P.: Software implementation of finite fields of characteristic three, for use in pairing based cryptosystems. In: LMS Journal of Computation and Mathematics, London. vol 5 (1), pp. 181–193. London Mathematical Society, London (2002) · Zbl 1068.94012
[14] Izu, T., Takagi, T.: Efficient computations of the Tate pairing for the large MOV degrees. In: International Conference on Information Security and Cryptology – ICISC 2002, pp. 283–297. Springer LNCS 2587 (2003) · Zbl 1029.11017
[15] Joux, A.: A one round protocol for tripartite Diffie–Hellman. In: Algorithmic Number Theory Symposium – ANTS IV, pp. 385–394. Springer LNCS 1838 (2000) · Zbl 1029.94026
[16] Joux, A., Lercier, R.: The function field sieve is quite special. In: Algorithmic Number Theory Symposium – ANTS V, pp. 431–445. Springer LNCS 2369 (2002) · Zbl 1057.11069
[17] Lercier, R.: Discrete logarithms in GF(p). Posting to NMBRTHRY List (2001)
[18] Li, N., Du, W., Boneh, D.:Oblivious signature-based envelope. In: 22nd ACM Symposium on Principles of Distributed Computing (PODC), pp. 182–189 (2003) · Zbl 1264.94101
[19] Miyaji, A., Nakabayashi, M., Takano, S.: New explicit conditions of elliptic curve traces for FR-reduction. IEICE Trans. Fundam. E84-A(5), pp. 1234–1243 (2001) · Zbl 0990.94024
[20] Miller, V.: Short programs for functions on curves. Unpublished manuscript (1986)
[21] Robertson, J.: Solving the generalized Pell equation. Available at http://hometown.aol.com/ jpr2718/
[22] Sakai, R., Ohgishi, K., Kasahara, M.: Cryptosystems based on pairings. In: Proceedings of SCIS 2000 (2000)
[23] Sakai, R., Ohgishi, K., Kasahara, M.: Cryptosystems based on pairings over elliptic curves. In: Proceedings of SCIS 2001 (2001)
[24] Schirokauer, O: Using number fields to compute logarithms in finite fields. Math. Comp. 69, pp. 1267–1283 (2000) · Zbl 1042.11085
[25] Scott, M.: Complex multiplication program. Available at ftp.compapp.dcu.ie/pub/crypto/cm.exe
[26] Scott, M., Barreto, P.S.L.M.: Generating more MNT elliptic curves. In: Cryptology ePrint Archive, Report 2004/058 (2004) · Zbl 1172.14309
[27] ThomĂ©, E.: Computation of discrete logarithms in GF(2607). In: Advances in Cryptology – ASIACRYPT 2001, pp. 107–124. Springer LNCS 2248 (2001) · Zbl 1062.11080
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.