Vai ai contenuti. | Spostati sulla navigazione | Spostati sulla ricerca | Vai al menu | Contatti | Accessibilità

logo del sistema bibliotecario dell'ateneo di padova

Parolini, Luca (2019) Security evaluation of a key management scheme based on bilinear maps on elliptic curves. [Magistrali biennali]

Full text disponibile come:

[img]
Preview
PDF
860Kb

Abstract

In recent years, many applications of elliptic curves to cryptography have been developed. Cryptosystems based on groups of rational points on elliptic curves allow more efficient alternatives to finite field cryptography, which usually requires groups with larger cardinality and lower efficiency. The existence of non-degenerate, bilinear maps on elliptic curves, called pairings, allow the construction of many efficient cryptosystems; however, their security must be carefully studied. We will study the security of a key menagement scheme introduced by Boneh, Gentry and Waters in 2005, which is based on the decisional version of the l-BDHE problem. This is a variant of the classical Diffie-Hellman problem, specifically constructed for pairing-based cryptography. Its hardness, is still a research topic and only some theoretical evidence exists. The aim of this work is to investigate the security of this broadcast encryption system, taking in account a model that proves the hardness of the l-BDHE problem, under strong assumptions. Drawbacks of this approach will be discussed: its main weakness is the system's behaviour during attack simulations, which is far from real. The main result of this thesis is a lower bound on the running time of an adversary solving the above problem. Moreover, also the elliptic curve choice, when implementing an encryption scheme, could affect its security. We will review the main criteria for this choice and we will investigate the existence of elliptic curves suitable for the system of our interest.

Item Type:Magistrali biennali
Corsi di Diploma di Laurea:Scuola di Scienze > Matematica
Uncontrolled Keywords:cryptography, Pairing-based cryptography
Subjects:Area 01 - Scienze matematiche e informatiche > MAT/02 Algebra
Codice ID:62451
Relatore:Colpi, Riccardo
Correlatore:Laurenti, Nicola and Ceccato, Silvia and Poltronieri, Anna
Data della tesi:18 April 2019
Biblioteca:Polo di Scienze > Biblioteca di Matematica
Tesi sperimentale (Si) o compilativa (No)?:Yes

Bibliografia

I riferimenti della bibliografia possono essere cercati con Cerca la citazione di AIRE, copiando il titolo dell'articolo (o del libro) e la rivista (se presente) nei campi appositi di "Cerca la Citazione di AIRE".
Le url contenute in alcuni riferimenti sono raggiungibili cliccando sul link alla fine della citazione (Vai!) e tramite Google (Ricerca con Google). Il risultato dipende dalla formattazione della citazione e non da noi.

[1] G. Adj, A. Menezes, T. Oliveira, F. Rodriguez-Henriquez. Computing discrete loga-rithms in F3(6-137) and F3(6-163) using Magma. C. K. Koc, S. Mesnager and E. Savas (eds) Arithmetic of Finite Fields (WAIFI 2014), vol. 9061, of Lectures Notes in Computer Science, pp. 3-22, Springer, 2014. Cerca con Google

[2] M. F. Atiyah, I. G. Macdonald. Introduction to commutative algebra. Addison-Wesley Publishing Company, 1969. Cerca con Google

[3] E. Bach, Jeffrey Shallit. Algorithmic number theory. The MIT Press, vol. 1, 1996. Cerca con Google

[4] R. Balasubramanian, N. Koblitz. The improbability that an elliptic curve has subexponential discrete log problem under the Menezes-Okamoto-Vanstone algorithm. Journal of Cryptology, vol. 11, issue 2, pp. 141-145, 1998. Cerca con Google

[5] R. Barbulescu, P. Gaudry, T. Kleinjung. The tower number field sieve. Advances in Cryptology, ASIACRYPT 2015, LCNS 9453, pp. 31-55, 2015. Cerca con Google

[6] R. Barbulescu, P. Gaudry, E. Thomé, A. Joux. A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic. P. Q. Nguyen, E. Oswald (eds) Advances in Cryptology - EUROCRYPT 2014, Lecture Notes in Computer Science, vol. 8441, Springer, 2013. Cerca con Google

