1. View xi as an integer in [0, N ’ 1] and let bi ∈

BLUM INTEGER {0, 1} be the least signi¬cant bit of xi .

2. Set xi+1 = xi2 ∈ Z N.

The output sequence is b1 b2 · · · b ∈ {0, 1} .

A positive integer n is a Blum integer if it is the

product of two distinct primes p, q where p ≡ q ≡ The generator can be viewed as a special case of

3 (mod 4). Blum integers are of interest in cryp- the general Blum“Micali generator [2]. To see this,

tography because the mapping we show that the generator is based on a one-way

permutation (see one-way function and substitu-

x ← x 2 mod n

tions and permutations) and a hard-core predicate

of that permutation. For an integer N let QR N =

is believed to be a trapdoor permutation (see

(Z— )2 denote the subgroup of quadratic residues

trapdoor one-way function) on the quadratic N

in Z— and let FN : Z N ’ Z N denote the function

residues modulo n. That is, exactly one of the four N

FN(x) = x 2 ∈ Z N. For Blum integers the function

square roots of a quadratic residue modulo a Blum

integer n is itself a quadratic residue. Inverting FN is a permutation (a one-to-one map) of the sub-

the permutation is equivalent to factoring n, but group of quadratic residues QR N. In fact, it is not

is easy given p and q. This fact is exploited in the dif¬cult to show that FN is a one-way permuta-

Blum“Blum“Shub PRNG. tion of QR N, unless factoring Blum integers is easy.

The permutation can be inverted when the Now that we have a one-way permutation we need

prime factors p and q are known by computing a hard-core bit of the permutation to construct a

both square roots modulo each factor, selecting Blum“Micali-type generator. Consider the predi-

cate B : QR N ’ {0, 1} that on input x ∈ QR N views

the square root modulo each factor which itself

is a square, then applying the Chinese remainder x as an integer in [1, N] and outputs the least sig-

theorem. Conveniently, the square roots modulo ni¬cant bit of x. Blum, Blum, and Shub showed

the prime factors of a Blum integer can be com- that B(x) is a hard-core predicate of FN assuming

puted with a simple formula: the solutions of x 2 ≡ it is hard to distinguish quadratic residues in Z N

a (mod p) are given by x ≡ ±a ( p+1)/4 (mod p) when from nonresidues in Z N with Jacobi symbol 1. Ap-

p ≡ 3 (mod 4). The appropriate square root can be plying the Blum“Micali construction to the one-

selected by computing the Legendre symbol. way permutation FN and the hard-core predicate

See also modular arithmetic, prime number. B produces the generator above. The general the-

orem of Blum and Micali now shows that the gen-

Burt Kaliski erator is secure assuming it is hard to distinguish

quadratic residues in Z N from nonresidues in Z N

with Jacobi symbol 1. Vazirani and Vazirani [5]

improved the result by showing that B(x) is a hard-

BLUM“BLUM“SHUB

core predicate under the weaker assumption that

PSEUDORANDOM BIT factoring random Blum integers is intractable.

GENERATOR One can construct many different hard-core

predicates for the one-way permutation FN de¬ned

above. Every such hard-core bit gives a slight vari-

The Blum“Blum“Shub (BBS) pseudorandom bit

ant of the BBS generator. For example, Hastad and

generator [1] is one of the most ef¬cient pseudo-

Naslund [3] show that for most 1 ¤ j < log2 N the

random number generators known that is prov-

predicate Bj(x) : QR N ’ {0, 1} that returns the jth

ably secure under the assumption that factor-

bit of x is a hard-core predicate of FN assuming fac-

ing large composites is intractable (see integer

toring Blum integers is intractable. Consequently,

factoring). The generator makes use of modular

one can output bit j of xi at every iteration and

arithmetic and works as follows:

Setup. Given a security parameter „ ∈ Z as input, still obtain a secure generator, assuming factoring

generate two random „ -bit primes p, q where Blum integers is intractable.

Blum“Goldwasser public key encryption system 51

One can improve the ef¬ciency of the gen- encryption whose security is based on the dif-

eral Blum“Micali generator by outputting mul- ¬culty of factoring Blum integers. The system

tiple simultaneously secure hard-core bits per makes use of modular arithmetic and works as

iteration. For the function FN it is known that follows:

Key Generation. Given a security parameter „ ∈

the O(log log N) least signi¬cant bits are si-

Z as input, generate two random „ -bit primes

multaneously secure, assuming factoring Blum

p, q where p = q = 3 mod 4. Set N = pq ∈ Z.

integers is intractable. Consequently, the simu-

lator remains secure (asymptotically) if one out- The public key is N and private key is ( p, q).

Encryption. To encrypt a message m =

puts the O(log log N) least signi¬cant bits of xi per

m1 . . . m ∈ {0, 1} :

iteration.

1. Pick a random x in the group Z— and set x1 =

Let I be the set of integers I = {1, . . . , N}. We N

—

x ∈ Z N.

