New construction of highly nonlinear resilient S-boxes via linear codes

Haixia Zhao^1,2 &
Yongzhuang Wei³

53 Accesses
2 Citations
1 Altmetric
Explore all metrics

Abstract

Highly nonlinear resilient functions play a crucial role in nonlinear combiners which are usual hardware oriented stream ciphers. During the past three decades, the main idea of construction of highly nonlinear resilient functions are benefited from concatenating a large number of affine subfunctions. However, these resilient functions as core component of ciphers usually suffered from the guess and determine attack or algebraic attack since the n-variable nonlinear Boolean functions can be easily given rise to partial linear relations by fixing at most n/2 variables of them. How to design highly nonlinear resilient functions (S-boxes) without concatenating a large number of n/2 variables affine subfunctions appears to be an important task. In this article, a new construction of highly nonlinear resilient functions is proposed. These functions consist of two classes subfunctions. More specially, the first class (nonlinear part) contains both the bent functions with 2k variables and some affine subfunctions with n/2 — k variables which are attained by using [n/2 — k, m, d] disjoint linear codes. The second class (linear part) includes some linear subfunctions with n/2 variables which are attained by using [n/2, m, d] disjoint linear codes. It is illustrated that these resilient functions have high nonlinearity and high algebraic degree. In particular, It is different from previous well-known resilient S-boxes, these new S-boxes cannot be directly decomposed into some affine subfunctions with n/2 variables by fixing at most n/2 variables. It means that the S-boxes (vectorial Boolean functions) which use these resilient functions as component functions have more favourable cryptography properties against the guess and determine attack or algebraic attacks.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic

$34.99 /Month

Get 10 units per month
Download Article/Chapter or eBook
1 Unit = 1 Article or 1 Chapter
Cancel anytime

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

On the nonlinearity of S-boxes and linear codes

Article 13 January 2016

Constructing S-boxes for Lightweight Cryptography with Feistel Structure

On the Relationship Between Resilient Boolean Functions and Linear Branch Number of S-Boxes

References

