Non-Binary Constant Weight Coding Technique

Abstract

This paper presents research results of mixed base number systems using a binomial representation of numbers and nonlinear coding techniques by constant weight codes, which are based on a binomial count. Also we propose a technique of non-binary constant weight coding based on a generalized binomial-positional representation, which allows to generalize the known approach to the non-binary case and practically implement computational algorithms for generating non-binary sequences of constant weight. The proposed technique of non-binary constant weight coding can be useful for improving post-quantum code-based cryptographic algorithms.

Keywords

• constant weight coding
• mixed base number systems
• binomial count
• code-based cryptographic algorithms

Introduction

The computational efficiency of arithmetic operations directly depends on the technique of representing numbers on which operations are performed, i.e. on the applied number system [ 1–4 ]. The most common is the positional number system in which the same numerical sign (digit) in the number record has different meanings, depending on the position where it is located [ 3, 4 ]. Among these systems is the modern decimal number system, the occurrence of which is associated with a finger count, the binary number system used in modern computers, etc.

A mixed base number system is a generalization of the positional system, its base is an increasing number sequence and each represented number is expressed through a linear combination of base elements [ 3–6 ]. Mixed base number systems include the Fibonacci number system, factorial, binomial and other systems [ 6–8 ].

It should be noted that many applications are based on the binomial number system, including the so-called binomial codes that belong to the class of nonlinear binary redundancy codes used to increase the noise immunity of binary asymmetric data transmission channels [ 3, 6–8 ]. The main property of binomial codes, an equal Hamming weight (the number of nonzero elements) of all codewords, is used to effectively detect asymmetric distortions of transmitted sequences. In this case, a change of Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).

Hamming weight of the sequence is an adequate criterion for detecting errors in asymmetric binary data channels.

Another, equally demanded application of constant weight codes consists in constructing provably robust cryptosystems [ 9–12 ], the security of which is justified by the reducability of the private key calculation task to the solution of the theoretical complexity problem of syndrome decoding [ 13, 14 ]. So, for example, in [ 15–17 ], provable secure encryption systems are considered. In works [ 18–20 ], code-based electronic signature schemes are considered, their parameters and basic properties are investigated. In articles [ 21, 22 ], pseudorandom number generators based on codes are studied, as well as promising stream encryption schemes [ 23–26 ]. Papers [ 27–29 ] are devoted to the study of zero-knowledge proof schemes. The design of fast and secure code-based hash functions is investigated in [ 25, 30–32 ].

Thus, code-based cryptography has many important applications. These crypto primitives are post-quantum security algorithms, i.e. they will be strong even under the conditions of possible quantum cryptanalysis [ 9–12 ].

Constant weight codes are used as one of the elements of code-based cryptosystems. In particular, in encryption systems, sequences with constant weights are used as a session key [ 16, 33, 34 ]. To generate a digital signature using the decoding algorithm, it is necessary to find a sequence with constant weight [ 18–20, 35 ]. When generating pseudo-random numbers, constant weight codes are used in the feedback circuit of the generator [ 21–23 ]. The input data for a code-based hash function is first converted to a constant weight sequence and then processed by a compression function [ 30, 32 ].

It should be noted that all listed applications only use binary constant weight codes.

The discrete mathematics literature also describes only binary algorithms [ 1, 2, 4 ]. We offer non-binary constant weight coding technique. This will greatly expand the area of possible use of code-based cryptosystems. In particular, the practical implementation of non-binary (for example, over finite field GF (2m ) ) codes can work faster and more efficiently, while providing a high level of strength of code-based cryptosystems. This determines the relevance of this article, a purpose of which is to develop a technique of non-binary constant weight coding based on a generalized binomialpositional representation. 2

Positional and Mixed Base Number Systems. Binary technique and Algorithm of Constant Weight Coding The positional number system is based on a positional numbering, i.e. on a local value of digits, and is determined by a certain number b  1 (a base of the number system) such that the b units in each category are combined into one unit of the next highest rank. The number system is also called b -positional system [ 1, 2, 13 ].

A number x in a b -ary positional number system is represented as a linear combination of powers of number b where ai are integers called numbers and they satisfy an inequality: i is a discharge sequence number, starting from zero, n is a number of bits (length) of the position code.