[7] R. Barbulescu, P. Gaudry, A. Guillevic, F. Morain. Improving NFS for the discrete logarithm problem in non-prime finite fields. M. Fischlin and E. Oswald (eds) Advances in Cryptology, Eurocrypt 2015, Lecture Notes in Computer Sciences, vol. 9056, pp.129-155, 2015. Cerca con Google

[8] N. Benger, M. Scott. Constructing tower extensions of finite fields for implementation of pairing-based cryptography. M.A. Hasan, T. Helleseth (eds), WAIFI 2010. Lecture Notes in Computer Science, vol. 6087, pp. 180-195. Springer, 2010. Cerca con Google

[9] D. J. Bernstein. Faster square roots in annoying finite fields. Cerca con Google

URL: http://cr.yp.to/papers/sqroot.ps. Vai! Cerca con Google

[10] I. Blake, G. Seroussi, N. Smart. Elliptic curves in cryptography. Cambridge University Press, 1999. Cerca con Google

[11] I. Blake, G. Seroussi, N. Smart. Advances in elliptic curve cryptography. Cambridge University Press, 2005. Cerca con Google

[12] D. Boneh, X. Boyen, E. Goh. Hierarchical identity based encryption with constant size ciphertext. Advances in Cryptology, R. Cramer editor, EUROCRYPT 2005, vol. 3493, pp. 440-456, Lecture Notes in Computer Science, Springer, 2005. Cerca con Google

[13] D. Boneh, X. Boyen, H. Shacham. Short group signatures. CRYPTO 2004, Springer-Verlag, 2004. Cerca con Google

[14] D. Boneh, M. Franklin. Identity-based encryption from the Weil pairing. Advances in Cryptology - CRYPTO 2001, Lecture Notes in Computer Science, vol. 2139, pp. 213-229, Springer, 2001. Full version: SIAM Journal on Computing, vol.32, pp. 586-615, 2003. Cerca con Google

[15] D. Boneh, C. Gentry, B. Waters. Collusion resistant broadcast encryption with short ciphertext and private keys. Advances in cryptology - CRYPTO 2005, Lecture Notes in Computer Science, vol. 3621, pp. 258-275, Springer, 2005. Cerca con Google

[16] D. Boneh, E.-J. Goh, K. Nissim. Evaluating 2-DNF formulae on ciphertexts. Theory of Cryptography '05, vol. 3378 of Lecture Notes in Computer Science, pp. 325-341, Springer-Verlag, 2005. Cerca con Google

[17] D. Boneh, B. Lynn, H. Shacham. Short signatures from the Weil pairing. Advances in Cryptology - ASIACRYPT 2001, Lecture Notes in Computer Science, vol. 2248, pp. 514-532, Springer, 2001. Full version: Journal of Cryptology, vol. 17, pp. 297-319, 2004. Cerca con Google

[18] S. Ceccato. A key management scheme for access control to GNSS services. Tesi di Laurea Magistrale, Dipartimento di Ing. dell'Informazione, Università di Padova, a.a. 2015-16, URL: http://tesi.cab.unipd.it/52989/ Vai! Cerca con Google

[19] J.H. Cheon. Security analysis of the strong Diffie-Hellman problem. S. Vaudenay (eds) Advances in Cryptology - EUROCRYPT 2006, Lecture Notes in Computer Science, vol. 4004. Springer, 2006. Cerca con Google

[20] H. Cohen, G. Frey, R. Avanzi, C. Doche, T. Lange, K.Nguyen, F.Vercauteren. Handbook of elliptic and hyperelliptic curve cryptography. Chapman & Hall/CRC, 2006. Cerca con Google

[21] D. Coppersmith. Fast evaluation of logarithms in fields of characteristic two. IEEE Transactions on Information Theory, vol. 30, pp. 587-594, 1984. Cerca con Google

[22] D. Eisenbund, M. Green, J. Harris Cayley-Bacharach theorems and conjectures. Bulletin of the American Mathematical Society, vol. 33, n. 3, 1996. Cerca con Google

[23] A. Enge. Bilinear pairings on elliptic curves. arXiv:1301.5520, 2013 Cerca con Google

