The set of all even subgraphs of a connected graph G on p vertices with q edges forms a binary linear code C=C/sub E/(G) with parameters [q,q-p+1,g], where g is the girth of G. Such codes were studied systematically by Bredeson and Hakimi (1967) and Hakimi and Bredeson (1968) who were concerned with the problems of augmenting C to a larger [q,k,g]-code and of efficiently decoding such augmented graphical codes. We give a new approach to these problems by requiring the augmented codes to be graphical. On one hand, we present two construction methods which turn out to contain the methods proposed by Hakimi and Bredeson as special cases. As we show, this not only gives a better understanding of their construction, it also results in augmenting codes of larger dimension. We look at the case of 1-error-correcting graphical codes in some detail. In particular, we show how to obtain the extended Hamming codes as "purely" graphical codes by our approach. On the other hand, we follow a suggestion of Ntafos and Hakimi (1981) and use techniques from combinatorial optimization to give decoding procedures for graphical codes which turn out to be considerably more efficient than the approach via majority logic decoding proposed by Bredeson and Hakimi. We also consider the decoding problem for the even graphical code based on the complete graph K/sub 2n/ in more detail: we discuss an efficient hardware implementation of an encoding/decoding scheme for these codes and show that things may be arranged in such a way that one can also correct all adjacent double errors. Finally, we discuss nonlinear graphical codes.

We present a new cryptosystem based on elliptic curves over the ring Z/sub n/, where n=pq, in which the message is held in the exponent and not the group element. The security of this system is based on the difficulty of factoring n. A digital signature scheme and ID-based key exchange system are also given.

The authors describe a VLSI Galois field processor and how it can be applied to the implementation of elliptic curve groups. They demonstrate the feasibility of constructing very fast, and very secure, public key systems with a relatively simple device, and the possibility of putting such a system on a smart card. The registers necessary to implement the elliptic curve system will require less than 1 mm/sup 2/ (or less than 4%) of the area available on the card.>

Elliptic curve cryptosystems have the potential to provide relatively small block size, high-security public key schemes that can be efficiently implemented. As with other known public key schemes, such as RSA and discrete exponentiation in a finite field, some care must be exercised when selecting the parameters involved, in this case the elliptic curve and the underlying field. Specific classes of curves that give little or no advantage over previously known schemes are discussed. The main result of the paper is to demonstrate the reduction of the elliptic curve logarithm problem to the logarithm problem in the multiplicative group of an extension of the underlying finite field. For the class of supersingular elliptic curves, the reduction takes probabilistic polynomial time, thus providing a probabilistic subexponential time algorithm for the former problem.>

This paper presents a generalization of Moenck’s root finding algorithm over $GF(q)$, for q a prime or prime power. The generalized algorithm, like its predecessor, is deterministic, given a primitive element $\omega $ for $GF(q)$. If $q - 1$ is b-smooth, where $b = (\log q)^{O(1)} $, then the algorithm runs in polynomial time. An analogue of this generalization which applies to extension fields $GF(q^m )$ is also considered. The analogue is a deterministic algorithm based on the recently introduced affine method for root finding in $GF(q^m )$, where $m > 1$; it is, however, less efficient that the affine method itself.

This paper is concerned with pair-splitting sets in $AG_k ( m,q )$, the design obtained from the points and k-flats in $AG (m,q)$. A pair-splitting set is a set of parallel classes $\{ R_1 ,R_2 , \cdots ,R_s \}$ such that there is no pair of distinct points $a,b$ such that $a,b$ are contained in a common k-flat of each of the s parallel classes. It is easy to prove that a lower bound on s is $\lceil m/( m - k ) \rceil $. The main result of this paper is to prove that this lower bound is always achievable for any choice of $m,q$, and k, where $0\leqq k\leqq m - 1$. The concept of pair-splitting sets arises naturally out of the problem of finding roots in $GF( q^m )$ of a polynomial over $GF ( q^m )$. The connection between the two concepts is briefly discussed.

Previously, no general-purpose algorithm was known for the elliptic curve logarithm problem that ran in better than exponential time.In this paper we demonstrate the reduction of the elliptic curve logarithm problem to the logarithm problem in the multiplicative group of an extension of the underlying hit e field.For the class of supersingular elliptic curves, the reduction takes probabilistic polynomial time, thus providing a probabilistic subexponential time algorithm for the former problem.The implications of our results to public key cryptography are discussed. , the subgroup of 2? generated by P, and the subgroup of nth roots of unity in Fqk, where n denot es the order of P. The isomorphism is given by the Weil pairing.Since the index-calculus methods for computing logarithms in a finite field have running times that are subexponential, the reduction is useful for the purpose of computing elliptic curve logarithms provided that k is small.This is indeed the case for special classes of elliptic curves, including the

In this paper we examine the development of a high-speed implementation of a system to perform exponentiation in fields of the form GF(2 n ). For sufficiently large n, this device has applications in public-key cryptography. The selection of representation and observations on the structure of multiplication have led to the development of an architecture which is of low complexity and high speed. A VLSI implementation has being fabricated with measured throughput for exponentiation for cryptographic purposes of approximately 300 kilobits per second.

The problem of finding roots in F of polynomials in F(x) for F=GF(q/sup m/), where q is a prime or prime power and m is a positive integer greater than 1 is considered. The problem is analyzed by making use of the finite affine geometry AG(m,q). A new method is proposed for finding roots of polynomials over finite extension fields. It is more efficient than previous algorithms when the degree of the polynomial whose roots are to be found is less than dimension m of the extension field. Implementation of the algorithm can be enhanced in cases in which optimal normal bases for the coefficient field are available.>

We investigate the combinatorial properties of threshold schemes. Informally, a $( t,w )$-threshold scheme is a way of distributing partial information (shadows) to w participants, so that any t of them can easily calculate a key, but no subset of fewer than t participants can determine the key. Our interest is in perfect threshold schemes: no subset of fewer than t participants can determine any partial information regarding the key. We give a combinatorial characterization of a certain type of perfect threshold scheme. We also investigate the maximum number of keys that a perfect $( t,w )$-threshold scheme can incorporate, as a function of $t,w$, and the total number of possible shadows, $v $. This maximum can be attained when there is a Steiner system $S( t,w,v )$ that can be partitioned into Steiner systems $S ( t - 1,w,v )$. Using known constructions for such Steiner systems, we present two new classes of perfect threshold schemes, and discuss their implementation.