Each degree bi in such record is called a rank, the certain rank and the corresponding numbers is determined by the value of the indicator i . Usually, for a nonzero number x , the leading digit an1 in the b -ary representation is also required to be nonzero.

If there are no discrepancies (for example, when all the numbers are presented in the form of unique written characters), the number is recorded as a sequence of its b ary digits, listed in ascending order of rank from left to right:

A mixed base number system is a generalization of the b -ary system and also often refers to positional number systems. The basis of the mixed base system is an increasing numbers sequence and each number is represented as a linear combination:

n1 x   aibi ,

i0 0  ai  b , where some code restrictions are imposed on the coefficients ai .

Numeral x in a mixed base number system is an enumeration of its numbers in decreasing order of the index i , starting with the first nonzero. If for some bi  bi , then the mixed base number system coincides with the b - ary positional number system.

The binomial number system is based on the representation of numbers through an increasing sequence of binomial coefficients b0   u1  , b1   u2  ,...,bn1   un  ,  1   2   n   ui1   bi    i 1 where w is number of non-zero elements of binomial code.

A number x in the binomial system is represented as a linear combination: n1 n1  ui1  , x   aibi   ai  i 1

i0 i0 where coefficients ai 0,1 .

In the case when there are no discrepancies in the calculation of binomial coeffi

 ui1  , i.e. when a rule is established for the formation of a numbers set cients , bi  

 i 1 0  u1  u2  ...  un , the number x is written in increasing order of ranks ai from left to right:  n is a length of the constant weight code, i.e. the number of elements (bits) of code

sequences (code words);  С  С0 ,C1,...,CM 1 is a set of code words for the constant weight code, where j : wCj   const  w , where wC j0

C j1 ... C jn1   #C j0

C j1

... C jn1  Cji 0 , #C j0

C j1 ... C jn1  Cji 0

is a number C ji , i  0,1,..., n 1 , where C ji  0 .

The power of the constant weight code (the number of elements in the set С ) is determined by the number of binary vectors of length n and weight w : j  0,1,..., M 1 we have equal

weight Hamming: С  М 

The well-known binomial (binary constant weight) coding technique [ 6, 7, 13 ] is based on the presentation of information data in the form of a numerical equivalent (denoted by a number A ) with further decomposition into a linear combination of binomial coefficients. Such system of code restrictions on the length of sequences of constant weight n , codeword weights w and code cardinality М are satisfied: j : wC j   const  w;   0  A  M ;  0  w  n.

 The number A is presented as binary sequence CA  CA0 CA1

... CAn1  of n1  n  i 1 constant weight and A  CAni1bi , where bi   w  l  , l is a nonzero element

i0 number in CA , l  0,1,..., w .

i1 Nonzero element is a CAni1 , for which bi   CAnm1bm .

m0

Obviously, the sum on the right side of the expression is equal to the sum of only bm those for which the corresponding elements of the vector CA are not equal to zero ( CAnm1  0 ).

It should be noted that the considered technique does not imply the formation of non-binary sequences with constant weight (vectors CA with Cji 0,1,..., q 1 , q  2 ) and thus does not allow the implementation of non-binary constant weight coding.

The article proposes a new technique of non-binary constant weight coding based on a generalized binomial-positional representation, which allows us to generalize the above approach to the non-binary case and practically implement computational algorithms for generating non-binary sequences of constant weight. 3

Proposed Technique of Non-Binary Constant Weight Coding To generalize the considered approach of generating sequences of constant weight to the non-binary case, a new form of a generalized binomial-positional representation of numbers is proposed. The proposed number system belongs to the class of mixed base systems and is based on the representation of numbers through an increasing sequence of binomial coefficients, each of which is encoded by positional numbering, i.e. the representation of digits with binomial coefficients is based on the local value of the digits.

Consider the number x in the proposed generalized binomial-positional number

n1 system: x   aibi .

i0 Let’s introduce the following notation and equalities:

 ui1   ai 0,1,..., q 1 , bi    i 1

,

, where w is a number of nonzero elements of the generalized binomial-positional code.

Then the number x is represented through an increasing sequence of binomial coefficients b0 ,b1,...,bn1 , and corresponding sequence a0 , a1,..., an1 .