https://arxiv.org/abs/1301.5520 Vai! Cerca con Google

[24] D. Freeman, M. Scott, E. Teske. A taxonomy of pairing-friendly elliptic curves. Journal of Cryptology, vol. 23, issue 2, pp. 224-280, 2010. Cerca con Google

[25] G. Frey, H. Gangl. How to disguise an elliptic curve (Weil de-scent). Talk at ECC '98, The 2nd Workshop on Elliptic Curve Cryptography, U. Waterloo, 1998, Cerca con Google

URL: http://www.cacr.math.uwaterloo.ca/conferences/1998/ecc98/frey.ps Vai! Cerca con Google

[26] S.Galbraith, K. Paterson, N. Smart. Pairings for cryptographers. Discrete Applied Mathematics, vol. 156, pp. 3113-3121, 2008. Cerca con Google

[27] R. Granger, T. Kleinjung, J. Zumbragel, Breaking 128-bit secure supersingular binary curves. J. A. Garay and R. Gennaro (eds) Advances in Cryptology - CRYPTO 2014, part II, vol. 8617 of Lecture Notes in Computer Science, pp. 126-145, Springer, 2014. Cerca con Google

[28] D. Hankerson, A. J. Menezes, S. Vanstone. Guide to Elliptic Curve Cryptography. Springer-Verlag, 2004. Cerca con Google

[29] F. Hess, N. P. Smart, F. Vercauteren. The eta pairing revisited. IEEE Transactions on Information Theory, vol. 52, issue 10, pp. 4595-4602, 2006. Cerca con Google

[30] L. Hitt On the Minimal Embedding Field. T. Takagi, T. Okamoto, E. Okamoto, T. Okamoto (eds) Pairing-Based Cryptography - Pairing 2007. Lecture Notes in Computer Science, vol. 4575, pp. 294-301, Springer, 2007. Cerca con Google

[31] K. Ireland, M. Rosen. A classical introduction to modern number theory. Springer, 1982 Cerca con Google

[32] A. Joux, C. Pierrot. The special number field sieve in Fpn - application to pairing-friendly constructions. Z. Cao and F. Zhang (eds) Pairing-Based Cryptography - Pairing 2013, vol. 8365 of Lecture Notes in Computer Science, pp. 54-61, Springer, 2014. Cerca con Google

[33] T. Kim, R. Barbulescu. Extended tower number field sieve: A new complexity for medium prime case. Annual Cryptology Conference, LCNS 9814, pp. 543-571, Springer Berlin Heidelberg, 2016. Cerca con Google

[34] T. Kim, J. Jeong. Extended Tower Number Field Sieve with Application to Finite Fields of Arbitrary Composite Extension Degree. S. Fehr (eds) Public-Key Cryptography - PKC 2017, Lecture Notes in Computer Science, vol. 10174. Springer, 2017. Cerca con Google

[35] N. Koblitz. Elliptic curve cryptosystems. Mathematics of Computation, vol. 48, n. 177, pp. 203-209, 1987. Cerca con Google

[36] N. Koblitz, A. Menezes. Another look at generic groups. Advances in Mathematics of Communications 1, pp. 13-28, 2007. Cerca con Google

[37] H. Kredel, V. Weispfenning. Computing dimension and independent sets for polynomial ideals. Journal of Symbolic Computation, vol. 6, issues 2-3, pp. 231-247, 1988. Cerca con Google

[38] D. Lubicz, T. Sirvent. On generic groups and related bilinear problems. Identity-Based Cryptography, M. Joye, G. Neven (eds.), IOS Press, vol. 2, pp. 169-187, Cryptology and Information Security Series, 2008. Cerca con Google

[39] B. Lynn. On the implementation of pairing-based cryptosystems. Cerca con Google

URL: https://crypto.stanford.edu/pbc/thesis.html, 2007. Vai! Cerca con Google

[40] D. Maimuµ, C. Murdica, D. Naccache, M. Tibouchi. Fault Attacks on Projective-to-Affine Coordinates Conversion. E. Prouff (eds) Constructive Side-Channel Analysis and Secure Design, COSADE 2013, Lecture Notes in Computer Science, vol. 7864, Springer, 2013. Cerca con Google

