On ideal $ t $-tuple distribution of orthogonal functions in filtering de bruijn generators

Kalikinkar Mandal; Guang Gong

doi:10.3934/amc.2020125

Article Contents

2022, Volume 16, Issue 3: 597-619. Doi: 10.3934/amc.2020125

This issue Previous Article Complete weight enumerator of torsion codes Next Article A practicable timing attack against HQC and its countermeasure

On ideal $ t $-tuple distribution of orthogonal functions in filtering de bruijn generators

Kalikinkar Mandal^, and
Guang Gong

Department of Electrical and Computer Engineering, University of Waterloo, Waterloo, Ontario, N2L 3G1, CANADA

^* Corresponding author
^* Corresponding author

Received: May 31, 2019

Revised: October 31, 2020

Early access: December 2020

Published: August 2022

Abstract Full Text(HTML) Figure(2) / Table(2) Related Papers Cited by

Abstract

Uniformity in binary tuples of various lengths in a pseudorandom sequence is an important randomness property. We consider ideal $ t $-tuple distribution of a filtering de Bruijn generator consisting of a de Bruijn sequence of period $ 2^n $ and a filtering function in $ m $ variables. We restrict ourselves to the family of orthogonal functions, that correspond to binary sequences with ideal 2-level autocorrelation, used as filtering functions. After the twenty years of discovery of Welch-Gong (WG) transformations, there are no much significant results on randomness of WG transformation sequences. In this article, we present new results on uniformity of the WG transform of orthogonal functions on de Bruijn sequences. First, we introduce a new property, called invariant under the WG transform, of Boolean functions. We have found that there are only two classes of orthogonal functions whose WG transformations preserve $ t $-tuple uniformity in output sequences, up to $ t = (n-m+1) $. The conjecture of Mandal et al. in [29] about the ideal tuple distribution on the WG transformation is proved. It is also shown that the Gold functions and quadratic functions can guarantee $ (n-m+1) $-tuple distributions. A connection between the ideal tuple distribution and the invariance under WG transform property is established.

Keywords:

Mathematics Subject Classification: Primary: 94A60, 94A55; Secondary: 94A15.

Citation:

Full Text(HTML)

Figure 1. Block diagram of a filtering de Bruijn generator (FDBG)

Download: Full-size image PowerPoint slide

Figure 2. Relations among Hadamard Transform, WG-inv, $ x_0 $-independence and ideal tuple distribution. $ g(\cdot) $ is independent of $ x_0 $. $ \leftrightarrow $ denotes if and only if condition, $ \rightarrow $ denotes if condition and $ n $ is the NLFSR length

Download: Full-size image PowerPoint slide

Table 1. A summary of the Hadamard transform values of three-term functions

Functions	Hadamard Transform values	Ref.
$ w(x) = T3(x^{2^k+1}) = {\rm Tr}(x + x^r + x^{r^2}) $	$ 3 $-valued	[11]
$ g(x) = T3(x^{2^k-1}) = {\rm Tr}(x + x^{q_2} + x^{q_2^2}) $	at most $ 5 $-valued	[39]
$ WG_{w}(x) = {\rm Tr}(x + (x+1)^{r} + (x+1)^{r^2}) $	$ 3 $-valued	Lemma 3.7
$ WG_{g}(x) = {\rm Tr}(x + (x+1)^{q_2} + (x+1)^{q_2^2}) $	at most $ 5 $-valued	Lemma 3.7
$ WG_{T3}(x^d) = {\rm Tr}(x^d + (x^d+1)^{q1} + (x^d+1)^{q_2}) $	at most $ 5 $-valued	Theorem 3.8

| Show Table

DownLoad: CSV

