Spectral and Nonlinear Properties of the Complete Quaternary Code Nadiia Kazakova1[0000-0003-3968-4094] and Artem Sokolov2[0000-0003-0283-7229] 1 Odesa State Environmental University, Ukraine 2 Odesa National Polytechnic University, Ukraine kaz2003@ukr.net Abstract. The current stage of development of information technologies is char- acterized by the active introduction of the functions of many-valued logic. In particular, many-valued logic functions are used in cryptography to build high- quality cryptographic primitives with a high level of nonlinearity. This circum- stance 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 oc- cupy a special place among other q values in the research of the level of nonlin- earity. This paper presents a universal method for calculating the possible abso- lute 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 elemen- tary 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. Keywords: Many-Valued Logic Function, Cryptography, Nonlinearity, PAPR. 1 Introduction and Statement of the Problem The current stage in the development of cryptography is characterized by the great at- tention of researchers to the methods of many-valued logic [1]. Methods of many-val- ued 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 crypto- graphic 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 many- valued 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) 77 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 . 2 Basic Definitions 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 2π j k zk  e 4 , k  {0,1, 2,3} , (1) then the alphabet of the considered in this paper vectors will consist of the following values 2π 2π 2π 2π j 0 j 1 j 2 j 3 z0  e 4  1; z1  e 4  j; z2  e 4  1; z 2  e 4   j . (2) For each sequence of 4-logic, we define the vector of the Vilenkin-Chrestenson trans- form [11] as the product of some sequence A of 4-valued logic by the transposed Vilenkin-Chrestenson matrix  f  f V T , (3) where the Vilenkin-Chrestenson matrix is defined by the following recurrent construc- tion [4] 78 V4k V4k V4k V4k   z0 z0 z0 z0  V k V k  1 V k  2 V k  3  z z z z  V4k 1   , V4   0 1 2 3  . V4k V4k  2 V4k V4k  2  4 4 4 4 (4) z0 z 2 z0 z 2    z0 z3 z2 z1  V4k V4k  3 V4k  2 V4k  1  In expression (4) matrices V are represented in symbolic form, i.e. the summation is performed relative to the indices zi . 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   q k  max  f , q  2;  Nf   (5) 1   2k 1  max W f , q  2,  2 where W f are the Walsh-Hadamard transform coefficients which are used instead of Vilenkin-Chrestenson transform coefficients in the case of Boolean functions [13]. The formula (5) for calculating the nonlinearity of the many-valued logic functions is basic in cryptography and is used to estimate the level of confusion that can be pro- vided by one or another many-valued logic functions used in cryptographic algorithms. The formula (5) also shows a direct relationship between nonlinearity and spectral properties of many-valued logic sequences. Thus, more detailed research of the struc- ture of the Vilenkin-Chrestenson spectrum of functions of many-valued logic will allow a better understanding of the possible values of their nonlinearity, as well as discovering the sets of sequences with a given level of nonlinearity. 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 Pср  max  f N t 2   (6) where Pmax is the peak power of the signal  f , 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 non- linearity 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. 79 3 Spectral Classification of Quaternary Sequences of Length N=4 Each quaternary sequence of length N  4 can be represented in the following gener- alized form 2π A  a1 a2 a4  , ai  zk  e 4 , k  {0,1, 2,3} . j k a3 (7) 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 trans- form coefficients can be represented as follows S  s1 s2 s3  , si  . (8) 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 admis- sible 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 clas- sification 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 Vilen- kin-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 (2). Let us denote by K0 , K1 , K2 , K3 the number of elements z0 , z1 , z2 and z3 in the se- quence A , respectively. Then the coefficient s1 will take the values s1   K 0  K 2   j  K1  K 3  , (9) where  K 0  K1  K 2  K 3  4,  K , K , K , K  {0,1, 2,3, 4}. (10)  0 1 2 3 It is easy to find that there are only 35 sets of numbers K0 , K1 , K2 , K3 that satisfy con- dition (10) 80  K 0 K1 K 2 K 3 K 0 K1 K 2 K 3 K 0 K1 K 2 K 3  0 0 0 4 0 3 0 1 1 3 0 0  0 0 1 3 0 3 1 0 2 0 0 2  0 0 2 2 0 4 0 0 2 0 1 1  0 0 3 1 1 0 0 3 2 0 2 0  0 0 4 0 1 0 1 2 2 1 0 1  0 1 0 3 1 0 2 1 2 1 1 0  . (11) 0 1 1 2 1 0 3 0 2 2 0 0  0 1 2 1 1 1 0 2 3 0 0 1  0 1 3 0 1 1 1 1 3 0 1 0  0 2 0 2 1 1 2 0 3 1 0 0    0 2 1 1 1 2 0 1 4 0 0 0   0 2 2 0 1 2 1 0  To find the possible absolute values of the coefficient s1 , we substitute solutions (11) into (9), after which, finding the absolute values of complex numbers, we obtain s1  ( K0  K 2 )2  ( K1  K3 )2  {0, 2, 2, 8, 10, 4}. (12) Proposition 1. The set of values (12), and only them, are possible absolute values of the Vilenkin-Chrestenson transform coefficients of vectors of length N  4 . Let us express the value of the first Vilenkin-Chrestenson transform coefficient in terms of the elements of the original sequence s1  [a1 a2 a3 a4 ]  [ z 0 z0 z0 z0 ]T   [a1 a4 ]  1 1 1 1  T a2 a3 (13)  a1  a2  a3  a4 , ai  {z0 , z1 , z2 , z3 }. Similarly, consider the ith Vilenkin-Chrestenson transform coefficient si  [a1 a2 a3 a4 ]  [v0 v1 v2 v3 ]T  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   (14)  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 a2 a3 a4 ], the 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 trans- 1 k form coefficient cannot be lower than q 2  4 2  2 . So, the values of the Vilenkin- Chrestenson transform coefficients of quaternary sequences si  0 and si  2 can- not be the maximum absolute values in the Vilenkin-Chrestenson transform vector. Thus, the set of possible values of nonlinearity by (5) is N f  4  {4, 10, 8, 2}  {0, 0.8377, 1.1716, 2} . (15) 81 We can highlight the method for calculating the possible absolute values of the Vilen- kin-Chrestenson transform coefficients, and, accordingly, the possible values of non- linearity 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 K 0 , K1 ,..., K q 1 of elements of the many-valued logic sequence alphabet. Step 2. Find possible values K 0 , K1 ,..., K q 1 that satisfy the condition  K 0  K1  ...  K q 1  N ,  K , K ,..., K  {0,1,.., N }. (16)  0 1 q 1 Step 3. Substitute the possible values K 0 , K1 ,..., K q 1 into the expression obtained in Step 1 for the absolute value of the first Vilenkin-Chrestenson transform coefficient s1 in terms of the numbers K 0 , K1 ,..., K q 1 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 (5) and (6) for the complete set of possible values of all Vilenkin-Chrestenson transform coef- ficients obtained at Step 3. 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. Table 1. Spectral classification of quaternary vectors of length N = 4 Spectral class represented Class Representative No. Nonlinearity PAPR in the form of irrationalities cardinality sequence 1 {4(1), 0(3)} 16 0 4.0 0000 2 { 10(1), 2(3)} 128 0.8377 2.5 0001 3 { 8(1), 2(2), 0(1)} 64 1.1716 2.0 0011 4 { 8(2), 0(2)} 16 1.1716 2.0 0022 5 {2(4)} 32 2.0000 1.0 0002 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 J 5  32 . In Fig. 1, a histogram of the distribution of nonlinearity of quaternary sequences of length N  4 is shown. 82 Fig. 1. Histogram of nonlinearity distribution of quaternary sequences of length N = 4. 4 Spectral Classification of Quaternary Sequences of Length N = 16 It should be noted that sequence length N  16 is very important in modern crypto- graphic 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 (16) for the case of quaternary sequences of length N  16 takes the following form  K 0  K1  K 2  K 3  16,  K , K , K , K  {0,1, 2,3,...,16}, (17)  0 1 2 3 while the total number of sets of numbers K0 , K1 , K2 , K3 that satisfy condition (17) is 969. 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, (18) 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 83 2 k than q 2  4 2  4 . The values of the Vilenkin-Chrestenson transform coefficients si  0, 2, 2, 8, 10 of quaternary sequences cannot be maximum in the Vilenkin- Chrestenson transform to vector. The full class of possible values of the nonlinearity of quaternary sequences of length N  16 by the formula (5) is 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, 247.40, 247.06, 246.94, 246.51, 246.10, 246.00, (19) 245.80, 245.70, 245.23, 244.95, 244.69, 244.60, 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. Table 2. Spectral classification of quaternary vectors of length N = 16 Cardinality Representative No. Value Nonlinearity PAPR of the class sequence 1 16 0 64 16.00 0000000000000000 2 226 0.97 2048 14.13 0000000000000001 3 200 1.86 15360 12.50 0000000000000011 4 14 2.00 16384 12.25 0000000000000002 5 178 2.66 71680 11.13 0000000000000111 6 170 2.96 245760 10.63 0000000000000012 7 160 3.35 232960 10.00 0000000000001111 8 148 3.83 1146880 9.25 0000000000000112 9 146 3.92 559104 9.13 0000000000011111 10 12 4.00 921600 9.00 0000000000000022 11 136 4.34 1025024 8.50 0000000000111111 12 130 4.60 5191680 8.13 0000000000001112 84 Table 3. Spectral classification of quaternary vectors of length N = 16 (continuation) Cardinality Representative No. Value Nonlinearity PAPR of the class sequence 13 128 4.69 823488 8.00 0000000011111111 14 122 4.95 8601600 7.63 0000000000000122 15 116 5.23 8945664 7.25 0000000000011112 16 106 5.70 16400384 6.63 0000000000111112 17 104 5.80 27955200 6.50 0000000000001122 18 10 6.00 43450368 6.25 0000000000000222 19 98 6.10 13172736 6.13 0000000001113333 20 90 6.51 67092480 5.63 0000000000011122 21 82 6.94 130433024 5.13 0000000000001222 22 80 7.06 122179584 5.00 0000000000111122 23 74 7.40 172720128 4.63 0000000000122233 24 72 7.51 95625216 4.50 0000000000122333 25 68 7.75 300613632 4.25 0000000000011222 26 8 8.00 195660800 4.00 0000000000002222 27 58 8.38 510885888 3.63 0000000000021222 28 52 8.79 586743808 3.25 0000000000220222 29 50 8.93 885211136 3.13 0000000000220122 30 40 9.68 628068352 2.50 0000000100021222 31 6 10.00 109428736 2.25 0000000200020222 32 34 10.17 324706304 2.13 0000000200120222 33 32 10.34 22414592 2.00 0000000200220222 34 26 10.90 12189696 1.63 0000001200222310 35 20 11.53 2015232 1.25 0000001201323211 36 4 12.00 200704 1.00 0000002202020220 85 Fig. 2. Histogram of nonlinearity distribution of quaternary sequences of length N = 16. The performed spectral classification of quaternary sequences of length N = 16 is a the- oretical 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 gen- erators 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 Conclusion In conclusion, we note the main results of the research: 1. A method for calculating the possible values of the Vilenkin-Chrestenson trans- form 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 nonline- arity 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. 86 References 1. Sokolov, A. V., Zhdanov, O. N.: Prospects for the application of many-valued logic func- tions in cryptography. Int. Conf. Theory Appl. Fuzzy Sys. Soft Comput.: 331–339 (2018). https://doi.org/10.1007/978-3-319-91008-6_33 2. Gnatyuk, S., Zhmurko, T., Falat, P.: Efficiency increasing method for quantum secure direct communication protocols. IEEE Proc. 8th Int. Conf. Intell. Data Acquis. Adv. Comput. Sys.: Technol. Appl. (IDAACS): 468–472 (2015). https://doi.org/10.1109/IDAACS.2015. 7340780 3. Gnatyuk, S. O., Zhmurko, T. O., Kіnzeryavy, V. M., Siyilova, N. A.: Method for quality evaluation of trit pseudorandom sequence to cryptographic applications. Inf. Technol. Secur. 2(3): 108–116 (2015). https://doi.org/10.20535/2411-1031.2015.3.2.60891 4. Sokolov, A. V., Zhdanov, O. N.: Cryptographic Constructions Based on Many-Valued Logic Functions. Scientific Thought (2020). https://doi.org/10.12737/1045434 5. Bessalov, A. V.: Calculation of parameters of cryptographically robust “Edwards curve” over the fields of characteristics 5 and 7. Cybersecur. Educ. Sci. Tech. 1(1): 94–104 (2018). https://doi.org/10.28925/2663-4023.2018.1.94104 6. Zhdanov, O. N., Sokolov, A. V.: Block symmetric cryptographic algorithm based on prin- ciples of variable block length and many-valued logic. Far East J. Electron. Commun. 16(3): 573–589 (2015). https://doi.org/10.17654/ec016030573 7. Bessalov, A., Grubiyan, E., Sokolov, V., Skladannyi, P.: 3- and 5-isogenies of supersingular Edwards curves. Cybersecur. Educ. Sci. Tech. 4(8): 6–21 (2020). https://doi.org/10.28925/ 2663-4023.2020.8.621 8. Paterson, K. G.: Sequences for OFDM and multi-code CDMA: Two problems in algebraic coding theory, sequences and their applications. Discret. Math. Theor. Comp. Sci.: 46–71 (2001). https://doi.org/10.1007/978-1-4471-0673-9_4 9. Schmidt, K.:Quaternary constant-amplitude codes for multicode CDMA. IEEE Int. Symp. Inf. Theory: 2781–2785 (2007). https://doi.org/10.1109/isit.2007.4557639 10. Zhdanov, O. N., Sokolov, A. V.: A synthesis method of basic ternary bent-squares based on the triad shift operator. Syst. Anal. Appl. Inf. Sci. 1: 77–85 (2017). https://doi.org/10.21122/ 2309-4923-2017-1-77-85 11. Trakhtman, A. M., Trakhtman, V. A.: Elements of Theory of Discrete Signals on Finite In- tervals (1975) 12. Sokolov, A. V., Krasota, N. I.: Very nonlinear permutations: synthesis method for S-boxes with maximal 4-nonlinearity. Proc. ONAT 1: 145–154 (2017). [Publication in Russian] 13. Maier, W.: Nonlinearity criteria for cryptographic functions. Adv. Cryptol. Eurocrypt. Lect Notes Comput. Sci.: 549–562 (1990). https://doi.org/10.1007/3-540-46885-4_53 14. Sokolov, A. V., Barabanov, N. A.: Algorithm for removing the spectral equivalence of com- ponent Boolean functions of Nyberg-design S-boxes, Radioelectron. Commun. Syst. 58(5): 220–227 (2015). https://doi.org/10.3103/s0735272715050040 15. Logachev, O. A., Salnikov, A. A., Iashchenko, V. V.: Boolean functions in coding theory and cryptography. Am. Math. Soc. 241 (2012). https://doi.org/10.1090/mmono/241 16. Tokareva, N.: Bent Functions: Results and Applications to Cryptography (2015). https://doi.org/10.1016/b978-0-12-802318-1.00004-2