[41] A. Menezes. An introduction to pairing-based cryptography. Contemporary Mathematics, vol. 477, pp. 47-65, American Mathematical Society, 2009. Cerca con Google

[42] A. Menezes, T. Okamoto, S. Vanstone. Reducing elliptic curve logarithms in a finite field. IEEE Transactions on Information Theory, vol. IT-39, n. 5, pp. 1639-1646, 1993. Cerca con Google

[43] V. S. Miller. Use of elliptic curves in cryptography. Advances in Cryptology, CRYPTO-1985 Proceedings, pp. 417-426, 1985. Cerca con Google

[44] J. S. Milne. Algebraic geometry. Version 6.02. Cerca con Google

URL: https://www.jmilne.org/math/CourseNotes/AG.pdf, 2017. Vai! Cerca con Google

[45] R. Miranda. Algebraic curves and Riemann surfaces. Graduate Studies in Mathematics book 5, American Mathematical Society, 1995. Cerca con Google

[46] N. El Mrabet, M. Joye. Guide to pairing based cryptography. Chapman & Hall/CRC, 2017. Cerca con Google

[47] D. Naccache, N. Smart, J. Stern. Projective coordinates leak. Advances in Cryptology, Eurocrypt 2004, LNCS 3027, pp. 257-267, Springer-Verlag, 2004. Cerca con Google

[48] P. Sarkar, S. Singh. New complexity trade-offs for the (multiple) number field sieve algorithm in non-prime fields. Cryptology ePrint Archive, Report 2015/944, 2015, Cerca con Google

URL: http://eprint.iacr.org/2015/944. Vai! Cerca con Google

[49] R. Schoof. Nonsingular plane cubic curves defined over finite fields. Journal of Combinatorial Theory, series A, vol. 46, issue 2, pp. 183-211, 1987. Cerca con Google

[50] J. T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. Journal of the Association for Computing Machinery, vol. 27, n. 4, pp. 701-717, 1980. Cerca con Google

[51] V. Shoup. Lower Bounds for Discrete Logarithms and Related Problems. Advances in Cryptology, W. Fumy (eds), EUROCRYPT 1997, Lecture Notes in Computer Science, vol. 1233, Springer, 1997. Cerca con Google

[52] J. H. Silverman. The arithmetic of elliptic curves. Springer-Verlag, 1986. Cerca con Google

[53] N.P. Smart, F. Vercauteren. On computable isomorphisms in efficient asymmetric pairing-basedsystems. Discrete Applied Mathematics, vol. 155, issue 4, pp. 538-547, 2007. Cerca con Google

[54] T. Teruya, K. Saito, N. Kanayama, Y. Kawahara, T.Kobayashi, E. Okamoto Constructing Symmetric Pairings over Supersingular Elliptic Curves with Embedding Degree Three. Z. Cao, F. Zhang (eds) Pairing-Based Cryptography - Pairing 2013, Lecture Notes in Computer Science, vol. 8365. Springer, 2014. Cerca con Google

[55] O. Uzunkol, M. S. Kiraz. Still wrong use of pairings in cryptography. Applied Mathematics and Computation, vol. 333, pp. 467-479, 2018. Cerca con Google

[56] E. R. Verheul. Evidence that XTR is more secure than supersingular elliptic curve cryptosystems. Journal of Cryptology 17, n. 4, pp. 277-296, 2004 Cerca con Google

[57] L. C. Washington. Elliptic curves. Number theory and cryptography. Chapman & Hall/CRC, 2003. Cerca con Google

[58] A. Wright. Transcendence degree. Cerca con Google

URL: http://www-personal.umich.edu/ alexmw/TranscDeg.pdf Vai! Cerca con Google

[59] X. Zhang, K. Wang. Fast Symmetric Pairing Revisited. Z. Cao and F. Zhang (eds) Pairing-Based Cryptography - Pairing 2013, Lecture Notes in Computer Science, vol. 8365, Springer, 2013. Cerca con Google

Solo per lo Staff dell Archivio: Modifica questo record