nach oben

Erschienen in:

2015 | OriginalPaper | Buchkapitel

Discrete Logarithms for Torsion Points on Elliptic Curve of Embedding Degree \(1\)

verfasst von : Yasuyuki Nogami, Hwajeong Seo

Erschienen in: Information Security and Cryptology - ICISC 2014

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Recent efficient pairings such as Ate pairing use two efficient subgroups of rational point such that \(\pi (P)=P\) and \(\pi (Q)=[p]Q\), where \(\pi \), \(p\), \(P\), and \(Q\) are the Frobenius map for rational point, the characteristic of definition field, and torsion points for pairing, respectively. This relation accelerates not only pairing but also pairing–related operations such as scalar multiplications. It holds in the case that the embedding degree \(k\) divides \(r-1\), where \(r\) is the order of torsion rational points. Thus, such a case has been well studied. Alternatively, this paper focuses on the case that the degree divides \(r+1\) but not \(r-1\). First, this paper shows a transitive representation for \(r\)–torsion points based on the fact that the characteristic polynomial \(f(\pi )\) becomes irreducible over \(\mathbb {F}_{r}\) for which \(\pi \) also plays a role of variable. In other words, this paper proposes an elliptic curve discrete logarithm on such a torsion group. After that, together with some example parameters, it is shown how to prepare such pairing–friendly elliptic curves.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Algebraic Cryptanalysis of Yasuda, Takagi and Sakurai’s Signature Scheme

Nächstes Kapitel Efficient Key Dependent Message Security Amplification Against Chosen Ciphertext Attacks

Nur mit Berechtigung zugänglich

It is noted that skew Frobenius map such as \(\hat{\pi }{d}\) is available for both \(E(\mathbb {F}_{p})\) and \(E_d(\mathbb {F}_{p})\) because they are twisted to and from each other.

There will be some other cases such that \(n=r\).

Barreto, P.S.L.M., Naehrig, M.: Pairing-friendly elliptic curves of prime order. In: Preneel, B., Tavares, S. (eds.) SAC 2005. LNCS, vol. 3897, pp. 319–331. Springer, Heidelberg (2006) CrossRef

Boneh, D., Goh, E.-J., Nissim, K.: Evaluating 2-DNF formulas on ciphertexts. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 325–341. Springer, Heidelberg (2005) CrossRef

Boneh, D., Sahai, A., Waters, B.: Fully collusion resistant traitor tracing with short ciphertexts and private keys. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 573–592. Springer, Heidelberg (2006) CrossRef

Boneh, D., Rabin, K., Silverberg, A.: Finding composite order ordinary elliptic curves using the cocks-pinch method. In: Cryptology ePrint Archive, Report 2009/533 (2009)

Castagnos, G., Laguillaumie, F.: Homomorphic encryption for multiplications and pairing evaluation. In: Visconti, I., De Prisco, R. (eds.) SCN 2012. LNCS, vol. 7485, pp. 374–392. Springer, Heidelberg (2012) CrossRef

Charles, D.: On the existence of distortion maps on ordinary elliptic curves. In: Cryptology ePrint Archive, Report 2006/128 (2006)

Cohen, H., Frey, G.: Handbook of Elliptic and Hyperelliptic Curve Cryptography. Discrete Mathematics and Its Applications. Chapman & Hall CRC, Boca Raton (2005) CrossRef

Dickson, L.E.: The analytic representation of substitutions on a power of a prime number of letters with a discussion of the linear group. Ann. Math. 11, 161–183 (1897)CrossRef

Galbraith, S.D., Scott, M.: Exponentiation in pairing-friendly groups using homomorphisms. In: Galbraith, S.D., Paterson, K.G. (eds.) Pairing 2008. LNCS, vol. 5209, pp. 211–224. Springer, Heidelberg (2008) CrossRef

10.

GNU MP. http://gmplib.org/

11.

Hankerson, D., Vanstone, S., Menezes, A.: Guide to Elliptic Curves Cryptography. Springer, New York (2004)

12.

Hitt, L.: On the minimal embedding field. In: Cryptology ePrint Archive, Report 2006/415 (2006)

13.

Itoh, T., Tsujii, S.: A fast algorithm for computing multiplicative inverses in GF\((2^m)\) using normal bases. Inf. Comp. 78, 171–177 (1988)CrossRefMATHMathSciNet

14.

Izuta, T., Takeuchi, S., Nishii, K., Nogami, Y., Morikawa, Y.: GLV subgroups on non-supersingular pairing-friendly curves of embedding degree 1. In: Computer Security Symposium 2010, pp. 249–254 (2010)

15.

Joux, A.: A one round protocol for tripartite diffie-hellman. J. Cryptol. 17(4), 263–276 (2004)CrossRefMATHMathSciNet

16.

Koblitz, N., Menezes, A.: Pairing-based cryptography at high security levels. In: Smart, N.P. (ed.) Cryptography and Coding 2005. LNCS, vol. 3796, pp. 13–36. Springer, Heidelberg (2005) CrossRef

17.

Morain, F.: Primality proving using elliptic curves: an update. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol. 1423, pp. 111–127. Springer, Heidelberg (1998) CrossRef

18.

Nakanishi, T., Funabiki, N.: Verifier-local revocation group signature schemes with backward unlinkability from bilinear maps. In: Roy, B. (ed.) ASIACRYPT 2005. LNCS, vol. 3788, pp. 533–548. Springer, Heidelberg (2005) CrossRef

19.

Nogami, Y., Akane, M., Sakemi, Y., Kato, H., Morikawa, Y.: Integer variable \(\chi \)–based ate pairing. In: Galbraith, S.D., Paterson, K.G. (eds.) Pairing 2008. LNCS, vol. 5209, pp. 178–191. Springer, Heidelberg (2008) CrossRef

20.

Ohta, K., Shiota, K.: Construction of CM Curves Suitable for Cryptosystem from the Weil Pairing. Memoirs of the Faculty of Science, Kochi Univ., Vol. 27, No. 1 (2007)

21.

Sakai, R., Ohgishi, K., Kasahara, M.: Cryptosystems based on pairing. In: SCIS 2000 (2000)

22.

Sakemi, Y., Nogami, Y., Okeya, K., Kato, H., Morikawa, Y.: Skew frobenius map and efficient scalar multiplication for pairing–based cryptography. In: Franklin, M.K., Hui, L.C.K., Wong, D.S. (eds.) CANS 2008. LNCS, vol. 5339, pp. 226–239. Springer, Heidelberg (2008) CrossRef

23.

Smart, N., Blake, I.F., Seroussi, G.: Elliptic Curves in Cryptography. LMS Lecture Note Series. Cambridge University Press, New York (1999) MATH

24.

Yoshida, M., Mitsunari, S., Fujiwara, T.: The vector decomposition problem. IEICE Trans. Fundamentals E93–A(1), 188–193 (2010)CrossRef

Titel: Discrete Logarithms for Torsion Points on Elliptic Curve of Embedding Degree
verfasst von: Yasuyuki Nogami
Hwajeong Seo
Verlag: Springer International Publishing
Buch: Information Security and Cryptology - ICISC 2014
Print ISBN: 978-3-319-15942-3

Electronic ISBN: 978-3-319-15943-0

Copyright-Jahr: 2015
DOI: https://doi.org/10.1007/978-3-319-15943-0_5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner