The cryptographic security of truncated linearly related variables

In this paper we describe a polynomial time algorithm for computing the values of variables x1, … xk when some of their bits and some linear relationships between them are known. The algorithm is essentially optimal in its use of information in the sense that it can be applied as soon as the values of the xi become uniquely determined by the constraints. Its cryptanalytic significance is demonstrated by two applications: breaking linear congruential generators whose outputs are truncated, and breaking Blum's protocol for exchanging secrets.