Efficient Primitives from Exponentiation in
详细信息 查看全文
- 作者：Shaoquan Jiang
- 刊名：Lecture Notes in Computer Science
- 出版年：2006
- 出版时间：2006
- 年：2006
- 卷：4058
- 期：1
- 页码：pp.259-270
- 全文大小：460 KB
- 刊物类别：Computer Science
- 刊物主题：Artificial Intelligence and Robotics
Computer Communication Networks
Software Engineering
Data Encryption
Database Management
Computation by Abstract Devices
Algorithm Analysis and Problem Complexity - 出版者：Springer Berlin / Heidelberg
- ISSN：1611-3349
文摘
Since Diffie-Hellman [12], many secure systems, based on discrete logarithm or Diffie-Hellman assumption in 
, were introduced in the literature. In this work, we investigate the possibility to construct efficient primitives from exponentiation techniques over 
. Consequently, we propose a new pseudorandom generator, where its security is proven under the decisional Diffie-Hellman assumption. Our generator is the most efficient among all generators from 
that are provably secure under standard assumptions. If an appropriate precomputation is allowed, our generator can produce O(loglogp) bits per modular multiplication. This is the best possible result in the literature (even improved by such a precomputation as well). Interestingly, our generator is the first provably secure under a decisional assumption and might be instructive for discovering potentially more efficient generators in the future. Our second result is a new family of universally collision resistant hash family (CRHF). Our CRHF is provably secure under the discrete log assumption and is more efficient than all previous CRHFs that are provably secure under standard assumptions (especially without a random oracle). This result is important, especially when the unproven hash functions (e.g., MD4, MD5, SHA-1) were broken by Wang et al. [37, 38, 39].
, were introduced in the literature. In this work, we investigate the possibility to construct efficient primitives from exponentiation techniques over . Consequently, we propose a new pseudorandom generator, where its security is proven under the decisional Diffie-Hellman assumption. Our generator is the most efficient among all generators from that are provably secure under standard assumptions. If an appropriate precomputation is allowed, our generator can produce O(loglogp) bits per modular multiplication. This is the best possible result in the literature (even improved by such a precomputation as well). Interestingly, our generator is the first provably secure under a decisional assumption and might be instructive for discovering potentially more efficient generators in the future. Our second result is a new family of universally collision resistant hash family (CRHF). Our CRHF is provably secure under the discrete log assumption and is more efficient than all previous CRHFs that are provably secure under standard assumptions (especially without a random oracle). This result is important, especially when the unproven hash functions (e.g., MD4, MD5, SHA-1) were broken by Wang et al. [37, 38, 39].