Table 2. Experimental results for ideal $ t $-tuple distributions of the WG transform of the Kasami power functions for $ k' = 3, 4 $ and $ 5 $. When $ k' = 3 $, $ WG_{R_3}(x^d) $ over $ {\mathbb F}_{2^m} $

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	S. Arora and B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009. doi: 10.1017/CBO9780511804090.
[2]	S. Boztas and P.V. Kumar, Binary sequences with Gold-like correlation but larger linear span, IEEE Trans. Inf. Theory, 40 (1994), 532-537. doi: 10.1109/18.312181.
[3]	N. G. de Bruijn, A combinatorial problem, Proc. Koninklijke Nederlandse Akademie v. Wetenschappen, 49 (1946), 758-764.
[4]	A. Canteaut, Analysis and Design of Symmetric Ciphers, Habilitation for directing Theses, University of Paris 6, 2006. Available from: https://www.rocq.inria.fr/secret/Anne.Canteaut/canteaut-hdr.pdf.
[5]	C. Carlet, Boolean functions for cryptography and error correcting codes, Chapter of the monography Boolean models and methods in mathematics, computer science, and engineering, Cambridge University Press, (2010), 257–397.
[6]	A. H. Chan, R. A. Games and E. L. Key, On the complexities of de Bruijn sequences, Journal of Combinatorial Theory, Series A, 33 (1982), 233-246. doi: 10.1016/0097-3165(82)90038-3.
[7]	A. Chang, P. Gaal, S. W. Golomb, G. Gong, T. Helleseth and P. V. Kumar, On a conjectured ideal autocorrelation sequence and a related triple-error correcting cyclic code, IEEE Trans. Inf. Theory, 46 (2000), 680-687. doi: 10.1109/18.825842.
[8]	T. W. Cusick and P. Stănică, Cryptographic Boolean Functions and Applications, Elsevier/Academic Press, Amsterdam, 2009.
[9]	National Institute of Standards and Technology, Digital Signature Standard (DSS), Federal information processing standards publication, FIPS PUB 186-2, Reaffirmed, 2000.,
[10]	J. F. Dillon, Multiplicative difference sets via additive characters, Designs, Codes and Cryptography, 17 (1999), 225-235. doi: 10.1023/A:1026435428030.
[11]	J. F. Dillon and H. Dobbertin, New cyclic difference sets with singer parameters, Finite Fields and Their Applications, 10 (2004), 342-389. doi: 10.1016/j.ffa.2003.09.003.
[12]	L. Ding, C. Jin, J. Guan and Q. Wang, Cryptanalysis of lightweight WG-8 stream cipher, IEEE Trans. Inf. Forensics and Security, 9 (2014), 645-652. doi: 10.1109/TIFS.2014.2307202.
[13]	L. Ding, C. Jin, J. Guan, S. Zhang, T. Cui, D. Han and W. Zhao, Cryptanalysis of WG family of stream ciphers, Computer Journal, 58 (2015), 2677-2685. doi: 10.1093/comjnl/bxv024.
[14]	The eStream project, (2008). Available from: http://www.ecrypt.eu.org/stream/project.html.
[15]	X. Fan, K. Mandal and G. Gong, WG-8: A lightweight stream cipher for resource-constrained smart devices, 9th International Conference on Quality, Reliability, Security and Robustness in Heterogeneous Networks, Springer Berlin, (2013), 617–632. doi: 10.1007/978-3-642-37949-9_54.
[16]	X. Fan, N. Zidaric, M. Aagaard and G. Gong, Efficient hardware implementation of the stream cipher WG-16 with composite field arithmetic, The 2013 ACM Workshop on Trustworthy Embedded Devices (TrustED'13), ACM Press, (2013), 21–34. doi: 10.1145/2517300.2517305.
[17]	R. Gold, Maximal recursive sequences with 3-valued recursive cross-correlation functions, IEEE Trans. Inf. Theory, 14 (1968), 154-156. doi: 10.1109/TIT.1968.1054106.
[18]	J. Dj Golić, On the security of nonlinear filter generators, in 1996 Proceedings of Fast Software Encryption, Springer, Berlin, Heidelberg, (1996), 173–188.
[19]	S. W. Golomb, On the classification of balanced binary sequences of period $2^n-1$, IEEE Trans. Inf. Theory, 26 (1980), 730-732. doi: 10.1109/TIT.1980.1056265.
[20]	S. W. Golomb, Shift register sequences, Aegean Park Press, Laguna Hills, CA, (1981).
[21]	S. W. Golomb and G. Gong, Signal Design for Good Correlation: For wireless Communication, Cryptography and Radar, Cambridge University Press, New York, 2005. doi: 10.1017/CBO9780511546907.
[22]	G. Gong, P. Gaal and S. W. Golomb, A suspected infinity class of cyclic Hadamard difference sets, Proceedings of 1997 IEEE Information Theory Workshop, Longyearbyen, Syalbard, Norway, (1997).
[23]	G. Gong and A. Youssef, Cryptographic properties of the Welch-Gong transformation sequence generators, IEEE Trans. Inf. Theory, 48 (2002), 2837-2846. doi: 10.1109/TIT.2002.804043.
[24]	B. Gordon, W. H. Mills and L. R. Welch, Some new difference sets, Canadian Journal of Mathematics, 14 (1962), 614-625. doi: 10.4153/CJM-1962-052-2.
[25]	M. Joseph, G. Sekar and R. Balasubramanian, Distinguishing attacks on (ultra-)lightweight WG ciphers, in 5th International Workshop on Lightweight Cryptography for Security and Privacy, LightSec 2016, Springer International Publishing, (2017), 45–59. doi: 10.1007/978-3-319-55714-4_4.
[26]	K. Mandal and G. Gong, Cryptographically strong de Bruijn sequences with large periods., in Selected Areas in Cryptography, SAC 2012, Lecture Notes in Comput. Sci., Springer, Heidelberg, 7707 (2012), 104–118.
[27]	K. Mandal and G. Gong, Feedback reconstruction and implementations of pseudorandom number generators from composited de Bruijn sequences, IEEE Trans. Computers, 65 (2016), 2725-2738. doi: 10.1109/TC.2015.2506557.
[28]	K. Mandal, G. Gong, X. Fan and M. Aagaard, Optimal parameters for the WG stream cipher family, Cryptography and Communications, 6 (2014), 117-135.
[29]	K. Mandal, B. Yang, G. Gong and M. Aagaard, On ideal $t$-tuple distribution of filtering de Bruijn sequence generators, Cryptography and Communications, 10 (2018), 629-641. doi: 10.1007/s12095-017-0248-3.
[30]	J. L. Massey, Shift-register synthesis and BCH decoding, IEEE Trans. Inform. Theory, 15 (1969), 122-127. doi: 10.1109/tit.1969.1054260.
[31]	Y. Nawaz and G. Gong, WG: A family of stream ciphers with designed randomness properties, Information Sciences, 178 (2008), 1903-1916. doi: 10.1016/j.ins.2007.12.002.
[32]	Y. Nawaz and G. Gong, The WG stream cipher, (2005). Available from: http://www.ecrypt.eu.org/stream/p2ciphers/wg/wg_p2.pdf.,
[33]	J.-S. No, S. W. Golomb, G. Gong, H. K. Lee and P. Gaal, Binary pseudorandom sequences of period $2^n-1$ with ideal autocorrelation, IEEE Trans. Inform. Theory, 44 (1998), 814-817. doi: 10.1109/18.661528.
[34]	M. A. Orumiehchiha, J. Pieprzyk and R. Steinfeld, Cryptanalysis of WG-7: A lightweight stream cipher, Cryptography Communications, 4 (2012), 277-285. doi: 10.1007/s12095-012-0070-x.
[35]	H. El-Razouk, A. Reyhani-Masoleh and G. Gong, New implementations of the WG stream cipher, IEEE Trans. on VLSI, 22 (2014), 1865-1878. doi: 10.1109/TVLSI.2013.2280092.
[36]	S. RØnjom, Improving algebraic attacks on stream ciphers based on linear feedback shift register over $\mathbb{F}_{2^k}$, Designs Codes Cryptography, 82 (2017), 27-41. doi: 10.1007/s10623-016-0212-9.
[37]	R. A. Rueppel, Analysis and Design of Stream Ciphers, Springer-Verlag, 1986. doi: 10.1007/978-3-642-82865-2.
[38]	T. Siegenthaler, R. Forré and A. W. Kleiner, Generation of binary sequences with controllable complexity and ideal $r$-tupel distribution, in Advances in Cryptology–EUROCRYPT 87, Lecture Notes in Comput. Sci, 304 (1987), 15–23. doi: 10.1007/3-540-39118-5_3.
[39]	N. Y. Yu and G. Gong, Crosscorrelation properties of binary sequences with ideal two-level autocorrelation, in Proceedings of the 4th International Conference on Sequences and Their Applications (SETA'06), Lecture Notes in Comput. Sci, Springer, Berlin, Heidelberg, 4086 (2006), 104–118. doi: 10.1007/11863854_9.
[40]	N. Y. Yu and G. Gong, A new binary sequence family with low correlation and large size, IEEE Trans. Inf. Theory, 52 (2006), 1624-1636. doi: 10.1109/TIT.2006.871062.
[41]	S. V. Smyshlyaev, Perfectly balanced Boolean functions and Golić conjecture, Journal of Cryptology, 25 (2012), 464-483. doi: 10.1007/s00145-011-9100-7.
[42]	G. Yang, X. Fan, M. Aagaard and G. Gong, Design space exploration of the lightweight stream cipher WG-8 for FPGAs and ASICs, Proceedings of the Workshop on Embedded Systems Security, (2013), 1–10. doi: 10.1145/2527317.2527325.
[43]	B. Yang, K. Mandal, M. D. Aagaard and G. Gong, Efficient composited de Bruijn sequence generators, IEEE Trans. on Computers, 66 (2017), 1354-1368. doi: 10.1109/TC.2017.2676763.