2

note that for a Blum integer N and a generator

g ∈ Z— , Hastad et al. [4] considered the function 2. For i = 1, . . . , :

N

G N,g : I ’ Z N de¬ned by G N,g (x) = g x ∈ Z N. They (a) View xi as an integer in [0, N ’ 1] and

showed that half the bits of x ∈ I are simultane- let bi ∈ {0, 1} be the least signi¬cant bit

ously secure for this function, assuming factoring of xi .

(b) Set ci = mi • bi ∈ {0, 1}.

Blum integers is intractable. Therefore, one can

(c) Set xi+1 = xi2 ∈ Z— .

build a Blum“Micali generator from this function N

3. Output (c1 , . . . , c , x +1 ) ∈ {0, 1} — Z N as the

that outputs (log N)/2 bits per iteration. The re-

sulting pseudorandom generator is essentially as ciphertext.

Decryption. Given a ciphertext (c1 , . . . , c , y) ∈

ef¬cient as the BBS generator and is based on the

{0, 1} — Z N and the private key ( p, q) decrypt

same complexity assumption.

as follows:

1. Since N is a Blum integer, •(N)/4 is odd

Dan Boneh

(see Euler™s totient function) and therefore

2 +1 has an inverse modulo •(N)/4. Let t =

References

(2 +1 )’1 mod (•(N)/4).

2. Compute x1 = yt ∈ Z— . Observe that if y ∈

[1] Blum, L., M. Blum, and M. Shub (1983). “Compari- N

(2 +1 ) (t·2 +1 )

—2

= y ∈ Z— .

=y

son of two pseudo-random number generators.” Ad- (Z N) then x1 N

3. Next, for i = 1, . . . , :

vances in Cryptology”CRYPTO™82, eds. Plenum D.

Chaum, R.L. Rivest, and A.T. Sherman. Springer- (a) View xi as an integer in [0, N ’ 1] and

Verlag, Berlin, 61“78. let bi ∈ {0, 1} be the least signi¬cant bit

[2] Blum, M. and S. Micali (1982). “How to generate

of xi .

cryptographically strong sequences of pseudoran-

(b) Set mi = ci • bi ∈ {0, 1}.

dom bits.” Proceedings of FOCS™82, 112“117.

(c) Set xi+1 = xi2 ∈ Z— .

[3] Hastad, J. and M. Naslund (2004). “The secu- N

4. Output (m1 , . . . , m ) ∈ {0, 1} as the plaintext.

rity of all RSA and discrete log bits.” Journal of

Semantic security of the system (against a pas-

the ACM. Extended abstract in Proc. of FOCS™98,

sive adversary) follows from the proof of secu-

510“521.

rity of the Blum“Blum“Shub generator. The proof

[4] Hastad, J., A. Schrift, and A. Shamir (1993). “The

discrete logarithm modulo a composite hides o(n) of security shows that an algorithm capable of

bits.” Journal of Computer and System Sciences mounting a successful semantic security attack is

(JCSS), 47, 376“404. able to factor the Blum integer N in the public

[5] Vazirani, U. and V. Vazirani (1984). “Ef¬cient and key.

secure pseudo-random number generation.” Pro-

We note that the system is XOR malleable:

ceedings of FOCS™84, 458“463.

given the encryption C = (c1 , . . . , c , y) of a mes-

sage m ∈ {0, 1} it is easy to construct an encryp-

tion of m • b for any chosen b ∈ {0, 1} (without

knowing m). Let b = b1 · · · b ∈ {0, 1} . Simply set

BLUM“GOLDWASSER

C = (c1 • b1 , . . . , c • b , y). Since the system is

PUBLIC KEY ENCRYPTION XOR malleable it cannot be semantically secure

SYSTEM under a chosen ciphertext attack.

Interestingly, the same reduction given in the

The Blum“Goldwasser public key encryption proof of semantic security shows that a chosen ci-

system combines the general construction of phertext attacker can factor the modulus N and

Goldwasser“Micali [5] with the concrete Blum“ therefore recover the private key from the public

Blum“Shub pseudorandom bit generator [2] to key. Consequently, as it is, the system completely

obtain an ef¬cient semantically secure public key falls apart under a chosen ciphertext attack. When

52 Bolero.net

using the system one must use a mechanism to it has been known as Bolero since 1994, when an

defend against chosen ciphertext attacks. For ex- early version was piloted in a project funded by the

ample, Fujisaki and Okamoto [4] provide a gen- European Commission.

eral conversion from semantic security to chosen Bolero.net handles not just Bs/L but all other

ciphertext security in the random oracle model. trade documentation too. However, it is the title

However, in the random oracle model one can con- function of the B/L which gives rise to the most

struct more ef¬cient chosen ciphertext secure sys- interesting isuses.

tems that are also based on the dif¬culty of factor- In essence, the B/L is issued as a message from

ing [1, 3]. the shipowner to the original cargo owner, digitally

signed and handled via bolero.net™s secure mes-

