The current stage of development of information technologies is characterized by the active introduction of the functions of many-valued logic. In particular, many-valued logic functions are used in cryptography to build highquality cryptographic primitives with a high level of nonlinearity. This circumstance determines the need for more detailed research of the nonlinearity of the complete codes of functions of many-valued logic. Because of the possibility of representing constructions of almost all modern ciphers by 4-functions, they occupy a special place among other q values in the research of the level of nonlinearity. This paper presents a universal method for calculating the possible absolute values of the Vilenkin-Chrestenson transform coefficients of many-valued logic functions. This method is applied to 4-functions of length N = 4 and N = 16. As a result, 5 spectral classes of vectors of length N = 4, and 36 spectral classes of vectors of length N = 16 were discovered, each of which has a unique elementary structure, and, accordingly, the certain value of nonlinearity. Because of the dependence of such a fundamental concept of MC-CDMA technology as the Peak-to-Average Power Ratio of the applied signals and their spectral properties, the results obtained can also be used to calculate the maximum cardinality values of constant amplitude codes constructed based on many-valued logic functions.
Introduction and Statement of the Problem The current stage in the development of cryptography is characterized by the great attention of researchers to the methods of many-valued logic [1]. Methods of many-valued logic are used both to increase the security of quantum cryptographic algorithms [2, 3] as well as to create new cryptographic primitives [4, 5], and traditional cryptographic algorithms [6], characterized by increased security [7]. There are also methods to estimate the cryptographic quality of existing cryptographic algorithms represented by the functions of many-valued logic. To estimate the cryptographic quality of manyvalued logic functions, a set of criteria [2] has been introduced, among which the most important is the criterion of nonlinearity.
Copyright © 2020 for this paper by its authors.
Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0) This circumstance makes it especially important to research the nonlinear properties of many-valued logic functions, which, due to the interconnection between nonlinearity and the spectral properties of many-valued logic functions, is closely related to the issue of spectral classification of complete quaternary code.
On the other hand, there is a direct relationship between the spectral properties of sequences and such a parameter as the Peak-to-Average Power Ratio (PAPR) of their spectrum, which plays a significant role in the case of their application in MC-CDMA technology [8]. That is, the problem of spectral classification of the complete code of quaternary sequences is also equivalent to the problem of determining the maximum cardinalities of actively used quaternary C-codes [9], which have a given level of the PAPR of the Vilenkin-Chrestenson spectrum.
At the moment, in the literature the spectral classification of the complete codes of ternary sequences of lengths N 3 and N 9 is already performed [10], nevertheless, the spectral properties of quaternary sequences remain unknown.
The purpose of this paper is to develop a method for the spectral classification of
quaternary sequences, as well as to carry out the spectral classification of the full set of
quaternary sequences of lengths N 4 and N 16 .
(
For each sequence of 4-logic, we define the vector of the Vilenkin-Chrestenson transform [11] as the product of some sequence A of 4-valued logic by the transposed Vilenkin-Chrestenson matrix 2
Let’s introduce the basic definitions. As an alphabet of sequences of 4-valued logic, it is convenient to consider the set of fourth roots of unity
j 2π k zk e 4 , k {0,1, 2, 3} , then the alphabet of the considered in this paper vectors will consist of the following values
f f V T , where the Vilenkin-Chrestenson matrix is defined by the following recurrent construction [4]
V4k1 VVVV4444kkkk VVV444Vkkk 4k123 VV44VVkk44kk 22 VVV444Vkkk 4k132 , V4 zzzz0000 zzzz1023 zzzz0022 zzzz1023 .
In expression (
The quaternary sequence of length N 4k can be considered as the truth table of the many-valued logic function of k variables, which are used to estimate the quality of cryptographic algorithms as well as for the construction of perspective cryptographic primitives [4].
Today there is a known method for estimating the nonlinearity of many-valued logic functions [12] using the coefficients of the Vilenkin-Chrestenson transform qk max f , q 2; N f 2k 1 1 2
max Wf , q 2, where Wf are the Walsh-Hadamard transform coefficients which are used instead of Vilenkin-Chrestenson transform coefficients in the case of Boolean functions [13].
The formula (
The formula (
Note also that from the spectral properties of many-valued logic sequences follows such an important characteristic as the PAPR, which is decisive for their use as C-codes in MC-CDMA technology [7] κ Pmax 1 max f 2
Pср N t
(
Pav is the average power of the signal f , N is the length of the sequence.
So, such practically valuable properties of sequences of many-valued logic as
nonlinearity and PAPR are the special cases of their spectral properties. This fact makes
the task of spectral classification of the sequences of many-valued logic very important.
(
j 2π k a4, ai zk e 4 , k {0,1, 2,3} .
For each such quaternary vector, the Vilenkin-Chrestenson transform can be found by multiplying it by the matrix complex conjugation of the Vilenkin-Chrestenson matrix S A V4 . In this case, in general form, the vector of the Vilenkin-Chrestenson transform coefficients can be represented as follows
S s1 s2
s3 , si .
Each vector A uniquely corresponds to its vector S . The converse is not true, i. e. not for every vector S , si , there is such corresponding vector with such coordinates ai {1, z1, z2 , z3} that equality S A V4 is valid.
In the general case, the problem of finding nonlinear sequences is the problem of finding sequences with given spectral properties, which implies research of the admissible structures of vectors S , as well as values of their elements for which exists the corresponding vectors in the time domain. This problem is a problem of spectral classification of quaternary vectors of length N.
We will perform the spectral classification by the approach [14], i.e. based on the definition of sets of absolute values of spectral vectors.
Let us find out what values the elements si can take in the example of the first
Vilenkin-Chrestenson transform coefficient s1 . This coefficient is the result of the product of
the sequence A in the time domain by the first column of the Vilenkin-Chrestenson
matrix. The elements of the sequence A belong to the alphabet z0 , z1, z2 , z3 , which
can be represented in the algebraic form of representing a complex number (
Let us denote by K0 , K1, K2 , K3 the number of elements z0 , z1, z2 and z3 in the sequence A , respectively. Then the coefficient s1 will take the values 3
Spectral Classification of Quaternary Sequences of Length
N = 4
Each quaternary sequence of length N 4 can be represented in the following
generalized form
where
dition (
(
Proposition 1. The set of values (
Let us express the value of the first Vilenkin-Chrestenson transform coefficient in terms of the elements of the original sequence Similarly, consider the ith Vilenkin-Chrestenson transform coefficient s1 [a1
a2 [a1 a2 a3 a3 a4 ][z0 z0 z0
z0 ]T a4 ]1 1 1 1T a1 a2 a3 a4 , ai {z0 , z1, z2 , z3}. si [a1 a2 a3 a4 ][v0 v1 v2
v3 ]T e jβ1 e jβ2 e jβ3 e jβ4 e jγ1 e jγ2 e jγ3 e jγ4 T e j(β1 γ1) e j(β2 γ2 ) e j(β3 γ3 ) e j(β4 γ4 ) .
Since βi , γi {z0 , z1, z2 , z4} for each si , there is a sequence A [a1 a a a4 ], the 2 3 Vilenkin-Chrestenson transform of which has a coefficient s1 equal to the given si .
Due to Parseval's equality, the minimum value of the Vilenkin-Chrestenson
transk 1
form coefficient cannot be lower than q 2 42 2 . So, the values of the
VilenkinChrestenson transform coefficients of quaternary sequences si 0 and si 2
cannot be the maximum absolute values in the Vilenkin-Chrestenson transform vector.
Thus, the set of possible values of nonlinearity by (
N f 4 {4, 10, 8, 2} {0, 0.8377, 1.1716, 2} . We can highlight the method for calculating the possible absolute values of the Vilenkin-Chrestenson transform coefficients, and, accordingly, the possible values of nonlinearity and PAPR, in the form of specific steps:
Step 1. Present in general form the absolute value of the first Vilenkin-Chrestenson transform coefficient s1 in terms of the numbers K0 , K1,..., Kq1 of elements of the many-valued logic sequence alphabet.
Step 2. Find possible values K0 , K1,..., Kq1 that satisfy the condition K0 K ... Kq1 N , 1 K0 , K1,..., Kq1 {0,1,.., N}.
Step 3. Substitute the possible values K0 , K1,..., Kq1 into the expression obtained in Step 1 for the absolute value of the first Vilenkin-Chrestenson transform coefficient s1 in terms of the numbers K0 , K1,..., Kq1 of the many-valued logic sequence alphabet. In this case, because of Statement 1, the resulting set of values will constitute the full set of possible values of all the coefficients of the Vilenkin-Chrestenson transform.
Step 4. Calculate the possible values of nonlinearity and PAPR by formulas (
The results of calculations showed that for vectors of length N 4 there are five
spectral classes of vectors (Table 1), for each of which the cardinality of the class, the
value of nonlinearity and PAPR as well as the representative sequence are provided.
(
{4(
0 Analysis of the data presented in Table 1 shows that the complete code of quaternary sequences of length N 4 can be classified into five spectral classes, among which there is a class of affine functions [15] of cardinality J1 16 , as well as the class of bent-functions [16] of cardinality J5 32 .
In Fig. 1, a histogram of the distribution of nonlinearity of quaternary sequences of length N 4 is shown. It should be noted that sequence length N 16 is very important in modern cryptographic applications. So, the problem of spectral classification of the complete set of quaternary sequences of length N 16 is of special interest in the terms of their usage in cryptography.
Expression (
Based on the set of suitable K0 , K1, K2 , K3 sets, and taking into account Statement 1, as well as the formula for the absolute value of a complex number, we can write down the set of possible absolute values of the Vilenkin-Chrestenson transform coefficients of quaternary sequences of length N 16 si {0, 2, 2, 8, 10, 4, 18, 20, 26, 32, 34, 6, 40, 50, 52, 58,8, 68, 72, 74, 80, 82, 90, 98,10, 104, 106, 116, 122, 128, 130, 136,12, 146, 148, 160, 170, 178,14, 200, 226,16}.
In the case of quaternary sequences of length N 16 , due to Parseval's equality, the
minimum value of the coefficient of the Vilenkin-Chrestenson transform cannot be less
(17)
(18)
2
than qk 2 42 4 . The values of the Vilenkin-Chrestenson transform coefficients
si 0, 2, 2, 8, 10 of quaternary sequences cannot be maximum in the
VilenkinChrestenson transform to vector. The full class of possible values of the nonlinearity of
quaternary sequences of length N 16 by the formula (
N f {252, 251.76, 251.53, 250.90, 250.34, 250.17, 250, 249.68, 248.93, 248.79, 248.38, 248, 247.75, 247.51, 224475..4800,, 224475..0760,, 224465..9243,, 224464..5915,, 224464..1609,, 224464..0600,, (19) 244.34, 244.00, 243.92, 243.83, 243.35, 242.96,
242.66, 242, 241.86, 240.97, 240}.
We present Table 2, which represents the number of quaternary sequences of length N = 16 having a given maximum absolute value of the Vilenkin-Chrestenson transform coefficients and, accordingly, the given value of nonlinearity and PAPR.
No. The performed spectral classification of quaternary sequences of length N = 16 is a theoretical basis for the synthesis of sets of 4-functions with a given level of nonlinearity. These sets are the initial material for the construction of cryptographically strong generators of pseudo-random key sequences, as well as cryptographic primitives of block symmetric ciphers and hash functions. Table 2 and Fig. 2 also specifies the maximum cardinalities of the C-code classes for MC-CDMA technology. 5
In conclusion, we note the main results of the research:
1. A method for calculating the possible values of the Vilenkin-Chrestenson transform coefficients is proposed. Because of the dependence of the spectral properties of the sequences and the determination of nonlinearity and PAPR, the proposed method can be applied to estimate the possible values of nonlinearity and PAPR of sequences of many-valued logic. The proposed method is suitable for arbitrary values of q and N, however, in this work, it was applied for the case of quaternary sequences of lengths N = 4 and N = 16.
2. A spectral classification of the full quaternary code of the lengths N = 4 and N = 16 was performed, as a result of which 5 spectral classes of sequences of length N = 4 was distinguished as well as 36 spectral classes of sequences of length N = 16, each of which has a unique elementary structure, and, accordingly, a value of nonlinearity and PAPR.
3. The resulting spectral classification is a theoretical basis for constructing sets of many-valued logic functions with a given level of nonlinearity used in cryptography, as well as for constructing C-codes used to reduce the PAPR in MC-CDMA technology.