More efficient DDH pseudorandom generators |
| |
Authors: | Hongsong Shi Shaoquan Jiang Zhiguang Qin |
| |
Institution: | 1.School of Computer Science and Engineering,University of Electronic Science and Technology of China,ChengDu,China;2.Center for Information Security and Cryptography (CISaC),University of Calgary,Calgary,Canada |
| |
Abstract: | In this paper, we first show a DDH Lemma, which states that a multi-variable version of the decisional Diffie–Hellman problem
is hard under the standard DDH assumption, where the group size is not necessarily known. Our proof, based on a self-reducibility
technique, has a small reduction complexity. Using DDH Lemma, we extend the FSS pseudorandom generator of Farashahi et al.
to a new one. The new generator is almost twice faster than FSS while still provably secure under the DDH assumption. Using
the similar technique for the RSA modulus, we improve the Goldreich–Rosen generator. The new generator is provably secure
under the factoring assumption and DDH assumption over
\mathbbZN*{\mathbb{Z}_N^*}. Evidently, to achieve the same security level, different generators may have different security parameters (e.g., distinct
length of modulus). We compare our generators with other generators under the same security level. For simplicity, we make
comparisons without any pre-computation. As a result, our first generator is the most efficient among all generators that are provably secure
under standard assumptions. It has the similar efficiency as Gennaro generator, where the latter is proven secure under a
non-standard assumption. Our second generator is more efficient than Goldreich–Rosen generator. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|