Using abelian varieties to improve pairing-based cryptography. (English) Zbl 1170.94013
In this long and quite technical paper the authors study several aspects of Pairing-Based Cryptography.
Bilinear pairings (Weil and Tate pairings) on elliptic curves or higher dimensional abelian varieties are used in Cryptography both in a constructive and destructive way, see [Handbook of elliptic and hyperelliptic curve cryptography. Boca Raton, FL: Chapman & Hall/CRC (2006; Zbl 1082.94001)]. In particular, given an abelian variety \(A\) defined over the finite field \(\mathbb{F}_q, q=p^n\), a prime \(l\neq p\) and a point \(0\neq P\in A(\mathbb{F}_q)[l]\), the algorithms of A. Menezes, T. Okamoto and S. A. Vanstone (MOV) [IEEE Trans. Inf. Theory 39, No. 5, 1639–1646 (1993; Zbl 0801.94011)] and of G. Frey and H.-G. Rück [Math. Comput. 62, No. 206, 865–874 (1994; Zbl 0813.14045)] allow to reduce the discrete logarithm problem in the cyclic group \(<P>\) to the same problem in the field \(\mathbb{F}_{q^k}\), where \(k\), called the embedding degree, is the multiplicative order of \(q\) modulo \(l\). Such embedding degree should be neither too small (to avoid MOV-like attacks) nor too large (for computational reasons). For this and other motivations supersingular varieties are usually used in Pairing-Based Cryptography.
The paper (Section 4) introduces two new invariants: the cryptographic exponent \(c_{A,q}\) and the security parameter \(\alpha(A,q)\). The authors argue that the cryptographic exponent (a number in \(1/2Z\)) is a better security measure than the embedding degree: theorem 6.3 shows that for an elementary supersingular abelian variety and \(l\) large enough \(\mathbb{F}_{q^{c_{A,q}}}\) is the smallest extension of \(\mathbb{F}_p\) whose multiplicative group contains the \(l-th\)-roots of unity. The security parameter \(\alpha(A,q)=c_{A,q}/\dim(A)\), measures MOV security per bit and allows to compare security among abelian varieties of different dimension. Section 7 determines which values can occur as the security parameters. The results are also collected in Table 1 (Section 1) and show that it is possible to obtain higher MOV security per bit than using supersingular elliptic curves.
The authors also discuss (Section 9) the cryptographic security of primitive subgroups \(V_{q^r|q}\) of the Weil restriction of scalars. They prove that given a supersingular elliptic curve \(E\) defined over \(\mathbb{F}_q\) and a suitable prime \(r\) there exists an abelian variety \(E_r\) over \(\mathbb{F}_q\) (the \(rth\) primitive subgroup) with security parameter better, by a factor \(r/(r-1)\), than the parameter of \(E\). If \(A_0\) denotes the trace zero subgroup of \(E(\mathbb{F}_{q^r})\) then \(E_r(\mathbb{F}_q)\cong A_0\subseteq E(\mathbb{F}_{q^r})\). Section 10 gives a compression/decompression algorithm for the points of \(A_0\) which compresses by a factor of \(r/(r-1)\). The algorithm is efficient when \(r=3, p\neq 3\) (Section 10.3) and \(r=5, p=3\) (Section 10.4) .
Section 12, keeping in mind the results of Table 1, constructs explicit examples of optimal abelian varieties (varieties with the highest \(c_{A,q}\) among abelian varieties of the same dimension) for those dimensions providing the highest MOV security per bit.
Bilinear pairings (Weil and Tate pairings) on elliptic curves or higher dimensional abelian varieties are used in Cryptography both in a constructive and destructive way, see [Handbook of elliptic and hyperelliptic curve cryptography. Boca Raton, FL: Chapman & Hall/CRC (2006; Zbl 1082.94001)]. In particular, given an abelian variety \(A\) defined over the finite field \(\mathbb{F}_q, q=p^n\), a prime \(l\neq p\) and a point \(0\neq P\in A(\mathbb{F}_q)[l]\), the algorithms of A. Menezes, T. Okamoto and S. A. Vanstone (MOV) [IEEE Trans. Inf. Theory 39, No. 5, 1639–1646 (1993; Zbl 0801.94011)] and of G. Frey and H.-G. Rück [Math. Comput. 62, No. 206, 865–874 (1994; Zbl 0813.14045)] allow to reduce the discrete logarithm problem in the cyclic group \(<P>\) to the same problem in the field \(\mathbb{F}_{q^k}\), where \(k\), called the embedding degree, is the multiplicative order of \(q\) modulo \(l\). Such embedding degree should be neither too small (to avoid MOV-like attacks) nor too large (for computational reasons). For this and other motivations supersingular varieties are usually used in Pairing-Based Cryptography.
The paper (Section 4) introduces two new invariants: the cryptographic exponent \(c_{A,q}\) and the security parameter \(\alpha(A,q)\). The authors argue that the cryptographic exponent (a number in \(1/2Z\)) is a better security measure than the embedding degree: theorem 6.3 shows that for an elementary supersingular abelian variety and \(l\) large enough \(\mathbb{F}_{q^{c_{A,q}}}\) is the smallest extension of \(\mathbb{F}_p\) whose multiplicative group contains the \(l-th\)-roots of unity. The security parameter \(\alpha(A,q)=c_{A,q}/\dim(A)\), measures MOV security per bit and allows to compare security among abelian varieties of different dimension. Section 7 determines which values can occur as the security parameters. The results are also collected in Table 1 (Section 1) and show that it is possible to obtain higher MOV security per bit than using supersingular elliptic curves.
The authors also discuss (Section 9) the cryptographic security of primitive subgroups \(V_{q^r|q}\) of the Weil restriction of scalars. They prove that given a supersingular elliptic curve \(E\) defined over \(\mathbb{F}_q\) and a suitable prime \(r\) there exists an abelian variety \(E_r\) over \(\mathbb{F}_q\) (the \(rth\) primitive subgroup) with security parameter better, by a factor \(r/(r-1)\), than the parameter of \(E\). If \(A_0\) denotes the trace zero subgroup of \(E(\mathbb{F}_{q^r})\) then \(E_r(\mathbb{F}_q)\cong A_0\subseteq E(\mathbb{F}_{q^r})\). Section 10 gives a compression/decompression algorithm for the points of \(A_0\) which compresses by a factor of \(r/(r-1)\). The algorithm is efficient when \(r=3, p\neq 3\) (Section 10.3) and \(r=5, p=3\) (Section 10.4) .
Section 12, keeping in mind the results of Table 1, constructs explicit examples of optimal abelian varieties (varieties with the highest \(c_{A,q}\) among abelian varieties of the same dimension) for those dimensions providing the highest MOV security per bit.
Reviewer: Juan Tena Ayuso (Valladolid)
MSC:
| 94A60 | Cryptography |
| 94A62 | Authentication, digital signatures and secret sharing |
| 14H52 | Elliptic curves |
| 11G10 | Abelian varieties of dimension \(> 1\) |
| 14G50 | Applications to coding theory and cryptography of arithmetic geometry |
Keywords:
elliptic curves; pairing-based cryptography; elliptic curve cryptography; abelian varieties; compressionReferences:
| [1] | Balasubramanian, R.; Koblitz, N., The improbability that an elliptic curve has subexponential discrete log problem under the Menezes-Okamoto-Vanstone algorithm, J. Cryptol., 11, 141-145 (1998) · Zbl 0978.94038 · doi:10.1007/s001459900040 |
| [2] | P.S.L.M. Barreto, Pairing-based crypto lounge, http://planeta.terra.com.br/informatica/paulobarreto/pblounge.html |
| [3] | Barreto, P. S.L. M.; Galbraith, S. D.; hÉigeartaigh, C.Ó.; Scott, M., Efficient pairing computation on supersingular Abelian varieties, Des. Codes Cryptogr., 42, 239-271 (2007) · Zbl 1142.14307 · doi:10.1007/s10623-006-9033-6 |
| [4] | Boneh, D.; Franklin, M., Identity based encryption from the Weil pairing, Advances in Cryptology—Crypto 2001, 213-229 (2001), Berlin: Springer, Berlin · Zbl 1002.94023 |
| [5] | Boneh, D.; Waters, B., Conjunctive, subset, and range queries on encrypted data, Theory of Cryptography, Proceedings of the 4th Theory of Cryptography Conference, TCC 2007, 535-554 (2007), Berlin: Springer, Berlin · Zbl 1156.94335 |
| [6] | Boneh, D.; Lynn, B.; Shacham, H., Short signatures from the Weil pairing, Advances in Cryptology—Asiacrypt 2001, 514-532 (2001), Berlin: Springer, Berlin · Zbl 1064.94554 |
| [7] | Boneh, D.; Lynn, B.; Shacham, H., Short signatures from the Weil pairing, J. Cryptol., 17, 297-319 (2004) · Zbl 1070.94010 · doi:10.1007/s00145-004-0314-9 |
| [8] | Boneh, D.; Goh, E.-J.; Nissim, K., Evaluating 2-DNF formulas on ciphertexts, Proceedings of TCC 2005, 325-341 (2005), Berlin: Springer, Berlin · Zbl 1079.94534 |
| [9] | Boneh, D.; Sahai, A.; Waters, B., Fully collusion resistant traitor tracing with short ciphertexts and private keys, Advances in Cryptology—Eurocrypt 2006, 573-592 (2006), Berlin: Springer, Berlin · Zbl 1140.94326 |
| [10] | Boyen, X.; Waters, B., Compact group signatures without random oracles, Advances in Cryptology—Eurocrypt 2006, 427-444 (2006), Berlin: Springer, Berlin · Zbl 1140.94327 |
| [11] | Coleman, R.; McCallum, W., Stable reduction of Fermat curves and Jacobi sum Hecke characters, J. Reine Angew. Math., 385, 41-101 (1988) · Zbl 0654.12003 |
| [12] | C. Diem, A study on theoretical and practical aspects of Weil-restrictions of varieties. Dissertation, 2001, http://www.math.uni-leipzig.de/ diem/dissertation_diem.dvi · Zbl 0985.14011 |
| [13] | Diem, C.; Naumann, N., On the structure of Weil restrictions of Abelian varieties, J. Ramanujan Math. Soc., 18, 153-174 (2003) · Zbl 1080.14536 |
| [14] | C. Diem, J. Scholten, An attack on a trace-zero cryptosystem, preprint |
| [15] | Duursma, I., Class numbers for some hyperelliptic curves, Arithmetic, Geometry and Coding Theory, 45-52 (1996), Berlin: de Gruyter, Berlin · Zbl 0901.11020 |
| [16] | Duursma, I.; Sakurai, K., Efficient algorithms for the Jacobian variety of hyperelliptic curves y^2=x^p−x+1 over a finite field of odd characteristic p, Coding Theory, Cryptography and Related Areas, 73-89 (2000), Berlin: Springer, Berlin · Zbl 1009.11047 |
| [17] | G. Frey, How to disguise an elliptic curve (Weil descent), Lecture at ECC ’98, http://www.cacr.math.uwaterloo.ca/conferences/1998/ecc98/frey.ps |
| [18] | Frey, G., Applications of arithmetical geometry to cryptographic constructions, Finite Fields and Applications, 128-161 (2001), Berlin: Springer, Berlin · Zbl 1015.94545 |
| [19] | Frey, G.; Rück, H.-G., A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves, Math. Comput., 62, 865-874 (1994) · Zbl 0813.14045 · doi:10.2307/2153546 |
| [20] | Galbraith, S., Supersingular curves in cryptography, Advances in Cryptology—Asiacrypt 2001, 495-513 (2001), Berlin: Springer, Berlin · Zbl 1064.11079 |
| [21] | P. Gaudry, Index calculus for Abelian varieties and the elliptic curve discrete logarithm problem, to appear in J. Symbolic Comput. · Zbl 1177.94148 |
| [22] | Gaudry, P.; Hess, F.; Smart, N. P., Constructive and destructive facets of Weil descent on elliptic curves, J. Cryptol., 15, 19-46 (2002) · Zbl 0996.94036 · doi:10.1007/s00145-001-0011-x |
| [23] | Golomb, S. W., Cyclotomic polynomials and factorization theorems, Am. Math. Monthly, 85, 734-737 (1978) · Zbl 0403.12002 · doi:10.2307/2321679 |
| [24] | Groth, J.; Ostrovsky, R.; Sahai, A., Perfect non-interactive zero knowledge for NP, Advances in Cryptology—Eurocrypt 2006, 339-358 (2006), Berlin: Springer, Berlin · Zbl 1129.94025 |
| [25] | Hitt, L., On the minimal embedding field, Pairing-Based Cryptography—Pairing 2007, 294-301 (2007), Berlin: Springer, Berlin · Zbl 1151.94518 |
| [26] | Honda, T., Isogeny classes of Abelian varieties over finite fields, J. Math. Soc. Jpn., 20, 83-95 (1968) · Zbl 0203.53302 · doi:10.2969/jmsj/02010083 |
| [27] | Joux, A., A one round protocol for tripartite Diffie-Hellman, Algorithmic Number Theory (ANTS-IV), 385-394 (2000), Berlin: Springer, Berlin · Zbl 1029.94026 |
| [28] | Joux, A.; Lercier, R., The function field sieve in the medium prime case, Advances in Cryptology—Eurocrypt 2006, 254-270 (2006), Berlin: Springer, Berlin · Zbl 1140.94349 |
| [29] | KASH, http://www.math.tu-berlin.de/ kant/kash_main.html · Zbl 1229.11160 |
| [30] | Lange, T., Trace zero subvarieties of genus 2 curves for cryptosystems, J. Ramanujan Math. Soc., 19, 15-33 (2004) · Zbl 1109.94003 |
| [31] | Lenstra, A. K.; Verheul, E. R., The XTR public key system, Advances in Cryptology—CRYPTO 2000, 1-19 (2000), Berlin: Springer, Berlin · Zbl 0995.94538 |
| [32] | Mazur, B.; Rubin, K.; Silverberg, A., Twisting commutative algebraic groups, J. Algebra, 314, 419-438 (2007) · Zbl 1128.14034 · doi:10.1016/j.jalgebra.2007.02.052 |
| [33] | Menezes, A. J.; Okamoto, T.; Vanstone, S. A., Reducing elliptic curve logarithms to logarithms in a finite field, IEEE Trans. Inf. Theory, 39, 1639-1646 (1993) · Zbl 0801.94011 · doi:10.1109/18.259647 |
| [34] | Miyaji, A.; Nakabayashi, M.; Takano, S., New explicit conditions of elliptic curve traces for FR-reduction, IEICE Trans. Fundam. E84-A, 5, 1234-1243 (2001) |
| [35] | Müller, W. B.; Nöbauer, W., Some remarks on public-key cryptosystems, Stud. Sci. Math. Hungar., 16, 71-76 (1981) · Zbl 0476.94016 |
| [36] | Mumford, D., Abelian Varieties (1970), London: Oxford University Press, London · Zbl 0223.14022 |
| [37] | Naumann, N., Weil-Restriktion Abelscher Varietäten (1999), Universität Essen: Diplomarbeit, Universität Essen |
| [38] | Rubin, K.; Silverberg, A., Supersingular Abelian varieties in cryptology, Advances in Cryptology—CRYPTO 2002, 336-353 (2002), Berlin: Springer, Berlin · Zbl 1026.94540 |
| [39] | Rubin, K.; Silverberg, A., Torus-based cryptography, Advances in Cryptology—CRYPTO 2003, 349-365 (2003), Berlin: Springer, Berlin · Zbl 1122.94400 |
| [40] | Rubin, K.; Silverberg, A., Using primitive subgroups to do more with fewer bits, Proceedings of ANTS-VI, 18-41 (2004), Berlin: Springer, Berlin · Zbl 1125.94328 |
| [41] | Rubin, K.; Silverberg, A., Compression in finite fields and torus-based cryptography, SIAM J. Comput., 37, 1401-1428 (2008) · Zbl 1211.94036 · doi:10.1137/060676155 |
| [42] | R. Sakai, K. Ohgishi, M. Kasahara, Cryptosystems based on pairing, SCIS2000 (The 2000 Symposium on Cryptography and Information Security), Okinawa, Japan, January 26-28, 2000, p. C20 |
| [43] | Schaefer, E. F., A new proof for the non-degeneracy of the Frey-Rück pairing and a connection to isogenies over the base field, Computational Aspects of Algebra Curves, 1-12 (2005), Hackensack: World Sci. Publ., Hackensack · Zbl 1154.14320 |
| [44] | Shimura, G., Introduction to the Arithmetic Theory of Automorphic Functions, Reprint of the 1971 Original (1994), Princeton: Princeton University Press, Princeton · Zbl 0872.11023 |
| [45] | Shimura, G., Abelian Varieties with Complex Multiplication and Modular Functions (1998), Princeton: Princeton Univ. Press, Princeton · Zbl 0908.11023 |
| [46] | A. Silverberg, Compression for trace zero subgroups of elliptic curves, in the Proceedings of the Daewoo Workshop on Cryptography, in Trends in Mathematics, vol. 8 (2005), pp. 93-100 |
| [47] | Smith, P. J.; Lennon, M. J.J., LUC: a new public key system, Proceedings of the IFIP TC11 Ninth International Conference on Information Security IFIP/Sec ’93, 103-117 (1993), Amsterdam: North-Holland, Amsterdam |
| [48] | Smith, P.; Skinner, C., A public-key cryptosystem and a digital signature system based on the Lucas function analogue to discrete logarithms, Advances in Cryptology—Asiacrypt 1994, 357-364 (1995), Berlin: Springer, Berlin · Zbl 0872.94041 |
| [49] | Tate, J., Endomorphisms of Abelian varieties over finite fields, Invent. Math., 2, 134-144 (1966) · Zbl 0147.20303 · doi:10.1007/BF01404549 |
| [50] | Tate, J., Classes d’isogénie des variétés abéliennes sur un corps fini (d’après T. Honda), Séminaire Bourbaki, 95-110 (1968), Paris: Soc. Math. France, Paris · Zbl 0212.25702 |
| [51] | Waterhouse, W. C., Abelian varieties over finite fields, Ann. Sci. École Norm. Sup., 2, 4, 521-560 (1969) · Zbl 0188.53001 |
| [52] | Weil, A., Adeles and Algebraic Groups (1982), Boston: Birkhäuser, Boston · Zbl 0493.14028 |
| [53] | A. Weimerskirch, The application of the Mordell-Weil group to cryptographic systems, MS thesis, Worcester Polytechnic Institute (2001), http://weimerskirch.org/papers/Weimerskirch_MordellWeilMSThesis.pdf |
| [54] | Zhu, H. J., Group structures of elementary supersingular Abelian varieties over finite fields, J. Number Theory, 81, 292-309 (2000) · Zbl 1096.11502 · doi:10.1006/jnth.1999.2463 |
| [55] | Zhu, H. J., Supersingular Abelian varieties over finite fields, J. Number Theory, 86, 61-77 (2001) · Zbl 1007.11036 · doi:10.1006/jnth.2000.2562 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
