Introduction

Cryptology is a very active and expanding field tha t brings forward new developments in cryptography and crypt analysis every year. A comprehensive survey and up-to-date report (as of 1988) on the advances in designing ciphers and cryptographic schemes and on recent successes in breaking cryptosystems has been published in [18] as a collection of important papers on cryptology. This special section of the Proceedings of the IEEE, from May 1988, may serve th e interested reader as a first introduction to a variety of topics in contemporary cryptology, ranging from conventional cyptosystems and the Dat a Encryption Standard, over public-key cryptography and recent advances in crypt analysis, to a survey of information authentification. Brassard [1] gives a brief survey of cryptography, which is kept at the nontechnical level. Mathematical concepts in cryptography are emphasised in the books by van Tilborg [19], Patterson [13] and Lidl and Niederreiter [6]. For those interested in details of the design and analysis of ciphers, we refer to the proceedings volumes of the annual meetings EUROCRYPT and CRYPTO, see for example [3] and [14].

Introduction

Every finite field has cardinality pn for some prime number p and some positive integer n. Conversely, if p is a prime number and n a positive integer, then there exists a field of cardinality pn, and any two fields of cardinality pn are isomorphic. These results are due to E. H. Moore (1893) [15]. In this paper, we discuss the complexity aspects of two algorithmic problems that are suggested by this theorem, and of two related problems.

Constructing finite fields. We say that a finite field is explicitly given if, for some basis of the field over its prime field, we know the product of any two basis elements, expressed in the same basis. Let, more precisely, p be a prime number and n a positive integer.

Introduction

Public key cryptosystems based on the knapsack trapdoor have been considered insecure since a polynomial time algorithm was found for breaking instances of the code. In particular, the Lenstra, Lenstra and Lovasz algorithm for producing short basis vectors of a lattice has proved useful in attacking the diophantine approximation problems which arise in attempts to break the codes. O'Connor [3] has proposed an interesting variant of the knapsack cryptosystem. Unfortunately, as will be shown, the diophantine equations associated with the system fall to the short basis vector attack. All instances of the proposed system that have been generated to test the system have been broken. It seems that there are many sets of parameters that will generate any instance of the code, and it is too easy to find such a set.

Introduction

The purpose of this paper is to give an overview of the main recent advances concerning Gauss's class number one problem for real quadratic fields, to describe the connections with prime-producing polynomials, continued fraction theory and the theory of reduced ideals, and to make the comparison with the development of the solution of Gauss's class number one problem for complex quadratic fields. This includes a description of the search for a real quadratic field analogue of the well-known Rabinowitsch result for complex quadratic fields.

Furthermore, we describe a criterion for class number 2 (in terms of continued fractions and reduced ideals) for general real quadratic fields. We also provide (for a specific class of real quadratric fields called Richaud-Degert types) class number 2 criteria in terms of prime-producing quadratic polynomials. This is the real quadratic field analogue of Hendy's result [9] for complex quadratic fields. Other related results including a solution of a problem of L. Bernstein [2], [3] are delineated as well.

Reed-Solomon error correction codes are powerful codes which allow efficient correction of multiple burst errors. The (n, k) Reed-Solomon code takes strings of n symbols, each containing k information symbols and n – k check symbols and can correct any occurrence of at most ½(n – k) incorrectly received symbols ([4]). The Reed-Solomon code is usually implemented via computation in a finite field of characteristic 2. However, this requires special circuits for encoding and decoding which have only recently become economic.

There is an alternative ‘spectral’ interpretation which uses ordinary complex arithmetic. This has the advantage that conventional floating point devices can be used for encoding and decoding. Its compensating disadvantage is that the arithmetic is no longer exact. For the purposes of this example, let us assume that we would like to code k = ½n message symbols and that we wish to correct up to ¼n incorrectly received symbols. First, pad the ½n length message sequence with a ‘prefix’ of ½n zero symbols. We view the resulting sequence as a sequence of spectral magnitudes. Thus it has a characteristic ‘high-pass’ spectrum, that is all low frequency spectral magnitudes are zero. Next, take the inverse fourier transform of the high-pass spectrum and transmit the resulting time domain sequence. The characteristic high-pass spectrum, that is zero symbols in the first ½n spectral bands, is spread over the entire n time domain components.

Introduction

Stream ciphers assimilate the one time pad, the only provably perfect secure system. However with the replacement of the random generator by a pseudo-random (PR) one, the perfect security of the system vanishes. It is easy to see that the assessment of the security of these systems is directly related to the properties of the PR generator. There are some necessary criteria which must be satisfied by the PR generator of a secure stream cipher. It is recognised that these generators should satisfy Golomb's criteria and have high linear complexity [1], [3].