A class of zero-correlation zone (ZCZ) sequences constructed by the recursive procedure from a perfect sequence and a unitary matrix was proposed by Torii, Nakamura, and Suehiro [1] . In the reference [1] , three parameters, s.t., the sequence length, the family size and the length of the ZCZ, were evaluated for a general estimate of the performance of the ZCZ sequences. In this letter, we give more detailed distributions of that correlation values are zero on their ZCZ sequence sets.

Recently two interesting conjectures on the linear complexity of binary complementary sequences of length 2nN0 were given by Karkkainen and Leppanen when those sequences are considered as periodic sequences with period 2nN0, where those sequences are constructed by successive concatenations or successive interleavings from a pair of kernel complementary sequences of length N0. Their conjectures were derived from numerical examples and suggest that those sequences have very large linear complexities. In this paper we give the exact formula of characteristic polynomials for those complementary sequences and show that their conjectures are true.

In ordinary digital signature schemes, anyone can verify signatures with signer's public key. However it is not necessary for anyone to be convinced a justification of signer's dishonorable message such as a bill. It is enough for a receiver only to convince outsiders of signature's justification if the signer does not execute a contract. On the other hand there exist messages such as official documents which will be first treated as limited verifier signatures but after a few years as ordinary digital signatures. We will propose a limited verifier signature scheme based on Horster-Michels-Petersen's authenticated encryption schemes, and show that our limited verifier signature scheme is more efficient than Chaum-Antwerpen undeniable signature schemes in a certain situation. And we will propose a convertible limited verifier signature scheme based on our limited verifier signature scheme, and show that our convertible limited verifier signature scheme is more efficient than Boyar-Chaum-Damg rd-Pedersen convertible undeniable signature schemes in a certain situation.

In this paper, we will show that some families of periodic sequences over Z4 and Z8 with period multiple of 2r-1 generated by r-th degree basic primitive polynomials assorted by the root of each polynomial, and give the exact distribution of sequences for each family. We also point out such an instability as an extreme increase of their linear complexities for the periodic sequences by one-symbol substitution, i.e., from the minimum value to the maximum value, for all the substitutions except one.

An algebraic group is an essential mathematical structure for current communication systems and information security technologies. Further, as a widely used technology underlying such systems, pseudorandom number generators have become an indispensable part of their construction. This paper focuses on a theoretical analysis for a series of pseudorandom sequences generated by a trace function and the Legendre symbol over an odd characteristic field. As a consequence, the authors give a theoretical proof that ensures a set of subsequences forms a group with a specific binary operation.

Firstly we show a usuful property of the fast algorithm for computing linear complexities of p-ary periodic sequences with period pn (p: a prime). Secondly the property is successfully applied to obtain the value distribution of the linear complexity for p-ary periodic sequences with period pn.

Because of its simple structure, many reports on the logistic map have been presented. To implement this map on computers, finite precision is usually used, and therefore rounding is required. There are five major methods to implement rounding, but, to date, no study of rounding applied to the logistic map has been reported. In the present paper, we present experimental results showing that the properties of sequences generated by the logistic map are heavily dependent on the rounding method used and give a theoretical analysis of each method. Then, we describe why using the map with a floor function for rounding generates long aperiodic subsequences.

From a sequence {ai}i0 over GF(p) with period pn-1 we can obtain another periodic sequence {i}i0 with period pn-2 by deleting one symbol at the end of each period. We will give the bounds (upper bound and lower bound) of linear complexity of {i}i0 as a typical example of instability of linear complexity. Derivation of the bounds are performed by using the relation of characteristic polynomials between {ai}i0 and {ai(j)}i0={ai+j}i0, jGF(p){0}. For a binary m-sequence {ai}i0 with period 2n-1, n-1 a prime, we will give the explicit formula for the characteristic polynomial of {i}i0.

The maximum order complexity (MOC) of a sequence is a very natural generalization of the well-known linear complexity (LC) by allowing nonlinear feedback functions for the feedback shift register which generates a given sequence. It is expected that MOC is effective to reduce such an instability of LC as an extreme increase caused by the minimum changes of a periodic sequence, i. e. , one-symbol substitution, one-symbol insertion or one-symbol deletion per each period. In this paper we will give the bounds (lower and upper bounds) of MOC for the minimum changes of an m-sequence over GF(q) with period qn-1, which shows that MOC is much more natural than LC as a measure for the randomness of sequences in this case.

From a GF(q) sequence {ai}i0 with period qn - 1 we can obtain new periodic sequences {ai}i0 with period qn by inserting one symbol b GF(q) at the end of each period. Let b0 = Σqn-2 i=0 ai. It Is first shown that the linear complexity of {ai}i0, denoted as LC({ai}) satisfies LC({ai}) = qn if b -b0 and LC({ai}) qn - 1 if b = -b0 Most of known sequences are shown to satisfy the zero sum property, i.e., b0 = 0. For such sequences satisfying b0 = 0 it is shown that qn - LC({ai}) LC({ai}) qn - 1 if b = 0.

This paper proposes a new multi-value sequence generated by utilizing primitive element, trace, and power residue symbol over odd characteristic finite field. In detail, let p and k be an odd prime number as the characteristic and a prime factor of p-1, respectively. Our proposal generates k-value sequence T={ti | ti=fk(Tr(ωi)+A)}, where ω is a primitive element in the extension field $F{p}{m}$, Tr(⋅) is the trace function that maps $F{p}{m} ightarrow {p}$, A is a non-zero scalar in the prime field ${p}$, and fk(⋅) is a certain mapping function based on k-th power residue symbol. Thus, the proposed sequence has four parameters as p, m, k, and A. Then, this paper theoretically shows its period, autocorrelation, and cross-correlation. In addition, this paper discusses its linear complexity based on experimental results. Then, these features of the proposed sequence are observed with some examples.

