Bit extraction, hard-core predicates and the bit security of RSA

by Näslund, Mats

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, andb(x) isone (or more) bit(s) in the binary representation of h(x). We study the two families: – Affine functions on GF[2n](n= ?log2(x)? +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. iii • Finally, we study the complexity of computing the hard-core b itself. We prove that a general family of boolean hard-core functions (only assuming f to be one-way) requires boolean circuits of depth ? (log n/ log log n) or super-polynomial size to be realized. This lower bound is essentially tight. For constant-depth circuits, an exponential lower bound on the size is obtained. For the second problem, we obtain the following results. • Fixing a bias ?, to explore the rate (as a function of n) at which the output bias, |E[b(X1,... ,Xn)]|, can tend to zero for a function b : {?1, 1}? ? {?1, 1}, we classify the behavior of the natural normalized quantity ?(?) ? inf b [ ? ] n lim |E[b(X1,... ,Xn)]| , n?? this infimum taken over all such b. We show that when ? ? Q, ?(?) = 1 1+? r s ,where 2 = s,and(r, s) =1. We then explore the case where ? is irrational. We prove a new metrical theorem concerning multidimensional Diophantine approximation from which we show that for (Lebesgue) almost all biases ?, ?(?)=0. Finally, we show that (real) algebraic biases exhibit curious “boundary” behavior, falling into two classes. I. Those algebraics ? for which ?(?) > 0 and furthermore, c1 ? ?(?) ? c2 where c1 and c2 are positive constants depending only on ?’s algebraic characteristics (and not its magnitude). II. Those algebraics ? for which there exist n>0andb:{?1, 1}n ? {?1, 1} so that E[b(X1,... ,Xn)] = 0. This classification excludes the possibility that n?|E[b(X1,... ,Xn)]| limits to zero for algebraics. For rational and algebraic biases, we also study the computational problem arising from restricting b to be a polynomial time computable function.