The discrete log is very discreet
A. W. Schrift, Adi Shamir · 1990
In this paper we consider the one-way function fg,N(X) = gX (modN), where N is a Blum integer.We prove that under the commonly assumed intractability of factoring Blum integers, almost all its bits are individually hard, and half 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.