Let p be an odd characteristic and m be the degree of a primitive polynomial f(x) over the prime field Fp. Let ω be its zero, that is a primitive element in F*pm, the sequence S={si}, si=Tr(ωi) for i=0,1,2,… becomes a non-binary maximum length sequence, where Tr(·) is the trace function over Fp. On this fact, this paper proposes to binarize the sequence by using Legendre symbol. It will be a class of geometric sequences but its properties such as the period, autocorrelation, and linear complexity have not been discussed. Then, this paper shows that the generated binary sequence (geometric sequence by Legendre symbol) has the period n=2(pm-1)/(p-1) and a typical periodic autocorrelation. Moreover, it is experimentally observed that its linear complexity becomes the maximum, that is the period n. Among such experimental observations, especially in the case of m=2, it is shown that the maximum linear complexity is theoretically proven. After that, this paper also demonstrates these properties with a small example.

This paper proposes a new approach for generating pseudo random multi-valued (including binary-valued) sequences. The approach uses a primitive polynomial over an odd characteristic prime field ${p}$, where p is an odd prime number. Then, for the maximum length sequence of vectors generated by the primitive polynomial, the trace function is used for mapping these vectors to scalars as elements in the prime field. Power residue symbol (Legendre symbol in binary case) is applied to translate the scalars to k-value scalars, where k is a prime factor of p-1. Finally, a pseudo random k-value sequence is obtained. Some important properties of the resulting multi-valued sequences are shown, such as their period, autocorrelation, and linear complexity together with their proofs and small examples.

The value distribution of the partial autocorrelation of periodic sequences is important for the evaluation of the sequence performances when sequences of long period are used. But it is difficult to find the exact value distribution of the autocorrelation in general. Therefore we derived some properties of the partial autocorrelation for binary m-sequences which may be used to find the exact value distribution.

A pseudorandom number generator is widely used in cryptography. A cryptographic pseudorandom number generator is required to generate pseudorandom numbers which have good statistical properties as well as unpredictability. An m-sequence is a linear feedback shift register sequence with maximal period over a finite field. M-sequences have good statistical properties, however we must nonlinearize m-sequences for cryptographic purposes. A geometric sequence is a binary sequence given by applying a nonlinear feedforward function to an m-sequence. Nogami, Tada and Uehara proposed a geometric sequence whose nonlinear feedforward function is given by the Legendre symbol. They showed the geometric sequences have good properties for the period, periodic autocorrelation and linear complexity. However, the geometric sequences do not have the balance property. In this paper, we introduce geometric sequences of two types and show some properties of interleaved sequences of the geometric sequences of two types. These interleaved sequences have the balance property and double the period of the geometric sequences by the interleaved structure. Moreover, we show correlation properties and linear complexity of the interleaved sequences. A key of our observation is that the second type geometric sequence is the complement of the left shift of the first type geometric sequence by half-period positions.

The authors have proposed a multi-value sequence called an NTU sequence which is generated by a trace function and the Legendre symbol over a finite field. Most of the properties for NTU sequence such as period, linear complexity, autocorrelation, and cross-correlation have been theoretically shown in our previous work. However, the distribution of digit patterns, which is one of the most important features for security applications, has not been shown yet. In this paper, the distribution has been formulated with a theoretic proof by focusing on the number of 0's contained in the digit pattern.

Pseudorandom number generators are required to generate pseudorandom numbers which have good statistical properties as well as unpredictability in cryptography. An m-sequence is a linear feedback shift register sequence with maximal period over a finite field. M-sequences have good statistical properties, however we must nonlinearize m-sequences for cryptographic purposes. A geometric sequence is a sequence given by applying a nonlinear feedforward function to an m-sequence. Nogami, Tada and Uehara proposed a geometric sequence whose nonlinear feedforward function is given by the Legendre symbol, and showed the period, periodic autocorrelation and linear complexity of the sequence. Furthermore, Nogami et al. proposed a generalization of the sequence, and showed the period and periodic autocorrelation. In this paper, we first investigate linear complexity of the geometric sequences. In the case that the Chan-Games formula which describes linear complexity of geometric sequences does not hold, we show the new formula by considering the sequence of complement numbers, Hasse derivative and cyclotomic classes. Under some conditions, we can ensure that the geometric sequences have a large linear complexity from the results on linear complexity of Sidel'nikov sequences. The geometric sequences have a long period and large linear complexity under some conditions, however they do not have the balance property. In order to construct sequences that have the balance property, we propose interleaved sequences of the geometric sequence and its complement. Furthermore, we show the periodic autocorrelation and linear complexity of the proposed sequences. The proposed sequences have the balance property, and have a large linear complexity if the geometric sequences have a large one.

The logistic map is a chaotic mapping. Although several studies have examined logistic maps over real domains with infinite/finite precisions, there has been little analysis of the logistic map over integers. Focusing on differences between the logistic map over the real domain with infinite precision and the logistic map over integers with finite precision, we herein show the characteristic properties of the logistic map over integers and discuss the sequences generated by the map.