Let's consider nonzero elements ai  1, i  0,1,..., n 1, sequences a0 , a1,..., an1 and renumber them, i.e. we denote them as elements of the sequence a0 , a1,..., aw1 , l  0,1,..., w 1 and l : al 1,..., q 1 .

A sequence a0 , a1,..., aw1 and all its elements al (nonzero elements of a sequence a0 , a1,..., an1 numbered according to the increasing digits order) are formed using a positional number system on the base q 1 , i.e. q 1 units in each rank are combined into one unit of the next highest rank. A set of nonzero elements sets al , l  0,1,..., w 1 defines the number xP that is represented in the positional system as follows:

w1 xP  al 1 hl ,

l0 where h  q 1 is a base of used positional system, 1  al  q .

The increasing sequence of binomial coefficients b0 ,b1,...,bn1 sets a number xB , n1 which is represented in the binomial number system as xB   aBibi , where coeffii0 cients aBi 0,1 .

The number x in the proposed generalized binomial-positional number system satisfies the following equality:

x  xB  q-1w  xP , which sets a main code restriction on the elements of the generalized binomialpositional code.

Thus, the number x in the proposed system of generalized binomial-positional counting is represented as a linear combination: x  n1 aibi  xB  q-1w  xP 

i0  q-1w n1 aBibi  w1 al 1 q 1l .

i0 l0

The proposed generalization of the binomial-positional way of representing numbers consists in the complex use of the positional number system and the binomial counting system: the first term on the right side of the equality, through the increasing sequence of binomial coefficients, determines the placement of nonzero elements of the generalized binomial-positional code, the second term defines the values of nonzero elements of the sequence in positional code.

The proposed technique of representing numbers is based on the technique of nonbinary constant weight coding. For the abstract definition of a non-binary constant weight code, we introduce the following formal notation:  n is a code length;  С  С0 ,C1 ,...,CM 1 is a set of code words,

... Cjn1  C, Cji 0,1,..., q 1, j  0,1,..., M 1, i  0,1,..., n 1, j : wCj   const  w .

The cardinality of a non-binary constant weight code defined in this way is determined by the number of length n and weight w vectors with elements from the set 0,1,..., q 1 : С  М  q 1w

.

The proposed technique is based on the presentation of information data in the form of a numerical equivalent A with further decomposition into a linear combination of binomial coefficients, each of which is encoded by positional numbering so that a system of code restrictions on the length of n sequences of constant weight, the weight w of code words and code cardinality М is satisfied:

AB   A 

 q-1w  , AP   A mod q-1w  , where  y is the integer part of number y .

The uniqueness of the representation of number A in the form of numbers AB and AP is justified by the Chinese remainder theorem [ 13 ].

The number AB lies within 0  AB  M w and can be represented in a binomial

q 1 number system with code restrictions:

The number AP lies within 0  AP  q 1w and, accordingly, can be represented in the positional number system on the basis of h  q 1 .

1. Representation of numbers in a binomial number system: j : wc j   const  w;   0  AB  w!nn! w!;  0  w  n.

n1  n  i 1 AB   aBibi , bi   w  l  .

i0 w1 AP  al 1 hl , h  q 1 .

l0 2. Representation of a number AP in a positional number system: Generating of sequence CA  CA0

CA1

... CAn1  C :

CAi  al aBi , i  0,1,..., n 1, l  0,1,..., w 1 , i.e., A aB0 aB1 aB2  and a0  and generated non-binary vectors CA  CA0 of constant weight are shown in table 1. forms a non-binary constant weight code C  C0 ,C1,...,C8 .

Thus, the proposed number system based on the generalized binomial-positional representation of numbers allows complex use of both the local value of the digits of the code sequence and the values of binomial coefficients specified by the placement of nonzero elements of the sequence. Application of the developed number system allows us to build effective techniques and algorithms of non-binary constant weight coding for their use in various practical applications. For example, the proposed technique can be useful for improving post-quantum code-based cryptographic algorithms (ciphers, electronic digital signatures, key encapsulation schemes, pseudorandom number generators, etc.) [ 19, 21, 23, 31, 32, 36 ]. The use of constant weight codes is also one of the basic transformations for the functioning of code-based cryptosystems.

