A Survey of Public-Key Cryptosystems (2004)

Previous article Next article A Survey of Public-Key CryptosystemsNeal Koblitz and Alfred J. MenezesNeal Koblitz and Alfred J. Menezeshttps://doi.org/10.1137/S0036144503439190PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstractWe give an overview of the most important public-key cryptosystems and discuss the difficult task of evaluating the merit of such systems.[1] Google Scholar[2] Google Scholar[3] I. Anshel, , M. Anshel and , and D. Goldfeld, An algebraic method for public‐key cryptography, Math. Res. Lett., 6 (1999), pp. 1–5. aig ZZZZZZ 1073-2780 Math. Res. Lett. CrossrefGoogle Scholar[4] Google Scholar[5] Google Scholar[6] R. Balasubramanian and and N. Koblitz, The improbability that an elliptic curve has subexponential discrete log problem under the Menezes–Okamoto–Vanstone algorithm, J. Cryptology, 11 (1998), pp. 141–145. jzq JOCREQ 0933-2790 J. Cryptology CrossrefISIGoogle Scholar[7] Google Scholar[8] Google Scholar[9] Google Scholar[10] Google Scholar[11] Google Scholar[12] Google Scholar[13] Google Scholar[14] Google Scholar[15] Dan Boneh, Twenty years of attacks on the RSA cryptosystem, Notices Amer. Math. Soc., 46 (1999), 203–213 MR1673760 Google Scholar[16] Google Scholar[17] D. Boneh and and G. Durfee, Cryptanalysis of RSA with private key d less than N0.292, IEEE Trans. Inform. Theory, 46 (2000), pp. 1339–1349. iet IETTAW 0018-9448 IEEE Trans. Inf. Theory CrossrefISIGoogle Scholar[18] D. Boneh and and M. Franklin, Identity‐based encryption from the Weil pairing, SIAM J. Comput., 32 (2003), pp. 586–615. sim SMJCAT 0097-5397 SIAM J. Comput. LinkISIGoogle Scholar[19] Google Scholar[20] Google Scholar[21] Google Scholar[22] Google Scholar[23] E. Brickell and and A. Odlyzko, Cryptanalysis: A survey of recent results, Proc. IEEE, 76 (1988), pp. 578–593. iee IEEPAD 0018-9219 Proc. IEEE CrossrefISIGoogle Scholar[24] Google Scholar[25] J. Buchmann, , R. Scheidler and , and H. C. Williams, A key exchange protocol using real quadratic fields, J. Cryptology, 7 (1994), pp. 171–199. jzq JOCREQ 0933-2790 J. Cryptology CrossrefISIGoogle Scholar[26] J. Buchmann and and H. C. Williams, A key exchange system based on imaginary quadratic fields, J. Cryptology, 1 (1988), pp. 107–118. jzq JOCREQ 0933-2790 J. Cryptology CrossrefGoogle Scholar[27] B. Chor and and R. Rivest, A knapsack‐type public key cryptosystem based on arithmetic in finite fields, IEEE Trans. Inform. Theory, 34 (1988), pp. 901–909. iet IETTAW 0018-9448 IEEE Trans. Inf. Theory CrossrefISIGoogle Scholar[28] Google Scholar[29] D. Coppersmith, Fast evaluation of logarithms in fields of characteristic two, IEEE Trans. Inform. Theory, 30 (1984), pp. 587–594. iet IETTAW 0018-9448 IEEE Trans. Inf. Theory CrossrefISIGoogle Scholar[30] Google Scholar[31] Google Scholar[32] W. Diffie and and M. Hellman, New directions in cryptography, IEEE Trans. Inform. Theory, 22 (1976), pp. 644–654. iet IETTAW 0018-9448 IEEE Trans. Inf. Theory CrossrefISIGoogle Scholar[33] T. ElGamal, A public key cryptosystem and a signature scheme based on discrete logarithms, IEEE Trans. Inform. Theory, 31 (1985), pp. 469–472. iet IETTAW 0018-9448 IEEE Trans. Inf. Theory CrossrefISIGoogle Scholar[34] M. Fellows and and N. Koblitz, Combinatorial cryptosystems galore!, Contemp. Math., 168 (1994), pp. 51–61. cte CTMAEH 0271-4132 Contemp. Math. CrossrefGoogle Scholar[35] M. Fouquet, , P. Gaudry and , and R. Harley, An extension of Satoh's algorithm and its implementation, J. Ramanujan Math. Soc., 15 (2000), pp. 281–318. Google Scholar[36] G. Frey and and H. Rück, A remark concerning m‐divisibility and the discrete logarithm in the divisor class group of curves, Math. Comp., 62 (1994), pp. 865–874. mcm MCMPAF 0025-5718 Math. Comput. ISIGoogle Scholar[37] Pierrick Gaudry, An algorithm for solving the discrete log problem on hyperelliptic curves, Lecture Notes in Comput. Sci., Vol. 1807, Springer, Berlin, 2000, 19–34 MR1772021 Google Scholar[38] Google Scholar[39] Google Scholar[40] P. Gaudry, , F. Hess and , and N. Smart, Constructive and destructive facets of Weil descent on elliptic curves, J. Cryptology, 15 (2002), pp. 19–34. jzq JOCREQ 0933-2790 J. Cryptology CrossrefISIGoogle Scholar[41] W. Geiselmann and and R. Steinwandt, Cryptanalysis of Polly Cracker, IEEE Trans. Inform. Theory, 48 (2002), pp. 2990–2991. iet IETTAW 0018-9448 IEEE Trans. Inf. Theory CrossrefISIGoogle Scholar[42] Google Scholar[43] Google Scholar[44] S. Goldwasser and and S. Micali, Probabilistic encryption, J. Comput. System Sci., 29 (1984), pp. 270–299. 8na JCSSBM 0022-0000 J. Comput. Syst. Sci. CrossrefISIGoogle Scholar[45] Guang Gong and , Lein Harn, Public‐key cryptosystems based on cubic finite field extensions, IEEE Trans. Inform. Theory, 45 (1999), 2601–2605 MR1725159 CrossrefISIGoogle Scholar[46] D. M. Gordon, Discrete logarithms in GF(p) using the number field sieve, SIAM J. Discrete Math., 6 (1993), pp. 124–138. am2 ZZZZZZ 0895-4801 SIAM J. Discrete Math. LinkISIGoogle Scholar[47] J. L. Hafner and and K. S. McCurley, A rigorous subexponential algorithm for computation of class groups, J. Amer. Math. Soc., 2 (1989), pp. 839–850. 5mx ZZZZZZ 0894-0347 J. Am. Math. Soc. CrossrefGoogle Scholar[48] Darrel Hankerson, , Alfred Menezes and , Scott Vanstone, Guide to elliptic curve cryptography, Springer Professional Computing, Springer‐Verlag, 2004xx+311 MR2054891 Google Scholar[49] J. Håstad, Solving simultaneous modular equations of low degree, SIAM J. Comput., 17 (1988), pp. 336–341. sim SMJCAT 0097-5397 SIAM J. Comput. LinkISIGoogle Scholar[50] M. E. Hellman and and R. C. Merkle, Hiding information and signatures in trapdoor knapsacks, IEEE Trans. Inform. Theory, 24 (1978), pp. 525–530. iet IETTAW 0018-9448 IEEE Trans. Inf. Theory CrossrefISIGoogle Scholar[51] Google Scholar[52] Jeffrey Hoffstein, , Jill Pipher and , Joseph Silverman, NTRU: a ring‐based public key cryptosystem, Lecture Notes in Comput. Sci., Vol. 1423, Springer, Berlin, 1998, 267–288 MR1726077 Google Scholar[53] Google Scholar[54] Google Scholar[55] Google Scholar[56] Google Scholar[57] M. Jacobson, , N. Koblitz, , J. Silverman, , A. Stein and , and E. Teske, Analysis of the xedni calculus attack, Des. Codes Cryptogr., 20 (2000), pp. 41–64. CrossrefISIGoogle Scholar[58] M. Jacobson, , A. Menezes and , and A. Stein, Solving elliptic curve discrete logarithm problems using Weil descent, J. Ramanujan Math. Soc., 16 (2001), pp. 231–260. Google Scholar[59] Google Scholar[60] Google Scholar[61] N. Koblitz, Elliptic curve cryptosystems, Math. Comp., 48 (1987), pp. 203–209. mcm MCMPAF 0025-5718 Math. Comput. CrossrefISIGoogle Scholar[62] N. Koblitz, Hyperelliptic cryptosystems, J. Cryptology, 1 (1989), pp. 139–150. jzq JOCREQ 0933-2790 J. Cryptology CrossrefGoogle Scholar[63] Google Scholar[64] N. Koblitz, Elliptic curve implementation of zero‐knowledge blobs, J. Cryptology, 4 (1991), pp. 207–213. jzq JOCREQ 0933-2790 J. Cryptology CrossrefGoogle Scholar[65] Google Scholar[66] Google Scholar[67] Google Scholar[68] Google Scholar[69] Google Scholar[70] Google Scholar[71] A. K. Lenstra, , H. W. Lenstra and , and L. Lovasz, Factoring polynomials with integer coefficients, Math. Ann., 261 (1982), pp. 513–534. maa MAANA3 0025-5831 Math. Ann. CrossrefISIGoogle Scholar[72] Google Scholar[73] Google Scholar[74] H. W. Lenstra, Factoring integers with elliptic curves, Ann. of Math. (2), 126 (1987), pp. 649–673. ann ANMAAH 0003-486X Ann. Math. CrossrefISIGoogle Scholar[75] Google Scholar[76] Google Scholar[77] Google Scholar[78] M. Maurer, , A. Menezes and , and E. Teske, Analysis of the GHS Weil descent attack on the ECDLP over characteristic two finite fields of composite degree, LMS J. Comput. Math., 5 (2002), pp. 127–174. CrossrefGoogle Scholar[79] U. M. Maurer and and S. Wolf, The relationship between breaking the Diffie–Hellman protocol and computing discrete logarithms, SIAM J. Comput., 28 (1999), pp. 1689–1721. sim SMJCAT 0097-5397 SIAM J. Comput. LinkISIGoogle Scholar[80] A. Menezes, , T. Okamoto and , and S. Vanstone, Reducing elliptic curve logarithms to logarithms in a finite field, IEEE Trans. Inform. Theory, 39 (1993), pp. 1639–1646. iet IETTAW 0018-9448 IEEE Trans. Inf. Theory CrossrefISIGoogle Scholar[81] Google Scholar[82] Google Scholar[83] Google Scholar[84] Google Scholar[85] Google Scholar[86] Google Scholar[87] P. S. Novikov, On the algorithmic unsolvability of the word problem in group theory, Trudy Mat. Inst. im. Steklov., 44 (1955), pp. 1–143. Google Scholar[88] Google Scholar[89] Google Scholar[90] Google Scholar[91] Google Scholar[92] Google Scholar[93] S. Pohlig and and M. Hellman, An improved algorithm for computing logarithms over GF(p) and its cryptographic significance, IEEE Trans. Inform. Theory, 24 (1978), pp. 106–110. iet IETTAW 0018-9448 IEEE Trans. Inf. Theory CrossrefISIGoogle Scholar[94] J. Pollard, Monte Carlo methods for index computation mod p, Math. Comp., 32 (1978), pp. 918–924. mcm MCMPAF 0025-5718 Math. Comput. ISIGoogle Scholar[95] J. Pollard, Factoring with cubic integers, Lecture Notes in Math., Vol. 1554, Springer, Berlin, 1993, 4–10 MR1321218 Google Scholar[96] J. Proos and and C. Zalka, Shor's discrete logarithm quantum algorithm for elliptic curves, Quantum Inf. Comput., 3 (2003), pp. 317–344. ag9 QICUAW 1533-7146 Quantum Inf. Comput. ISIGoogle Scholar[97] G. Purdy, A high‐security log‐in procedure, Comm. ACM, 17 (1974), pp. 442–445. cao CACMA2 0001-0782 Commun. ACM CrossrefISIGoogle Scholar[98] R. L. Rivest, , A. Shamir and , and L. Adleman, A method for obtaining digital signatures and public key cryptosystems, Comm. ACM, 21 (1978), pp. 120–126. cao CACMA2 0001-0782 Commun. ACM CrossrefISIGoogle Scholar[99] Google Scholar[100] T. Satoh, The canonical lift of an ordinary elliptic curve over a prime field and its point counting, J. Ramanujan Math. Soc., 15 (2000), pp. 247–270. Google Scholar[101] T. Satoh and and K. Araki, Fermat quotients and the polynomial time discrete log algorithm for anomalous elliptic curves, Comment. Math. Univ. St. Paul., 47 (1998), pp. 81–92. Google Scholar[102] T. Satoh, , B. Skjernaa and , and Y. Taguchi, Fast computation of canonical lifts of elliptic curves and its application to point counting, Finite Fields Appl., 9 (2003), pp. 89–101. CrossrefISIGoogle Scholar[103] O. Schirokauer, Discrete logarithms and local units, Philos. Trans. Roy. Soc. London Ser. A, 345 (1993), pp. 409–423. ptr PTRMAD 0962-8428 Philos. Trans. R. Soc. London, Ser. A CrossrefISIGoogle Scholar[104] R. Schoof, Elliptic curves over finite fields and the computation of square roots mod p, Math. Comp., 44 (1985), pp. 483–494. mcm MCMPAF 0025-5718 Math. Comput. ISIGoogle Scholar[105] R. Schoof, Nonsingular plane cubic curves, J. Combin. Theory Ser. A, 46 (1987), pp. 183–211. cta JCBTA7 0097-3165 J. Comb. Theory, Ser. A CrossrefISIGoogle Scholar[106] I. Semaev, Evaluation of discrete logarithms in a group of p‐torsion points of an elliptic curve in characteristic p, Math. Comp., 67 (1998), pp. 353–356. mcm MCMPAF 0025-5718 Math. Comput. CrossrefISIGoogle Scholar[107] Adi Shamir, A polynomial time algorithm for breaking the basic Merkle‐Hellman cryptosystem, IEEE, New York, 1982, 145–152 MR780392 Google Scholar[108] Google Scholar[109] P. W. Shor, Polynomial‐time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput., 26 (1997), 1484–1509. sim SMJCAT 0097-5397 SIAM J. Comput. LinkISIGoogle Scholar[110] Barry Mazur and , Karl Rubin, Pairings in the arithmetic of elliptic curves, Progr. Math., Vol. 224, Birkhäuser, Basel, 2004, 151–163 MR2058649 Google Scholar[111] Joseph Silverman, The xedni calculus and the elliptic curve discrete logarithm problem, Des. Codes Cryptogr., 20 (2000), 5–40 2001b:14042 CrossrefISIGoogle Scholar[112] Google Scholar[113] N. Smart, The discrete logarithm problem on elliptic curves of trace one, J. Cryptology, 12 (1999), pp. 193–196. jzq JOCREQ 0933-2790 J. Cryptology CrossrefISIGoogle Scholar[114] J. Solinas, Efficient arithmetic on Koblitz curves, Des. Codes Cryptogr., 19 (2000), pp. 195–249. CrossrefISIGoogle Scholar[115] Andreas Guthmann, Vigenère‐Verschlüsselung: Theorie und Praxis, Math. Semesterber., 47 (2000), 39–49 MR1820887 CrossrefGoogle Scholar[116] Google Scholar[117] Google Scholar[118] Google Scholar[119] Google Scholar[120] Google Scholar[121] Google Scholar[122] W. Waterhouse, Abelian varieties over finite fields, Ann. Sci. École Norm. Sup. (4), 2 (1969), pp. 521–560. a9b ZZZZZZ 0012-9593 Ann. Sci. Ec. Normale Super. Google Scholar[123] M. Wiener, Cryptanalysis of short RSA secret exponents, IEEE Trans. Inform. Theory, 36 (1990), pp. 553–558. iet IETTAW 0018-9448 IEEE Trans. Inf. Theory CrossrefISIGoogle Scholar[124] Google ScholarKeywordscryptographypublic keyelliptic curve Previous article Next article FiguresRelatedReferencesCited byDetails A Public Key Cryptosystem Using Cyclotomic Matrices25 May 2022 Cross Ref Searching on Encrypted E-Data Using Random Searchable Encryption (RanSCrypt) Scheme15 May 2018 | Symmetry, Vol. 10, No. 5 Cross Ref D-NTRU: More efficient and average-case IND-CPA secure NTRU variantInformation Sciences, Vol. 438 Cross Ref Integer Factorization Based Cryptography17 March 2017 Cross Ref Building Secure Public Key Encryption Scheme from Hidden Field EquationsSecurity and Communication Networks, Vol. 2017 Cross Ref Group-oriented encryption for dynamic groups with constant rekeying cost15 August 2016 | Security and Communication Networks, Vol. 9, No. 17 Cross Ref A Security Scheme for Video Streaming in Wireless Multimedia Sensor Networks15 October 2015 Cross Ref Anonymous Identity-Based Encryption with Bounded Leakage Resilience Cross Ref Signature Scheme Using the Root Extraction Problem on QuaternionsJournal of Applied Mathematics, Vol. 2014 Cross Ref Designing and Performance Analysis of a Proposed Symmetric Cryptography Algorithm Cross Ref Lattice Attacks on DSA Schemes Based on Lagrange's Algorithm Cross Ref Sieve Method for Polynomial Linear EquivalenceJournal of Applied Mathematics, Vol. 2013 Cross Ref Some lattice attacks on DSA and ECDSA16 September 2011 | Applicable Algebra in Engineering, Communication and Computing, Vol. 22, No. 5-6 Cross Ref EFFICIENT ALGORITHMS FOR THE BASIS OF FINITE ABELIAN GROUPS5 April 2012 | Discrete Mathematics, Algorithms and Applications, Vol. 03, No. 04 Cross Ref WEP and WPA Attacks Cross Ref A Pairwise Key Pre-distribution Scheme Based on Prior Deployment Knowledge Cross Ref Study of the effects of pairwise key pre-distribution scheme on the performance of a topology control protocol Cross Ref An Algorithm for Computing a Basis of a Finite Abelian Group Cross Ref Linear Time Algorithms for the Basis of Abelian Groups Cross Ref Double-Moduli Gaussian Encryption/Decryption with Primary Residues and Secret ControlsInternational Journal of Communications, Network and System Sciences, Vol. 04, No. 07 Cross Ref CRYPPAR: An efficient framework for privacy preserving association rule mining over vertically partitioned data Cross Ref A tree-based group key agreement scheme for secure multicast increasing efficiency of rekeying in leave operation Cross Ref Preventing Wormhole Attacks in Mobile Commerce Cross Ref A client/server implementation of an encryption system for fingerprint user authenticationKybernetes, Vol. 37, No. 8 Cross Ref Volume 46, Issue 4| 2004SIAM Review History Published online:04 August 2006 InformationCopyright © 2004 Society for Industrial and Applied MathematicsKeywordscryptographypublic keyelliptic curveMSC codes94A6011T7114G5068P25PDF Download Article & Publication DataArticle DOI:10.1137/S0036144503439190Article page range:pp. 599-634ISSN (print):0036-1445ISSN (online):1095-7200Publisher:Society for Industrial and Applied Mathematics