[Resource Topic] 2006/046: Efficient Primitives from Exponentiation in Zp

Welcome to the resource topic for 2006/046

Efficient Primitives from Exponentiation in Zp

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

ePrint: https://eprint.iacr.org/2006/046

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .