We developed and evaluated several cryptographic system libraries for Palm OS(R) which include stream and block ciphers, hash functions and multiple-precision integer arithmetic operations. We noted that the encryption speed of SSC2 outperforms both ARC4 (Alleged RC4) and SEAL 3.0 if the plaintext is small. On the other hand, SEAL 3.0 almost doubles the speed of SSC2 when the plaintext is very large. We also observed that the optimized Rijndael with 8KB of lookup tables is 4 times faster than DES. In addition, our results show that implementing the cryptographic algorithms as system libraries does not degrade their performance significantly. Instead, they provide great flexibility and code management to the algorithms. Furthermore, the test results presented provide a basis for performance estimation of cryptosystems implemented on the PalmPilot/sup TM/.

Pseudorandom binary sequences with high linear complexity and low correlation function values are sought in many applications of modern communication systems. A new family of pseudorandom binary sequences, cascaded GMW sequences, is constructed. These sequences are shown to share many desirable correlation properties with the GMW sequences of B. Gordon, W.A. Mills, and L.R. Welch (1962)-for example, high-shifted autocorrelation values and, in many cases, three-valued cross-correlation values with m-sequences. It is shown, moreover, that in many cases the linear complexities of cascaded GMW sequences are far greater than those of GMW sequences.>

A class of periodic binary sequences that are obtained from q-ary m-sequences is defined, and a general method to determine their linear spans (the length of the shortest linear recursion over the Galois field GF(2) satisfied by the sequence) is described. The results imply that the binary sequences under consideration have linear spans that are comparable with their periods, which can be made very long. One application of the results shows that the projective and affine hyperplane sequences of odd order both have full linear span. Another application involves the parity sequence of order n, which has period p/sup m/-1, where p is an odd prime. The linear span of a parity sequence of order n is determined in terms of the linear span of a parity sequence of order 1, and this leads to an interesting open problem involving primes.>

The quadratic span of a periodic binary sequence is defined to be the length of the shortest quadratic feedback shift register (FSR) that generates it. An algorithm for computing the quadratic span of a binary sequence is described. The required increase in quadratic span is determined for the special case of when a discrepancy occurs in a linear FSR that generates an initial portion of a sequence. The quadratic spans of binary DeBruijn sequences are investigated. An upper bound for the quadratic span of a DeBruijn sequence of span n is given; this bound is attained by the class of DeBruijn sequences obtained from m-sequences. It is easy to see that a lower bound is n+1, but a lower bound of n+2 is conjectured. The distributions of quadratic spans of DeBruijn sequences of span 3, 4, 5 and 6 are presented.>

Sequences generated by arbitrary feedback registers (not necessarily feedback shift registers) with arbitrary feedforward functions are studied. The definition of linear complexity of a sequence is generalized to the notions of strong and weak linear complexity of feedback registers. A technique for finding upper bounds for the strong linear complexities of such registers is developed. This technique is applied to several classes of registers. It is shown that a feedback shift register in which the feedback function is of the form x/sub 1/+h(x/sub 2/, . . . , x/sub n/) can generate long periodic sequences with high linear complexities only if its linear and quadratic terms have certain specific forms.>

An algorithm to minimize decision trees of Boolean functions with multiple-valued inputs is presented. The recursive algorithm is used to obtain a complement of a sum-of-products expression for a binary function with multiple-valued inputs. In the case where each input is p-valued, the algorithm produces at most pn−l products for n-variable functions, whereas Sasao's algorithm produces pn/2 products. This upper bound on the number of products is the best possible.

The complexity of a periodic sequence(s)is defined to be the least number of stages in a linear feedback shift register that generates(s).

The technique of error-trapping decoding for algebraic codes is studied in combinatorial terms of covering systems. Letn, k, andtbe positive integers such thatn \geq k \geq t > 0. An(n, k,t)-covering system is a pair(X, \beta), whereXis a set of sizenand\betais a collection of subsets ofX, each of sizek, such that for allT \subseteq Xof sizet, there exists at least oneB \in \betawithT\subseteq B. Letb(n, k, t)denote the smallest size of\beta, such that(X, \beta)is an(n, k, t)-covering system. It is shown that the complexity of an error-trapping decoding technique is bounded byb(n, k, t)from below. Two new methods for constructing small(n, k, t)-covering systems, the algorithmic method and the difference family method, are given.