<<

. 8
( 11 .)



>>

. First, set x1 = s. Then, for i = 1, . . . , :
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

<<

. 8
( 11 .)



>>