The discrete logarithm modulo a composite hides 0(n) Bits

摘要

In this paper we consider the one-way function fg,N(X) = gX (mod N), where N is a Blum integer. We prove that under the commonly assumed intractability of factoring Blum integers, all its bits are individually hard, and the lower as well as upper halves of them are simultaneously hard. As a result, fg,N can be used in efficient pseudo-random bit generators and multi-bit commitment schemes, where messages can be drawn according to arbitrary probability distributions.