Public-Key Cryptography - A Classical Introduction to Cryptography: Applications for Communications Security - page 239

We can indeed show that msb(2 i x mod N ) = 0 if and only if there exists an integer k

such that

2 k
2 i + 1 ≤

x
N <

2 k + 1

.

2 i + 1

So this algorithm simply gets the binary expansion of x / N .

The least (and most) significant bits of the plaintext are thus called hard core
bits since recovering them can be used to break the cryptosystem. Further studies can
additionally show that even approximating those bits, i.e. being able to predict them
with a nontrivial advantage, can also be used to break the scheme.

There are bits which are not hard-core, e.g. the Jacobi symbol. Let

x
N

1) bit( x )

( − =

and bitdec be defined as above. We can easily compute bitdec by noticing that

y
N

1) bitdec( y )

( − =

The plain RSA encryption indeed preserves the Jacobi symbol since e is odd and
x e

x e
N

x
N

e x

N

mod N
N

= = = .

9.3.7 Back to the Encryption Security Assumptions

After having seen all these attacks on public-key encryption schemes, a question re-
mains: what minimal security requirements must such a scheme satisfy? There are so
many attack scenarii that we have seen so far that the intuitive notion of encryption
security, i.e. that the decryption problem is computationally hard, is not sufficient. For
instance the decryption problem could in theory still be hard even though recovering
half of the plaintext would be easy, but this would not match our intuition about security.
Currently, there are two popular notions of security against three notions of adversaries,
leading us to six possible definitions.

First of all, Shafi Goldwasser and Silvio Micali proposed the notion of semantic
security (see Ref. [77]). This notion intuitively means that the ciphertext leaks no
interesting bit of information about the plaintext. This notion is described as a game
between a challenger and an adversary. The game runs as follows (see Fig. 9.9).

1. First of all, the challenger and the adversary are given the cryptosystem.
2. The challenger generates a matching pair of public and secret keys and discloses
the public one.
3. The adversary selects two plaintexts x 0 and x 1 and sends them to the challenger.