Dan Boneh sage handling facility, the Core Messaging Plat-

form (CMP). The CMP, when sent a new B/L,

also passes a message to a bolero.net component

References

called the Title Registry (TR). The TR sets up a

new record in its database and from this point

[1] Bellare, Mihir and Phillip Rogaway (1996). “The

on, it is the information about ownership held in

exact security of digital signatures: How to sign

the TR which is ultimately authoritative in any

with RSA and Rabin.” Advances in Cryptology”

dispute.

EUROCRYPT™96, Lecture Notes in Computer Sci-

ence, vol. 1070, ed. U. Maurer. Springer-Verlag, When the electronic B/L is being traded, the TR

Berlin, 399“416. is updated through digitally signed messages from

[2] Blum, L., M. Blum, and M. Shub (1983). “Compari- the users via the CMP. The TR will only accept

son of two pseudo-random number generators.” Ad- instructions from the user currently recorded as

vances in Cryptology”CRYPTO™83, ed. D. Chaum.

the “holder,” i.e., owner of the title being traded.

Springer-Verlag, Berlin, 61“78.

This is a system similar to that operated by most

[3] Boneh, Dan (2001). “Simpli¬ed OAEP for the RSA

dematerialized share trading schemes.

and Rabin functions.” Advances in Cryptology”

To enable electronic trading of negotiable docu-

CRYPTO 2001, Lecture Notes in Computer Science,

ments such as the B/L, all you need is a database

vol. 2139, ed. J. Kilian. Springer-Verlag, Berlin.

operated by a trusted third party, and digital

[4] Fujisaki, E. and T. Okamoto (1999). “Secure inte-

signatures which can be veri¬ed by that party.

gration of asymmetric and symmetric encryption

schemes.” Advances in Cryptology”CRYPTO™99, Bolero.net is that trusted third party, and it oper-

Lecture Notes in Computer Science, vol. 1666, ates its own Certi¬cation Authority, though there

ed. J. Wiener. Springer-Verlag, Berlin, 537“ is a project under way to accept certi¬cates from

554. other issuers in the future.

[5] Goldwasser, S. and S. Micali (1984). “Probabilistic

As the traders would also like to keep their in-

encryption.” Journal of Computer and System Sci-

formation con¬dential, the communications are

ence (JCSS), 28 (2), 270“299.

handled as SSL protected exchanges (see Secure

Socket Layer). The legal security of the transac-

tion, i.e. the certainty that a trade carried out

BOLERO.NET over bolero.net will be treated as legally binding

by the courts, is provided via a multilateral user

contract, known as the Rule Book. All users are

When exporters and importers wish to trade in

bound by this contract and it creates a legal safety

goods onboard a ship, they use a document of ti-

net which ensures that the traditional function-

tle called a Bill of Lading (or B/L for short). It is

ality of the ancient B/L can still be provided by

issued by the ship operator as a receipt for the

electronic means.

goods and, because he will only release the cargo

For more information, see www.bolero.net and

against production of this document, the B/L has

www.bolerassociation.org

been used for centuries for trading and as ¬nancial

security.

Peter Landrock

Making the functionality of this document avail-

able by electronic means is an undertaking simi-

lar to that of putting share trading online, and it

is the job of bolero.net, a service operated since

BOOLEAN FUNCTIONS

1999 by the Through Transport Club, a mutual

marine insurer, and S.W.I.F.T., the banks™ coop-

eratively owned data network operator. The ori- Boolean functions play a central role in the de-

gins of the project stem from the mid-1980s and sign of most symmetric cryptosystems and in their

Boolean functions 53

security. In stream ciphers, they are usually used x1 x2 x3 f(x)

to combine the outputs to several linear feedback 0 0 0 0

shift registers (see the corresponding entry and 0 0 1 1

Combination generator), or to ¬lter (and combine) 0 1 0 0

the contents of a single one (see Filter generators). 0 1 1 0

The sequence of their output, during a certain

1 0 0 0

number of clock cycles, then produces the pseudo-

1 0 1 1

random sequence which is used in a Vernam cipher

1 1 0 0

(that is, which is bitwisely added to the plaintext

1 1 1 1

to produce the ciphertext). In block ciphers (see

(1 • x1 )(1 • x2 ) x3 • x1 (1 • x2 ) x3 •

Block cipher, Data Encryption Standard (DES), has ANF:

x1 x2 x3 = x1 x2 x3 • x2 x3 • x3 . Indeed, the expres-

Advanced Encryption Standard (Rijndael/AES)),

sion (1 • x1 )(1 • x2 ) x3 , for instance, equals 1

the S-boxes are designed by appropriate composi-

if and only if 1 • x1 = 1 • x2 = x3 = 1, that is,

tion of nonlinear Boolean functions.

(x1 , x2 , x3 ) = (0, 0, 1).

An n-variable Boolean function f is a function

from the set F2 of all binary vectors x = (x1 , . . . , xn )

n