In particular, constant weight codes are used in the McEliece [ 33 ] and Niederreiter [ 17 ] public key encryption schemes, as well as in electronic signature schemes and code-based pseudorandom numbers generators. It is worth noting that at the moment, code-based cryptography is considered one of the most optimal ways of developing post-quantum cryptography. A good example of the use of constant weight codes in cryptosystems is a Niederreiter encryption process, which consists of several basic steps. First, user generates key and system parameters. Next, an information sequence e that needs to be encrypted is converted using constant-weight codes into a sequence of fixed length n and constant weight t . Then vector syndrome s  e  HxT must be calculated.

This vector is a ciphertext, i.e. an encrypted message that can be decrypted only by the user who has a secret key. Decryption consists in removing the action of masking matrices, after which the sequence is decoded using a fast algebraic technique. The found error vector is a sequence of constant weight e . To restore the information sequence, the conversion is used, the inverse of what was used. As you can see, each possible information sequence should be uniquely associated with the corresponding constant weight sequence, i.e. to build a code-based cryptosystem, it is necessary to implement an algebraic rule of this correspondence, implemented through an constant weight account system.

Thus, it is necessary to realize a one-to-one correspondence between all possible information sequences and various constant weight vectors. In the other words, for an arbitrary countable set (in advance of a given power), it is required to implement a new recording technique (number system) in the form of a set of constant weight vectors. At the moment, resistance versions of the constructions of code-based cryptosystems are based on the use of binary Goppa codes. In this simplest case, it is possible to use the well-known binomial count to convert information sequences into constant weight binary vectors. In the general case, code-based cryptosystems can be built for arbitrary base. And for this general case, we offer a generalized binomialpositional number system and a new technique of non-binary constant weight coding (binomial-positional counting). This will not only increase the strength of code-based cryptosystems, but also provide additional useful properties, such as the control of non-binary errors during transmission.

In addition, this study can be useful in other practical applications, for example, to improve channel coding techniques, to prevent interference in telecommunication networks, etc. 4

Conclusions

As a result of the research, a new number system based on the generalized binomialpositional representation of numbers is proposed. It is that the complex use of the binomial counting system (through the increasing binomial coefficients sequence defines a position of nonzero element) and the positional number system (the values of nonzero elements are specified through the local value of numbers).

For the first time, a technique of non-binary constant weight coding based on a generalized binomial-positional representation of numbers is proposed, which allows us to generalize the well-known approach to the non-binary case and practically implement computational algorithms for generating non-binary sequences of constant weight.

The proposed non-binary constant weight coding technique is a generalization of the well-known binary case. In fact, a well-known binary code is used to represent a number in the binomial number system. Nonzero elements of the resulting binomial sequence are additionally encoded with a positional code. Thus, the complexity of the implementation of the proposed technique is defined as the total complexity of the known techniques of binomial and positional coding.

The developed technique can be used in various practical applications, for example, in code-based cryptosystems: ciphers, electronic digital signatures, key encapsulation schemes, pseudorandom number generators, etc. These cryptosystems are expected to be safe even in the conditions of the possible application of quantum cryptographic analysis techniques, i.e. focused on the post-quantum period.

References

1. Anderson , J.A. : Discrete Mathematics With Combinatorics . Prentice Hall, Upper Saddle River, N.J ( 2003 )

2. Knuth , D.E. : The art of computer programming , volume 2 (3rd ed.) : seminumerical algorithms . Addison-Wesley Longman Publishing Co., Inc., USA ( 1997 )

3. Borisenko , A.A. , Kalashnikov , V.V. , Protasova , T.A. , Kalashnykova , N.I.: A New Approach to the Classification of Positional Numeral Systems . In: IDT/IIMSS/STET ( 2014 )

4. Wolfram Demonstrations Project brings ideas to life with over 11k interactive #WolframNotebooks for education , research, recreation & more. #WolframDemo #WolfLang, http://demonstrations.wolfram.com/NumberSystemsUsingAComplexBase/

5. Stakhov , A. : Numeral Systems with Irrational Bases for Mission-Critical Applications . World Scientific Publishing Co Pte Ltd , New Jersey ( 2017 )

