~

ELECTRONICS LETTERS 70th April 1997 Vol. 33 No. 8 677

Acknowledgments: P. Assun@o would like to acknowledge the financial support of Instituto PolitEcnico de Leiria and JNICT, Praxis XXI: Sub-Programa CiEncia e Tecnologia do P Quadro Comunitario de Apoio, Portugal.

0 IEE 1997 Electronics Letters Online No: 19970482 P.A.A. Assunqiio and M. Ghanbari (Department of Electronic Systems Engineering, University of Essex, Colchester, CO4 3SQ, United Kingdom)

6 March 1997

E-mail: paaass@essex.ac.uk

References

ASSUNCAO, P., and GHANBARI, M.: ‘Post-processing of MPEG2 coded video for transmission at lower bit rates’. IEEE Int. Conf. Acoustics, Speech, and Signal Processing, ICASSP’96, Atlanta, USA, May 1996, Vol. 4, pp. 1998-2001 KEESMAN, G , HELLINGHUIZEN, R., HOEKSEMA, F., and HEIDEMAN, G.: ‘Transcoding of MPEG2 bitstreams’, Signal Process.: Image Commun., 1996, 8, pp. 481-500 ISO/IEC, ‘Test Model 5, ISO/IEC JTCl/SC29/WGll/NO400, MPEG93/457’. April 1993 SHOHAM, Y . , and GERSHO, A.: ‘Efficient bit allocation for an arbitrary set of quantisers’, ZEEE Trans., 1988, ASSP-36, pp. 1445-1453 RAMCHANDRAN, K., and VETTERLI, M.: ‘Best wavelet packet bases in a rate-distrotion sense’, IEEE Trans. Image Process., 1993, 2, pp. 160-175

Blum-Blum-Shub generator

C. Ding

Indexing term: Random number generation

such a special Blum integer, the least period of the binary sequence b- is controllable.

With the above choice of the two primes we can only say that the least period of the output sequences of the Blum-Blum-Shub generator divides 2p2q2, but cannot guarantee that their least period divides p2q2. So results described in [2] cannot be used to control the linear span of the output sequences of this generator. However, we have the following result.

Proposition 1: Let N = pq, where p , q are special, and let x, be a quadratic residue modulo N. Then for the sequence 6- over GF(q)

where L(b-) denotes the linear span of the sequence. A proof of this result can be outlined as follows. From the

above discussion, the output sequence h- has a period 2p2q2 (not necessarily the least period). Note that the minimal (also called feedback) polynomial of s divides

where Qn(x) is the cyclotomic polynomial. Since the minimal poly- nomial of s cannot be (x2-1), the argument used in [2] can be used to prove the above proposition.

Thus, with a special Blum integer the linear span of the Blum- Blum-Shub sequence can be controlled by controlling the orders of 2 modulo 07-3)/4 and (q-3)/4.

Another cryptographically interesting property of the Blum- Blum-Shub generator is its unpredictability under the hypothesis that any efficient procedure for guessing the quadratic residuacity of a given m modulo N will be incorrect for a positive fraction of the inputs [2]. Some randomness property of the Blum-Blum-Shub sequences was proved by Cusick [3].

It is well-known that the linear span of the keystream genera- tors for additive synchronous stream ciphers must be controlled. Our result here shows that the Blum-Blum-Shub generator can be used for additive stream ciphering when the two primes are prop- erly chosen. It is slow for multimedia applications, but certainly reasonable for military and diplomatic communications.

The Blum-Blum-Shub generator has a number of interesting pseudorandom properties. The author shows how to control the linear span of the output sequences of this generator by a proper choice of the two primes.

Main contribution: Pseudorandom number generators have appli- cations in simulation, software testing, global positioning systems, ranging systems, code-division multiple-access systems, radar sys- tems, spread-spectrum communication systems, and stream ciphers.

One of the cryptographically interesting number-theoretic gen- erators is the Blum-Blum-Shub generator [l]. This generator can be described as follows. Let p = 3 (mod 4) and q = 3 (mod 4) be primes. Such an integer N = pq is called a Blum integer. Let x, be an integer which is a quadratic residue modulo N, i.e. x, = u2 (mod N) for some integer u and gcd(x,, N) = 1. The Blum-Blum-Shub generator is then defined by

b, = x, mod 2

where

(1) z - - 2 ? - mod N i = 1 ,2 , ... Here x mod N is defined to be the least non-negative integer con- gruent to x modulo N.

Blum, Blum and Shub [I] proved that the least period of the sequence x- defined by eqn. 1 divides h(h(N)) if x, is a quadratic residue modulo a Blum integer N, where h is the lambda function. Thus, the least period of the binary sequence b- must divide h(h(N)). If the Blum integer N = pq is chosen such that

where p , p l , p2 , q, q,, q2 are all odd primes, then

Such primes p and q are called special [l]. If p and q are special and N = pq, then the least period of b- must be one of p2, q2, 2p,, 2qz, 2p,q2, p2q2. Thus, it must be no less than min@,, q2}. With

0 IEE 1997 Electronics Letters Online No: 19970440

24 February 1997

C. Ding (Turlcu Centre for Computer Science, Datacity, Lemminkaisenkatu 14 A , FIN-20520 Turku, Finland)

References

1 BLUM, L., BLUM, M., and SHUB, M.: ‘A simple unpredictable pseudorandom number generator’, SIAM J. Comput., 1986, 15, pp. 364-3 8 3 DING, c : ‘Binary cyclotomic generators’. Lecture notes in computer science 1008, (Springer-Verlag, 1995), PP. 29-60 CUSICK, T w.: ‘Properties of the X2 mod N generator’, ZEEE Trans. Iuf Theory, 1995, 41, pp. 1155-1 159

2

3

Security of a one-time signature

Sung-Ming Yen

Indexing term: Security of data

Recently, Wu and Sung reported a one-time digital signature based on any one-way function in their article about password authentication. Owing to its general construction and potential applications, including the development of a one-time password scheme, in-depth security analysis is considered in the Letter. It is shown to suffer from a signature forgery problem.

Introduction: Early works about the one-time digital signature have been reported in [l, 21 and are further studied in [3 - 51. Although a signature upon these constructions can only be gener- ated once or a small predetermined number of times while using the setting up signing-key and the related verification-key, some