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

Abstract (Summary)

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.
Bibliographical Information:

Advisor:

School:Kungliga Tekniska högskolan

School Location:Sweden

Source Type:Doctoral Dissertation

Keywords:

ISBN:91-7170-295-4

Date of Publication:01/01/1998