6. Borisenko , A. , Kalashnykova , N. , Kalashnikov , V. , Gutenko , D. : Binomial Numeral Systems: Description and Applications to Numeration Problems(<Special Issue>Variational Inequality and Combinatorial Problems) . International Journal of Biomedical Soft Computing and Human Sciences: the official journal of the Biomedical Fuzzy Systems Association . 17 , 11 - 17 ( 2012 ). https://doi.org/10.24466/ijbschs.17.2_ 11

7. Borisenko , A. , Kalashnikov , V. , Kalashnykova , N.: BINOMIAL CALCULUS: ADVANTAGES AND PROSPECTS . 8 ( 2008 )

8. Borysenko , O.A. , Kalashnikov , V.V. , Kalashnykova , N.I. , Matsenko , S.M.: The Fibonacci Numeral System for Computer Vision . In: Favorskaya, M.N. and Jain , L.C. (eds.) Computer Vision in Control Systems-3: Aerial and Satellite Image Processing . pp. 321 - 343 . Springer International Publishing, Cham ( 2018 )

9. Overbeck , R. , Sendrier , N.: Code-based cryptography . In: Bernstein, D.J. , Buchmann , J. , and Dahmen , E. (eds.) Post-Quantum Cryptography . pp. 95 - 145 . Springer, Berlin, Heidelberg ( 2009 )

10. Bernstein , D.J. : Introduction to post-quantum cryptography . In: Bernstein, D.J. , Buchmann , J. , and Dahmen , E. (eds.) Post-Quantum Cryptography . pp. 1 - 14 . Springer, Berlin, Heidelberg ( 2009 )

11. Ding , J. , Tillich , J.-P. eds: Post-Quantum Cryptography : 11th International Conference, PQCrypto 2020 , Paris, France, April 15-17 , 2020 , Proceedings. Springer International Publishing, Cham ( 2020 )

12. Ding , J. , Steinwandt , R. eds: Post-Quantum Cryptography : 10th International Conference, PQCrypto 2019 , Chongqing, China, May 8- 10 , 2019 Revised Selected Papers . Springer International Publishing, Cham ( 2019 )

13. The Theory of Error-Correcting Codes . Elsevier ( 1977 )

14. Blahut , R.E. : Theory and Practice of Error Control Codes . Addison-Wesley, Reading, MA ( 1983 )

15. Sendrier , N.: Niederreiter Encryption Scheme . In: van Tilborg, H.C. A. and Jajodia , S. (eds.) Encyclopedia of Cryptography and Security . pp. 842 - 843 . Springer US, Boston, MA ( 2011 )

16. Sidelnikov , V.M. , Shestakov , S.O. : On insecurity of cryptosystems based on generalized Reed-Solomon codes . Discrete Mathematics and Applications . 2 , 439 - 444 ( 1992 ). https://doi.org/10.1515/dma. 1992 . 2 .4. 439

17. NIEDERREITER , H.: Knapsack-type cryptosystems and algebraic coding theory . Prob. Contr. Inform. Theory . 15 , 157 - 166 ( 1986 )

18. Courtois , N.T. , Finiasz , M. , Sendrier , N.: How to Achieve a McEliece-Based Digital Signature Scheme . In: Boyd, C . (ed.) Advances in Cryptology - ASIACRYPT 2001 . pp. 157 - 174 . Springer, Berlin, Heidelberg ( 2001 )

19. Finiasz , M. : Parallel-CFS . In: Biryukov, A. , Gong , G. , and Stinson , D.R . (eds.) Selected Areas in Cryptography. pp. 159 - 170 . Springer, Berlin, Heidelberg ( 2011 )

20. Kuznetsov , A. , Kiian , A. , Pushkar'ov, A. , Mialkovskyi , D. , Smirnov , O. , Kuznetsova , T. : Code-Based Schemes for Post-Quantum Digital Signatures . In: 2019 10th IEEE International Conference on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications (IDAACS) . pp. 707 - 712 ( 2019 )

21. Fischer , J.-B. , Stern , J.: An Efficient Pseudo-Random Generator Provably as Secure as Syndrome Decoding . In: Maurer, U . (ed.) Advances in Cryptology - EUROCRYPT '96 . pp. 245 - 255 . Springer, Berlin, Heidelberg ( 1996 )