Menezes A J, Vanstone S A, Van Oorschot P C. Handbook of Applied Cryptography. 1st ed. Cleveland: CRC Press, 1997
MATH Google Scholar
Ding C S, Shan W J, Xiao G Z. The stability theory of stream ciphers. Lecture Notes in Computer Science, 1991, 561: 13–28
Article MathSciNet MATH Google Scholar
Siegenthaler T. Correlation-immunity of nonlinear combining functions for cryptographic applications (Corresp.). IEEE Transactions on Information Theory, 2003, 30(5): 776–780
Article MathSciNet MATH Google Scholar
Courtois N. Fast algebraic attacks on stream ciphers with linear feedback. In: Proceedings of Advances in Cryptology — EUROCRYPT 2003: International Conference on the Theory and Applications of Cryptographic Techniques. 2003: 176–194
Zhou Y, Hu Y P, Dong X F. The Design and Analysis of Boolean Function. 1st ed. Beijin: National Defense Industry Press, 2015
Google Scholar
Camion P, Carlet C, Charpin P, Sendrier N. On correlation-immune functions. In: Proceedings of International Cryptology Conference on Advances in Cryptology. 1991: 86–100
Carlet C. A larger class of cryptographic boolean functions via a study of the Maiorana-McFarland construction. In: Proceedings of International Cryptology Conference on Advances in Cryptology. 2002: 549–564
Pasalic E. Maiorana-McFarland class: degree optimization and algebraic properties. IEEE Transactions on Information Theory, 2006, 52(10): 4581–1594
Article MathSciNet MATH Google Scholar
Pasalic E, Maitra S. Linear codes in generalized construction of resilient functions with very high nonlinearity. IEEE Transactions on Information Theory, 2002, 48(8): 2182–2191
Article MathSciNet MATH Google Scholar
Johansson T, Pasalic E. A construction of resilient functions with high nonlinearity. IEEE Transactions on Information Theory, 2003, 49(2): 494–501
Article MathSciNet MATH Google Scholar
Zhang W G, Pasalic E. Constructions of resilient S-boxes with strictly almost optimal nonlinearity through disjoint linear codes. IEEE Transactions on Information Theory, 2014, 60(3): 1638–1651
Article MathSciNet MATH Google Scholar
Zhang W G, Xiao G Z. Constructions of almost optimal resilient Boolean functions on large even number of variables. IEEE Transactions on Information Theory, 2009, 55(12): 5822–5831
Article MathSciNet MATH Google Scholar
Zhang W G, Pasalic E. Generalized Maiorana-McFarland construction of resilient Boolean functions with high nonlinearity and good algebraic properties. IEEE Transactions on Information Theory, 2014, 60(10): 6681–6695
Article MathSciNet MATH Google Scholar
Khoo K, Chew G, Gong G, Lee H K. Time-memory-data trade-off attack on stream ciphers based on Maiorana-McFarland functions. IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences, 2009, 92(1): 11–21
Article Google Scholar
Mihaljevic M, Gangopadhyay S, Paul G, Imaiand H. Internal state recovery of Grain-v1 employing normality order of the filter function. Information Security Iet, 2012, 6(2): 55–64
Article Google Scholar
Pasalic E. On guess and determine cryptanalysis of LFSR-based stream ciphers. IEEE Transactions on Information Theory, 2009, 55(7): 3398–3406
Article MathSciNet MATH Google Scholar
Boura C, Canteaut A. A new criterion for avoiding the propagation of linear relations through an S-box. In: Proceedings of International Workshop on Fast Software Encryption. 2013: 585–604
Wei Y Z, Pasalic E, Zhang F R. New constructions of resilient functions with strictly almost optimal nonlinearity via non-overlap spectra functions. Information Sciences, 2017, 415: 377–396
Article MATH Google Scholar
Cusick T W, Stanica P. Cryptographic Boolean Functions and Applications. 1st ed. San Diego: Elsevier, 2009
MATH Google Scholar
Xiao G Z, Massey J L. A spectral characterization of correlation immune combining functions. IEEE Transactions on Information Theory, 1988, 34(3): 569–571
Article MathSciNet MATH Google Scholar
Wen Q Y, Niu X X, Yang Y X. Boolean Functions in Modern Cryptography. 1st ed. Beijing: Science Press, 2000
Google Scholar
Zhang X M, Zheng Y L. Cryptographically resilient functions. IEEE Transactions on Information Theory, 1997, 43(5): 1740–1747
Article MathSciNet MATH Google Scholar
Wang X M, Xiao G Z. Error Correcting Code — Principle and Method. 1st ed. Xian: Xidian University Press, 2003
Google Scholar
Fu S J, Li C, Qu L J. A recursive construction of highly nonlinear resilient vectorial functions. Information Science, 2014, 269: 388–396
Article MathSciNet MATH Google Scholar

Download references

Acknowledgements

The work was supported in part by the National Natural Science Foundation of China (Grant No. 61872103), in part by Guangxi Science and Technology Foundation (Guike AB18281019, Guike AD1828 1026), in part by Guangxi Natural Science Foundation (2019GXNSFGA 245004), in part by the Foundation of Ministry of Education Key Laboratory of Cognitive Radio and Information Processing (Guilin University of Electronic Technology)(CRKL180107).

Author information

Authors and Affiliations

Ministry of Education Key Laboratory of Cognitive Radio and Information Processing, Guilin University of Electronic Technology, Guilin, 541004, China
Haixia Zhao
School of Mathematics and Computing Science, Guilin University of Electronic Technology, Guilin, 541004, China
Haixia Zhao
Guangxi Key Laboratory of Cryptography and Information Security, Guilin University of Electronic Technology, Guilin, 541004, China
Yongzhuang Wei

Authors

Haixia Zhao
View author publications
You can also search for this author in PubMed Google Scholar
Yongzhuang Wei
View author publications
You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yongzhuang Wei.

Additional information

Haixia Zhao is a doctoral student. She received the BS and MS from Southwest University, China in 2002 and 2007 respectively. In 2002, she joined Guilin University of Electronic Technology, China. Her research interests include cryptographic functions and cryptanalysis of block ciphers.

Yongzhuang Wei is a professor. He received the MS and PhD from Xidian University, China in 2004 and 2009, respectively. In 2004, he joined Guilin University of Electronic Technology, China. His research interests include the design and analysis of symmetric encryption algorithms.

Electronic supplementary material