Nonlinear complication functions for symmetric stream ciphers
DOI:
https://doi.org/10.30837/rt.2018.4.195.12Keywords:
pseudo-random sequence generators, de Brain sequence, cryptographic analysis, Boolean functions, nonlinear complication functionsAbstract
Currently, nonlinear Boolean functions are being investigated very actively around the world. However, many open questions remain in this area. The theory of nonlinear Boolean functions suitable for use in robust cryptographic algorithms is largely incomplete. Despite the presence of numerous publications on these topics, many issues related to the interrelation of design characteristics affecting the performance of the generator and its cryptographic characteristics are still open. The generation of a special type of sequences, called de Brain sequences, with minimal hardware and software costs, the rationale for their use as non-linear functions of the complexity of stream encryption systems, is the main theme of this work. The paper presents estimates of cryptographic indicators of nonlinear complexity functions of iterative bit sequence generators with various characteristics of the generated sequence, such as linear complexity and autocorrelation.References
Marcus Schafheutle. A First Report on the Stream Cipher SNOW. http://www.cryptonessie.org
C. Berbain, O. Billet, A. Canteaut, N. Courtois, B. Debraize, H. Gilbert, L. Goubin, A. Gouget, L. Granboulan, C. Lauradoux, M. Minier, T. Pornin, and H. Sibert. Decim – A new Stream Cipher for Hardware applications. In ECRYPT Stream Cipher Project Report 2005/004. Available at http://www.ecrypt.eu.org/stream/
S. Kiyomoto, T. Tanaka, and K. Sakurai, “A word-oriented stream cipher using clock control,” Workshop Recod of SASC 2007, pp.260–274, January 2007 [Електронний ресурс]. – Режим доступу: https://www.cosic.esat.kuleuven.be/ecrypt/stream/papersdir/2007/029.pdf
The eSTREAM Project – eSTREAM Phase 3. SOSEMANUK (Portfolio Profile 1). [Електронний ресурс]. – Режим доступу: http://www.ecrypt.eu.org/ stream /sosemanukpf.html
The eSTREAM Project – eSTREAM Phase 3. Grain (Portfolio Profile 2). [Електронний ресурс]. – Режим доступу: http://www.ecrypt.eu.org/stream/ grainpf.html
The eSTREAM Project – eSTREAM Phase 3. MICKEY (Portfolio Profile 2). [Електронний ресурс]. – Режим доступу: http://www.ecrypt.eu.org/stream/ mickeypf.html
The eSTREAM Project – eSTREAM Phase 3. Trivium (Portfolio Profile 2). [Електронний ресурс]. – Режим доступу: http://www.ecrypt.eu.org/stream/triviumpf.html
Dabrowski P., Łabuzek G., Rachwalik T., Szmidt J. Searching for Nonlinear Feedback Shift Registers with Parallel Computing. [Електронний ресурс]. 2013 URL: https://eprint.iacr.org/2013/542.pdf (дата звернення: 07.10.2016).
Fredricksen H. A survey of full length nonlinear shift register cycle algorithms,” SIAM Review. 1982, vol. 24, № 2. Р. 195–221.
Jansen C.J. Investigations On Nonlinear Streamcipher Systems: Construction and Evaluation Methods. Ph.D. Thesis, Technical University of Delft. 1989.
Jansen C.J. The maximum order complexity of sequence ensembles. Lecture Notes in Computer Science, Adv. Cryptology-Eupocrypt’1991, Berlin, Germany. 1991, vol. 547, Р. 153–159.
Linardatos D., Kalouptsidis N. Synthesis of minimal cost nonlinear feedback shift registers // Signal Process. –2002. – Vol. 82, № 2. – Р. 157–176.
Rizomiliotis P., Kalouptsidis N. Results on the nonlinear span of binary sequences // IEEE Transactions on Information Theory. – 2005. – Vol. 51, № 4. – Р. 1555–5634.
Limniotis K., Kolokotronis N., Kalouptsidis N. On the nonlinear complexity and Lempel-Ziv complexity of finite length sequences // IEEE Transactions on Information Theory. – 2007. – vol. 53, № 11. – Р. 4293–4302.
E. Dubrova, A scalable method for constructing Galois NLFSRs with period 2n-1 using cross-join pairs // IEEE Transactions on Information Theory. – 2013. – vol. 59(1). – Р. 703-709.
Mykkeltveit J., Siu M-K., Tong P. On the cyclic structure of some nonlinear shift register sequences // Inform. and Control. – 1979. – vol. 43. – Р. 202-215.
Carlet C. Boolean functions for cryptography and error correcting codes // In: Crama Y., Hammer P. L. (Eds.), Boolean Methods and Models, Cambridge University Press, http://www-rocq.inria.fr/secret/Claude.Carlet/ chap-fcts-Bool.pdf
Knuth, D. The Art of Computer Programming. Vol. II. Seminumerical Algorithms. – USA, Commonwealth of Massachusetts: Addison-Wesley, 1969. – Р.634.
Flye-Sainte Marie С. Solution to question number 48 // l'Intermediaire des Mathematiciens. –1894. – V. 1. – P. 107-110.
de Bruijn N.G. A combitorial problem // Nederl. Akad. Wetensch. Proc. –1946. – V. 49. – P. 758-764.
H. Fredricksen. A survey of full length nonlinear shift register cycle algorithm // SIAM Review, 24(2):195–221, 1982.
Mayhew G.L., Golomb S.W. Characterizations of generators for modified de Bruijn sequences. Advances in applied mathematics 13(4), 454-461 (1992) https://www.sciencedirect.com/ sci-ence/article/pii/019688589290021N
Berlekamp E. R. Algebraic Coding Theory. McGraw-Hill, NY, 1968. – Р.474.
McWilliams F.J. Sloane N.J. The Theory of Error-Correcting Codes // North-Holland, 1978. – Р. 762.
Mayhew G.L., Golomb S.W. Linear spans of modified de Bruijn sequences // IEEE Trans. Inform. Theory. – 1990. – № 36(5). – Р. 1166–1167.
Downloads
Published
How to Cite
Issue
Section
License
Authors who publish with this journal agree to the following terms:
1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
