期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

Solving the Multi-discrete Logarithm Problems over a Group of Elliptic Curves with Prime Order

Solving the Multi-discrete Logarithm Problems over a Group of Elliptic Curves with Prime Order
原文传递
导出
摘要 In this paper, we discuss the expected number of steps in solving multi-discrete logarithm problems over a group of elliptic curves with prime order by using Pollard＇s rho method and parallel collision search algorithm. We prove that when using these algorithms to compute discrete logarithms, the knowledge gained through computing many logarithms does not make it easier for finding other logarithms. Hence in an elliptic cryptosystem, it is safe for many users to share the same curve, with different private keys. In this paper, we discuss the expected number of steps in solving multi-discrete logarithm problems over a group of elliptic curves with prime order by using Pollard＇s rho method and parallel collision search algorithm. We prove that when using these algorithms to compute discrete logarithms, the knowledge gained through computing many logarithms does not make it easier for finding other logarithms. Hence in an elliptic cryptosystem, it is safe for many users to share the same curve, with different private keys.
作者 Jun Quan LI Mu Lan LIU Liang Liang XIAO
机构地区 Academy of Mathematics and Systems Science
出处 《Acta Mathematica Sinica,English Series》 SCIE CSCD 2005年第6期1443-1450,共8页 数学学报（英文版）
基金 NNSF of China.No.90304012 973 Project,No.2004CB318000
关键词 Pollard＇s rho method Parallel collision search algorithm Elliptic curve Discrete logarithm Distinguished point Pollard＇s rho method, Parallel collision search algorithm, Elliptic curve, Discrete logarithm, Distinguished point
分类号 O17 [理学—基础数学]
  • 相关文献

参考文献9

  • 1Menezes, A, Okamoto, T, Vanstone, S. A.: Reducing elliptic curve logarithms to logarithms in a finite field. IEEE Transactions on Information Theory, 39, 1639-1646 (1993).
  • 2Smart, N. P.: The discrete logarithm problem on elliptic curves of trace one, J. Cryptology, 12(3), 193-196(1999).
  • 3Satoh, T, Arako, K.: Fermat quotients and the polynomial time discrete log algorithm for anomalous elliptic curves. Commentarii Math. Univ. St. Pauli, 47(1), 81-92 (1998).
  • 4Silverman, J. H, Suzuki, J.: Elliptic curve discrete logarithms and the index calculus, Proceedings of ASIACRYPT'98, to appear.
  • 5Balasubramanian, R,Koblitz, N.: The improbability that an elliptic curve has subexponential discrete log problem under the Menezes-Okamoto Vanstone algorithm. J. Cryptology, 11, 114-145 (1998).
  • 6van Oorschot, P, C, Wiener, M.: Parallel collision search with cryptanalytic applications. J. Cryptology,12, 1-28 (1999).
  • 7Knuth, D. E.: Big omicron and big omega and big theta. SIGACT News, 8(2), 18-24 (1976).
  • 8Pollard, J.: A Monte Carlo method for factorization. BIT, 32(143), 918-924 (1978).
  • 9Nishimura, K, Sibuya, M.: Probability to meet in the middle. J. Cryptology, 2(1), 13-22 (1990).
Acta Mathematica Sinica,English Series
2005年 第6期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部