Paper 2006/046

Efficient Primitives from Exponentiation in Zp

Shaoquan Jiang


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}.

Available format(s)
Publication info
Published elsewhere. Unpublished
Contact author(s)
jiangshq @ calliope uwaterloo ca
2006-02-10: received
Short URL
Creative Commons Attribution


      author = {Shaoquan Jiang},
      title = {Efficient Primitives from Exponentiation in Zp},
      howpublished = {Cryptology ePrint Archive, Paper 2006/046},
      year = {2006},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.