{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,2,3]],"date-time":"2024-02-03T08:02:08Z","timestamp":1706947328741},"reference-count":43,"publisher":"American Institute of Mathematical Sciences (AIMS)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["AMC"],"published-print":{"date-parts":[[2022]]},"abstract":"<p style='text-indent:20px;'>Uniformity in binary tuples of various lengths in a pseudorandom sequence is an important randomness property. We consider ideal <inline-formula><tex-math id=\"M1\">\\begin{document}$ t $\\end{document}<\/tex-math><\/inline-formula>-tuple distribution of a filtering de Bruijn generator consisting of a de Bruijn sequence of period <inline-formula><tex-math id=\"M2\">\\begin{document}$ 2^n $\\end{document}<\/tex-math><\/inline-formula> and a filtering function in <inline-formula><tex-math id=\"M3\">\\begin{document}$ m $\\end{document}<\/tex-math><\/inline-formula> 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 <i>invariant under the WG transform<\/i>, of Boolean functions. We have found that there are only two classes of orthogonal functions whose WG transformations preserve <inline-formula><tex-math id=\"M4\">\\begin{document}$ t $\\end{document}<\/tex-math><\/inline-formula>-tuple uniformity in output sequences, up to <inline-formula><tex-math id=\"M5\">\\begin{document}$ t = (n-m+1) $\\end{document}<\/tex-math><\/inline-formula>. The conjecture of Mandal <i>et al.<\/i> in [<xref ref-type=\"bibr\" rid=\"b29\">29<\/xref>] about the ideal tuple distribution on the WG transformation is proved. It is also shown that the Gold functions and quadratic functions can guarantee <inline-formula><tex-math id=\"M6\">\\begin{document}$ (n-m+1) $\\end{document}<\/tex-math><\/inline-formula>-tuple distributions. A connection between the ideal tuple distribution and the invariance under WG transform property is established.<\/p><\/jats:p>","DOI":"10.3934\/amc.2020125","type":"journal-article","created":{"date-parts":[[2020,12,18]],"date-time":"2020-12-18T01:59:51Z","timestamp":1608256791000},"page":"597","source":"Crossref","is-referenced-by-count":1,"title":["On ideal $ t $-tuple distribution of orthogonal functions in filtering de bruijn generators"],"prefix":"10.3934","volume":"16","author":[{"given":"Kalikinkar","family":"Mandal","sequence":"first","affiliation":[{"name":"Department of Electrical and Computer Engineering, University of Waterloo, Waterloo, Ontario, N2L 3G1, CANADA"}]},{"given":"Guang","family":"Gong","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering, University of Waterloo, Waterloo, Ontario, N2L 3G1, CANADA"}]}],"member":"2321","reference":[{"key":"key-10.3934\/amc.2020125-1","doi-asserted-by":"publisher","unstructured":"S. Arora, B. Barak., Computational Complexity: A Modern Approach<\/i>, ${ref.volume}<\/b> (2009).","DOI":"10.1017\/CBO9780511804090"},{"key":"key-10.3934\/amc.2020125-2","doi-asserted-by":"publisher","unstructured":"S. Boztas, P.V. Kumar.Binary sequences with Gold-like correlation but larger linear span, IEEE Trans. Inf. Theory<\/i>, 40<\/b> (1994), 532-537.","DOI":"10.1109\/18.312181"},{"key":"key-10.3934\/amc.2020125-3","unstructured":"N. G. de Bruijn.A combinatorial problem, Proc. Koninklijke Nederlandse Akademie v. Wetenschappen<\/i>, 49<\/b> (1946), 758-764."},{"key":"key-10.3934\/amc.2020125-4","unstructured":"A. Canteaut, Analysis and Design of Symmetric Ciphers<\/i>, Habilitation for directing Theses, University of Paris 6, 2006. Available from: https:\/\/www.rocq.inria.fr\/secret\/Anne.Canteaut\/canteaut-hdr.pdf<\/a>."},{"key":"key-10.3934\/amc.2020125-5","doi-asserted-by":"crossref","unstructured":"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\u2013397.","DOI":"10.1017\/CBO9780511780448.011"},{"key":"key-10.3934\/amc.2020125-6","doi-asserted-by":"publisher","unstructured":"A. H. Chan, R. A. Games, E. L. Key.On the complexities of de Bruijn sequences, Journal of Combinatorial Theory, Series A<\/i>, 33<\/b> (1982), 233-246.","DOI":"10.1016\/0097-3165(82)90038-3"},{"key":"key-10.3934\/amc.2020125-7","doi-asserted-by":"publisher","unstructured":"A. Chang, P. Gaal, S. W. Golomb, G. Gong, T. Helleseth, P. V. Kumar.On a conjectured ideal autocorrelation sequence and a related triple-error correcting cyclic code, IEEE Trans. Inf. Theory<\/i>, 46<\/b> (2000), 680-687.","DOI":"10.1109\/18.825842"},{"key":"key-10.3934\/amc.2020125-8","doi-asserted-by":"crossref","unstructured":"T. W. Cusick, P. St\u0103nic\u0103., Cryptographic Boolean Functions and Applications<\/i>, ${ref.volume}<\/b> (2009).","DOI":"10.1016\/B978-0-12-374890-4.00009-4"},{"key":"key-10.3934\/amc.2020125-9","unstructured":"National Institute of Standards and Technology, Digital Signature Standard (DSS)<\/i>, Federal information processing standards publication, FIPS PUB 186-2, Reaffirmed, 2000.,"},{"key":"key-10.3934\/amc.2020125-10","doi-asserted-by":"publisher","unstructured":"J. F. Dillon.Multiplicative difference sets via additive characters, Designs, Codes and Cryptography<\/i>, 17<\/b> (1999), 225-235.","DOI":"10.1023\/A:1026435428030"},{"key":"key-10.3934\/amc.2020125-11","doi-asserted-by":"publisher","unstructured":"J. F. Dillon, H. Dobbertin.New cyclic difference sets with singer parameters, Finite Fields and Their Applications<\/i>, 10<\/b> (2004), 342-389.","DOI":"10.1016\/j.ffa.2003.09.003"},{"key":"key-10.3934\/amc.2020125-12","doi-asserted-by":"publisher","unstructured":"L. Ding, C. Jin, J. Guan, Q. Wang.Cryptanalysis of lightweight WG-8 stream cipher, IEEE Trans. Inf. Forensics and Security<\/i>, 9<\/b> (2014), 645-652.","DOI":"10.1109\/TIFS.2014.2307202"},{"key":"key-10.3934\/amc.2020125-13","doi-asserted-by":"publisher","unstructured":"L. Ding, C. Jin, J. Guan, S. Zhang, T. Cui, D. Han, W. Zhao.Cryptanalysis of WG family of stream ciphers, Computer Journal<\/i>, 58<\/b> (2015), 2677-2685.","DOI":"10.1093\/comjnl\/bxv024"},{"key":"key-10.3934\/amc.2020125-14","unstructured":"The eStream project, (2008). Available from: http:\/\/www.ecrypt.eu.org\/stream\/project.html<\/a>."},{"key":"key-10.3934\/amc.2020125-15","doi-asserted-by":"publisher","unstructured":"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<\/i>, Springer Berlin, (2013), 617\u2013632.","DOI":"10.1007\/978-3-642-37949-9_54"},{"key":"key-10.3934\/amc.2020125-16","doi-asserted-by":"publisher","unstructured":"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)<\/i>, ACM Press, (2013), 21\u201334.","DOI":"10.1145\/2517300.2517305"},{"key":"key-10.3934\/amc.2020125-17","doi-asserted-by":"publisher","unstructured":"R. Gold.Maximal recursive sequences with 3-valued recursive cross-correlation functions, IEEE Trans. Inf. Theory<\/i>, 14<\/b> (1968), 154-156.","DOI":"10.1109\/TIT.1968.1054106"},{"key":"key-10.3934\/amc.2020125-18","doi-asserted-by":"crossref","unstructured":"J. Dj Goli\u0107, On the security of nonlinear filter generators, in 1996 Proceedings of Fast Software Encryption<\/i>, Springer, Berlin, Heidelberg, (1996), 173\u2013188.","DOI":"10.1007\/3-540-60865-6_52"},{"key":"key-10.3934\/amc.2020125-19","doi-asserted-by":"publisher","unstructured":"S. W. Golomb.On the classification of balanced binary sequences of period $2^n-1$, IEEE Trans. Inf. Theory<\/i>, 26<\/b> (1980), 730-732.","DOI":"10.1109\/TIT.1980.1056265"},{"key":"key-10.3934\/amc.2020125-20","unstructured":"S. W. Golomb, Shift register sequences, Aegean Park Press, Laguna Hills, CA, (1981)."},{"key":"key-10.3934\/amc.2020125-21","doi-asserted-by":"publisher","unstructured":"S. W. Golomb, G. Gong., Signal Design for Good Correlation: For wireless Communication, Cryptography and Radar<\/i>, ${ref.volume}<\/b> (2005).","DOI":"10.1017\/CBO9780511546907"},{"key":"key-10.3934\/amc.2020125-22","unstructured":"G. Gong, P. Gaal and S. W. Golomb, A suspected infinity class of cyclic Hadamard difference sets, Proceedings of 1997 IEEE Information Theory Workshop<\/i>, Longyearbyen, Syalbard, Norway, (1997)."},{"key":"key-10.3934\/amc.2020125-23","doi-asserted-by":"publisher","unstructured":"G. Gong, A. Youssef.Cryptographic properties of the Welch-Gong transformation sequence generators, IEEE Trans. Inf. Theory<\/i>, 48<\/b> (2002), 2837-2846.","DOI":"10.1109\/TIT.2002.804043"},{"key":"key-10.3934\/amc.2020125-24","doi-asserted-by":"publisher","unstructured":"B. Gordon, W. H. Mills, L. R. Welch.Some new difference sets, Canadian Journal of Mathematics<\/i>, 14<\/b> (1962), 614-625.","DOI":"10.4153\/CJM-1962-052-2"},{"key":"key-10.3934\/amc.2020125-25","doi-asserted-by":"publisher","unstructured":"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<\/i>, Springer International Publishing, (2017), 45\u201359.","DOI":"10.1007\/978-3-319-55714-4_4"},{"key":"key-10.3934\/amc.2020125-26","doi-asserted-by":"crossref","unstructured":"K. Mandal and G. Gong, Cryptographically strong de Bruijn sequences with large periods., in Selected Areas in Cryptography, SAC 2012<\/i>, Lecture Notes in Comput. Sci., Springer, Heidelberg, 7707<\/b> (2012), 104\u2013118.","DOI":"10.1007\/978-3-642-35999-6_8"},{"key":"key-10.3934\/amc.2020125-27","doi-asserted-by":"publisher","unstructured":"K. Mandal, G. Gong.Feedback reconstruction and implementations of pseudorandom number generators from composited de Bruijn sequences, IEEE Trans. Computers<\/i>, 65<\/b> (2016), 2725-2738.","DOI":"10.1109\/TC.2015.2506557"},{"key":"key-10.3934\/amc.2020125-28","doi-asserted-by":"crossref","unstructured":"K. Mandal, G. Gong, X. Fan, M. Aagaard.Optimal parameters for the WG stream cipher family, Cryptography and Communications<\/i>, 6<\/b> (2014), 117-135.","DOI":"10.1007\/s12095-013-0091-0"},{"key":"key-10.3934\/amc.2020125-29","doi-asserted-by":"publisher","unstructured":"K. Mandal, B. Yang, G. Gong, M. Aagaard.On ideal $t$-tuple distribution of filtering de Bruijn sequence generators, Cryptography and Communications<\/i>, 10<\/b> (2018), 629-641.","DOI":"10.1007\/s12095-017-0248-3"},{"key":"key-10.3934\/amc.2020125-30","doi-asserted-by":"publisher","unstructured":"J. L. Massey.Shift-register synthesis and BCH decoding, IEEE Trans. Inform. Theory<\/i>, 15<\/b> (1969), 122-127.","DOI":"10.1109\/tit.1969.1054260"},{"key":"key-10.3934\/amc.2020125-31","doi-asserted-by":"publisher","unstructured":"Y. Nawaz, G. Gong.WG: A family of stream ciphers with designed randomness properties, Information Sciences<\/i>, 178<\/b> (2008), 1903-1916.","DOI":"10.1016\/j.ins.2007.12.002"},{"key":"key-10.3934\/amc.2020125-32","unstructured":"Y. Nawaz and G. Gong, The WG stream cipher, (2005). Available from: http:\/\/www.ecrypt.eu.org\/stream\/p2ciphers\/wg\/wg_p2.pdf<\/a>.,"},{"key":"key-10.3934\/amc.2020125-33","doi-asserted-by":"publisher","unstructured":"J.-S. No, S. W. Golomb, G. Gong, H. K. Lee, P. Gaal.Binary pseudorandom sequences of period $2^n-1$ with ideal autocorrelation, IEEE Trans. Inform. Theory<\/i>, 44<\/b> (1998), 814-817.","DOI":"10.1109\/18.661528"},{"key":"key-10.3934\/amc.2020125-34","doi-asserted-by":"publisher","unstructured":"M. A. Orumiehchiha, J. Pieprzyk, R. Steinfeld.Cryptanalysis of WG-7: A lightweight stream cipher, Cryptography Communications<\/i>, 4<\/b> (2012), 277-285.","DOI":"10.1007\/s12095-012-0070-x"},{"key":"key-10.3934\/amc.2020125-35","doi-asserted-by":"publisher","unstructured":"H. El-Razouk, A. Reyhani-Masoleh, G. Gong.New implementations of the WG stream cipher, IEEE Trans. on VLSI<\/i>, 22<\/b> (2014), 1865-1878.","DOI":"10.1109\/TVLSI.2013.2280092"},{"key":"key-10.3934\/amc.2020125-36","doi-asserted-by":"publisher","unstructured":"S. R\u00d8njom.Improving algebraic attacks on stream ciphers based on linear feedback shift register over $\\mathbb{F}_{2^k}$, Designs Codes Cryptography<\/i>, 82<\/b> (2017), 27-41.","DOI":"10.1007\/s10623-016-0212-9"},{"key":"key-10.3934\/amc.2020125-37","doi-asserted-by":"publisher","unstructured":"R. A. Rueppel, Analysis and Design of Stream Ciphers<\/i>, Springer-Verlag, 1986.","DOI":"10.1007\/978-3-642-82865-2"},{"key":"key-10.3934\/amc.2020125-38","doi-asserted-by":"publisher","unstructured":"T. Siegenthaler, R. Forr\u00e9 and A. W. Kleiner, Generation of binary sequences with controllable complexity and ideal $r$-tupel distribution, in Advances in Cryptology\u2013EUROCRYPT 87<\/i>, Lecture Notes in Comput. Sci, 304<\/b> (1987), 15\u201323.","DOI":"10.1007\/3-540-39118-5_3"},{"key":"key-10.3934\/amc.2020125-39","doi-asserted-by":"publisher","unstructured":"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)<\/i>, Lecture Notes in Comput. Sci, Springer, Berlin, Heidelberg, 4086<\/b> (2006), 104\u2013118.","DOI":"10.1007\/11863854_9"},{"key":"key-10.3934\/amc.2020125-40","doi-asserted-by":"publisher","unstructured":"N. Y. Yu, G. Gong.A new binary sequence family with low correlation and large size, IEEE Trans. Inf. Theory<\/i>, 52<\/b> (2006), 1624-1636.","DOI":"10.1109\/TIT.2006.871062"},{"key":"key-10.3934\/amc.2020125-41","doi-asserted-by":"publisher","unstructured":"S. V. Smyshlyaev.Perfectly balanced Boolean functions and Goli\u0107 conjecture, Journal of Cryptology<\/i>, 25<\/b> (2012), 464-483.","DOI":"10.1007\/s00145-011-9100-7"},{"key":"key-10.3934\/amc.2020125-42","doi-asserted-by":"publisher","unstructured":"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<\/i>, (2013), 1\u201310.","DOI":"10.1145\/2527317.2527325"},{"key":"key-10.3934\/amc.2020125-43","doi-asserted-by":"publisher","unstructured":"B. Yang, K. Mandal, M. D. Aagaard, G. Gong.Efficient composited de Bruijn sequence generators, IEEE Trans. on Computers<\/i>, 66<\/b> (2017), 1354-1368.","DOI":"10.1109\/TC.2017.2676763"}],"container-title":["Advances in Mathematics of Communications"],"original-title":[],"link":[{"URL":"http:\/\/aimsciences.org\/\/article\/doi\/10.3934\/amc.2020125?viewType=html","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,29]],"date-time":"2022-06-29T09:25:51Z","timestamp":1656494751000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.aimsciences.org\/article\/doi\/10.3934\/amc.2020125"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"references-count":43,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022]]}},"alternative-id":["1930-5346_2022_3_597"],"URL":"https:\/\/doi.org\/10.3934\/amc.2020125","relation":{},"ISSN":["1930-5346","1930-5338"],"issn-type":[{"value":"1930-5346","type":"print"},{"value":"1930-5338","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022]]}}}