You are looking at a specific version 20060210:213609 of this paper. See the latest version.

Paper 2006/046

Efficient Primitives from Exponentiation in Zp

Shaoquan Jiang

Abstract

Since Diffie-Hellman \cite{DH76}, many secure systems, based on discrete logarithm or Diffie-Hellman assumption in $\mathbb{Z}_p$, were introduced in the literature. In this work, we investigate the possibility to construct efficient primitives from exponentiation techniques over $\mathbb{Z}_p$. 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 $\mathbb{Z}_p^*$ that are provably secure under standard assumptions. If an appropriate precomputation is allowed, our generator can produce $O(\log\log p)$ 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. \cite{W+05,WY05,WYY05}.

Metadata
Available format(s)
PDF PS
Category
Foundations
Publication info
Published elsewhere. Unpublished
Contact author(s)
jiangshq @ calliope uwaterloo ca
History
2006-02-10: received
Short URL
https://ia.cr/2006/046
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.