Bit extraction, hard-core predicates and the bit security of RSA
Mats Näslund · 1998
This thesis presents results on bit security and bit extraction. 1. A function b(·) is called secure or a hard-core function for a given function f(·), if for all probabilistic polynomial time algorithms, the information f(x) does not significantly aid in distinguishing b(x) from a random string of the same length. The benefit of studying hard-core functions is that they provide insight to the security of cryptosystems and means to construct pseudo-random generators. 2. The bit extraction problem is the problem of transforming n independent, identically biased, {−1, 1}-valued random variables, X1, . . . , Xn into a single {−1, 1} value, b(X1, . . . , Xn), so that this result is as unbiased as possible. (A {−1, 1} random variable Xi has bias β if E[Xi] = β.) In general, no function b produces a completely unbiased result. We perform the first study of the relationship between the bias β of these Xi and the rate at which b(X1, . . . , Xn) can converge to an unbiased {−1, 1} random variable as n→∞. Although our main interest in this problem is information theoretic, the access to true random bits is a primary tool in computer science and many other research areas. Since one does not always have access to a perfect (unbiased) random source, it may be necessary to simulate such. The first problem is considered in a purely complexity theoretic setting, whereas as mentioned, the second is mainly studied from an information theoretic point of view. For problem 1, we demonstrate the following results. • We consider the case when f is any one-way function and where h is chosen randomly from a family of strong universal hash functions, and b(x) is one (or more) bit(s) in the binary representation of h(x). We study the two families: – Affine functions on GF[2] (n = blog2(x)c + 1). – Affine functions on Zp, p an Ω(n)-bit prime. We show individual security for all bits in both cases, and both types of functions are also shown to have O(log n) bits that are simultaneously secure. • Next, we study the case when f(x) = EN (x) is RSA encryption and b(x) is a single bit in the binary representation of x. We show that given EN (x), predicting any single bit in x with non-negligible advantage over the trivial guessing strategy, is (through a polynomial time reduction) as hard as breaking RSA.