22. Kuznetsov , A. , Kiian , A. , Smirnov , O. , Cherep , A. , Kanabekova , M. , Chepurko , I. : Testing of Code-Based Pseudorandom Number Generators for Post-Quantum Application . In: 2020 IEEE 11th International Conference on Dependable Systems, Services and Technologies (DESSERT) . pp. 172 - 177 ( 2020 )

23. Gaborit , P. , Lauradoux , C. , Sendrier , N.: SYND: a Fast Code-Based Stream Cipher with a Security Reduction . In: 2007 IEEE International Symposium on Information Theory . pp. 186 - 190 ( 2007 )

24. Meziani , M. , Hoffmann , G. , Cayrel , P.-L.: Improving the Performance of the SYND Stream Cipher . In: Mitrokotsa, A. and Vaudenay , S. (eds.) Progress in Cryptology - AFRICACRYPT 2012 . pp. 99 - 116 . Springer, Berlin, Heidelberg ( 2012 )

25. Implementation of code-based hash-functions and stream-ciphers - Pierre-Louis Cayrel , http://www.cayrel.net/? Implementation-of-code-based-hash

26. Meziani , M. , Cayrel , P.-L., El Yousfi Alaoui , S.M.: 2SC: An Efficient Code-Based Stream Cipher . In: Kim, T. , Adeli , H. , Robles , R.J. , and Balitanas , M. (eds.) Information Security and Assurance . pp. 111 - 122 . Springer Berlin Heidelberg, Berlin, Heidelberg ( 2011 )

27. Aguilar , C. , Gaborit , P. , Schrek , J.: A new zero-knowledge code based identification scheme with reduced communication . In: 2011 IEEE Information Theory Workshop . pp. 648 - 652 ( 2011 )

28. Aguilar , C. , Gaborit , P. , Schrek , J.: A new zero-knowledge code based identification scheme with reduced communication . arXiv:1111 .1644 [cs]. ( 2011 )

29. Brunetta , C. , Liang , B. , Mitrokotsa , A. : Code-Based Zero Knowledge PRF Arguments . In: Lin, Z. , Papamanthou , C. , and Polychronakis , M. (eds.) Information Security. pp. 171 - 189 . Springer International Publishing, Cham ( 2019 )

30. Finiasz , M. , Gaborit , P. , Sendrier , N.: Improved Fast Syndrome Based Cryptographic Hash Functions . Presented at the ( 2005 )

31. Bernstein , D.J. , Lange , T. , Peters , C. , Schwabe , P. : Really Fast Syndrome-Based Hashing . In: Nitaj, A. and Pointcheval , D. (eds.) Progress in Cryptology - AFRICACRYPT 2011 . pp. 134 - 152 . Springer, Berlin, Heidelberg ( 2011 )

32. Augot , D. , Finiasz , M. , Sendrier , N.: A Family of Fast Syndrome Based Cryptographic Hash Functions . In: Dawson, E. and Vaudenay , S. (eds.) Progress in Cryptology - Mycrypt 2005 . pp. 64 - 83 . Springer, Berlin, Heidelberg ( 2005 )

33. McEliece , R.J. : A Public-Key Cryptosystem Based On Algebraic Coding Theory. Deep Space Network Progress Report . 44 , 114 - 116 ( 1978 )

34. Kuznetsov , A. , Svatovskij , I. , Kiyan , N. , Pushkar 'ov, A.: Code-based public-key cryptosystems for the post-quantum period . In: 2017 4th International Scientific-Practical Conference Problems of Infocommunications. Science and Technology (PIC S T ) . pp. 125 - 130 ( 2017 )

35. Kuznetsov , A. , Kiian , A. , Babenko , V. , Perevozova , I. , Chepurko , I. , Smirnov , O. : New Approach to the Implementation of Post-Quantum Digital Signature Scheme . In: 2020 IEEE 11th International Conference on Dependable Systems, Services and Technologies (DESSERT) . pp. 166 - 171 ( 2020 )

36. Meziani , M. , Dagdelen , Ö., Cayrel , P.-L., El Yousfi Alaoui , S.M.: S-FSB : An Improved Variant of the FSB Hash Family . In: Kim, T. , Adeli , H. , Robles , R.J. , and Balitanas , M. (eds.) Information Security and Assurance . pp. 132 - 145 . Springer, Berlin, Heidelberg ( 2011 )