New Results on The Hardness of ElGamal And RSA
Bits Basing on Binary Expansions
ZHENG-QI KANG
State Key Lab of Information Security
Institute of Information Engineering
Chinese Academy of Sciences
Beijing,10093, P.R.China
KE-WEI LV
DCS Research Center
Institute of Information Engineering
Chinese Academy of Sciences
Beijing,10093, P.R.China
kwlv@is.ac.cn
Abstract—González Vasco et al. extend the area of application
of algorithms for the hidden number problem in 2004. Using this
extension and relations among the bits in ࢞ܕܗ܌ and binary
fraction expansion of ࢞ܕܗ܌Ȁ , we present a probabilistic
algorithm for some trapdoor functions to recover a hidden
message when an imperfect oracle is given of predicting most
significant bits in hidden message. We show that computing the
most significant bit in message encrypted by ElGamal encryption
function is as hard as computing the entire plaintext, and so is
RSA.
Keywords—Most Significant Bit; RSA; ElGamal; Hidden
Number Problem
I. INTRODUCTION
In 1996, Boneh and Venkatesan[1] proposed a problem,
called Hidden Number Problem (HNP): Fix a prime and k,
let
ܱ
ఈǡ
ሺݔሻ be an oracle that on input x computes the k
most
significant bits of ߙ݃
௫
. The task is to findߙ given
access to the oracle ܱ
ఈǡ
ሺݔሻ. That is, for ͳ݅݀, we try to
recover ߙ given
ሺݐ
ǡܯܵܤ
ሺ
ߙݐ
ሻ
ሻ
. Here the k most
significant bits ܯܵܤ
ሺ
ߙݐ
ሻ
is defined to be the integer t such
that
ሺ
ݐെͳ
ሻ
ȉȀʹ
ߙݐ
ݐ ȉ Ȁʹ
and d is a polynomial
function of . Here ߙ is called a hidden number.
Using HNP, Boneh and Venkatesan[1,2] and Shparlinski et
al.[3,4,5] analyzed bits security of Diffie-Hellman Scheme
(DH), ElGamal cryptosystem (EG), Shamir Message Passing
Scheme (3PASS) and Okamato Conference Key Sharing
(CONF). They gave reduction from computing the first
ߠൌܱሺ
ඥ
ɒ ȉ ሺሻȀሻ most significant bits of
plaintext in DH, EG, 3PASS and CONF to computing the
entire plaintext respectively, where
U is an arbitrary absolute
constant. Shparlinski et al. [8, 10] studied extensions of HNP
and its applications; Su at el. [13-15] studied the bits security
of two variants of Paillier trapdoor function; Hlaváš et al. [7]
gave a polynomial time algorithm to attack certain DSA-like
signature schemes using extension of HNP. More studies could
be found in [10, 12], which is a survey of all kinds of the
hidden number problem and its applications.
Although HNP has been studied for over ten years, most
algorithms for HNP need a perfect oracle on bits of the hidden
number. By extending the area of application of hidden number
problem, González Vasco, Näslund and Shparlinski [3] obtain
new bit security properties of the Diffie-Hellman key exchange
scheme. They show one can obtain bit security results for the
Diffie-Hellman secret key of the same strength as [1,4] with
two types of imperfect oracles, roughly corresponding to the
classical "Monte Carlo"-type algorithms, as well as the "Las
Vegas"-type algorithm, and also show a trade-off between the
tolerated error rate and the number of unpredictable bits.
Concretely, oracle outputs
ܱሺɉሻ most significant bits of
plaintext in DH, EG, 3PASS and CONF for "Monte Carlo"
type, where
ɉis an arbitrary absolute constant, and outputs
ܱሺ
ඥ
ɒ ȉ ሺሻȀሻ most significant bits of the
plaintext in DH, EG, 3PASS and CONF for "Las Vegas" type,
where
U is an arbitrary absolute constant.
In this paper, we first discuss relations among the bits in
binary expansion of ݔ and fractional 2-adic expansion of
ݔȀ
for an odd prime p. Basing on the extension of [3]
and these relations, we present an algorithm for hidden number
problem for any k
>0 with a "Monte Carlo" type oracle on the
most significant bits. Then, we generalize these results to the
case modulo an odd composite. Finally, given a more realistic
oracle than [3], we analyze the bits security of El Gamal Public
Key encryption scheme and RSA as applications.
II. PRELIMINARIES
A. Notation
1) Notation 1: Let be an n-bit odd prime and , where
ܨ
is a finite field of p elements. Throughout the paper we use
ݔ݉݀ or ሾݔሿ
to denote the unique integer a in
[0 1]p
satisfying ݔؠܽ݉݀.
2015 2nd International Conference on Information Science and Control Engineering
978-1-4673-6850-6/15 $31.00 © 2015 IEEE
DOI 10.1109/ICISCE.2015.81
336
2015 2nd International Conference on Information Science and Control Engineering
978-1-4673-6850-6/15 $31.00 © 2015 IEEE
DOI 10.1109/ICISCE.2015.81
336