Please wait a minute...
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

Front. Comput. Sci.    2022, Vol. 16 Issue (3) : 163805    https://doi.org/10.1007/s11704-020-0182-y
RESEARCH ARTICLE
New construction of highly nonlinear resilient S-boxes via linear codes
Haixia ZHAO1,2, Yongzhuang WEI3()
1. Ministry of Education Key Laboratory of Cognitive Radio and Information Processing, Guilin University of Electronic Technology, Guilin 541004, China
2. School of Mathematics and Computing Science, Guilin University of Electronic Technology, Guilin 541004, China
3. Guangxi Key Laboratory of Cryptography and Information Security, Guilin University of Electronic Technology, Guilin 541004, China
 Download: PDF(852 KB)   HTML
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
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 2 k 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.

Keywords stream cipher      S-box      disjoint linear codes      resiliency      nonlinearity     
Corresponding Author(s): Yongzhuang WEI   
Just Accepted Date: 25 August 2020   Online First Date: 26 February 2021    Issue Date: 18 September 2021
 Cite this article:   
Haixia ZHAO,Yongzhuang WEI. New construction of highly nonlinear resilient S-boxes via linear codes[J]. Front. Comput. Sci., 2022, 16(3): 163805.
 URL:  
https://academic.hep.com.cn/fcs/EN/10.1007/s11704-020-0182-y
https://academic.hep.com.cn/fcs/EN/Y2022/V16/I3/163805
1 A J Menezes , S A Vanstone , P C Van Oorschot . Handbook of Applied Cryptography. 1st ed. Cleveland: CRC Press, 1997,
2 C S Ding , W J Shan , G Z Xiao . The stability theory of stream ciphers. Lecture Notes in Computer Science, 1991, 561 : 13– 28
3 T Siegenthaler . Correlation-immunity of nonlinear combining functions for cryptographic applications (Corresp.). IEEE Transactions on Information Theory, 2003, 30( 5): 776– 780
https://doi.org/10.1109/TIT.1984.1056949
4 N Courtois . 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
5 Y Zhou , Y P Hu , X F Dong . The Design and Analysis of Boolean Function. 1st ed. Beijin: National Defense Industry Press, 2015,
6 P Camion , C Carlet , P Charpin , N Sendrier . On correlation-immune functions. In: Proceedings of International Cryptology Conference on Advances in Cryptology, 1991, 86– 100
7 C Carlet . 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
8 E Pasalic . Maiorana-McFarland class: degree optimization and algebraic properties. IEEE Transactions on Information Theory, 2006, 52( 10): 4581– 4594
https://doi.org/10.1109/TIT.2006.881721
9 E Pasalic , S Maitra . Linear codes in generalized construction of resilient functions with very high nonlinearity. IEEE Transactions on Information Theory, 2002, 48( 8): 2182– 2191
https://doi.org/10.1109/TIR.2002.800492
10 T Johansson , E Pasalic . A construction of resilient functions with high nonlinearity. IEEE Transactions on Information Theory, 2003, 49( 2): 494– 501
https://doi.org/10.1109/TIT.2002.807297
11 W G Zhang , E Pasalic . Constructions of resilient S-boxes with strictly almost optimal nonlinearity through disjoint linear codes. IEEE Transactions on Information Theory, 2014, 60( 3): 1638– 1651
https://doi.org/10.1109/TIT.2014.2300067
12 W G Zhang , G Z Xiao . Constructions of almost optimal resilient Boolean functions on large even number of variables. IEEE Transactions on Information Theory, 2009, 55( 12): 5822– 5831
https://doi.org/10.1109/TIT.2009.2032736
13 W G Zhang , E Pasalic . 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
https://doi.org/10.1109/TIT.2014.2345772
14 K Khoo , G Chew , G Gong , H K Lee . 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
15 M Mihaljevic , S Gangopadhyay , G Paul , H Imaiand . Internal state recovery of Grain-v1 employing normality order of the filter function. Information Security Iet, 2012, 6( 2): 55– 64
https://doi.org/10.1049/iet-ifs.2011.0107
16 E Pasalic . On guess and determine cryptanalysis of LFSR-based stream ciphers. IEEE Transactions on Information Theory, 2009, 55( 7): 3398– 3406
https://doi.org/10.1109/TIT.2009.2021316
17 C Boura , A Canteaut . 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
18 Y Z Wei , E Pasalic , F R Zhang . New constructions of resilient functions with strictly almost optimal nonlinearity via non-overlap spectra functions. Information Sciences, 2017, 415 : 377– 396
19 T W Cusick , P Stanica . Cryptographic Boolean Functions and Applications. 1st ed. San Diego: Elsevier, 2009,
20 G Z Xiao , J L Massey . A spectral characterization of correlation immune combining functions. IEEE Transactions on Information Theory, 1988, 34( 3): 569– 571
https://doi.org/10.1109/18.6037
21 Q Y Wen , X X Niu , Y X Yang . Boolean Functions in Modern Cryptography. 1st ed. Beijing: Science Press, 2000,
22 X M Zhang , Y L Zheng . Cryptographically resilient functions. IEEE Transactions on Information Theory, 1997, 43( 5): 1740– 1747
https://doi.org/10.1109/18.623184
23 X M Wang , G Z Xiao . Error Correcting Code – Principle and Method. 1st ed. Xian: Xidian University Press, 2003,
24 S J Fu , C Li , L J Qu . A recursive construction of highly nonlinear resilient vectorial functions. Information Science, 2014, 269 : 388– 396
https://doi.org/10.1016/j.ins.2013.10.015
[1] Xin LIU, An WANG, Liehuang ZHU, Yaoling DING, Zeyuan LYU, Zongyue WANG. SCARE and power attack on AES-like block ciphers with secret S-box[J]. Front. Comput. Sci., 2022, 16(4): 164814-.
[2] Wenfeng YANG, Yupu HU. A resynchronization attack on stream ciphers filtered by Maiorana-McFarland functions[J]. Front Comput Sci Chin, 2011, 5(2): 158-162.
[3] Zhixiong CHEN, Xiaoni DU, . Linear complexity and autocorrelation values of a polyphase generalized cyclotomic sequence of length pq[J]. Front. Comput. Sci., 2010, 4(4): 529-535.
[4] Yu ZHOU, Guozhen XIAO, . On the equal-weight symmetric Boolean functions[J]. Front. Comput. Sci., 2009, 3(4): 485-493.
[5] Nianping WANG, Chenhui JIN, . Security evaluation against differential and linear cryptanalyses for Feistel ciphers[J]. Front. Comput. Sci., 2009, 3(4): 494-502.
[6] ZHANG Weiguo, ZHANG Weiguo, XIAO Guozhen, XIAO Guozhen, CAI Mian, CAI Mian. On constructing disjoint linear codes[J]. Front. Comput. Sci., 2007, 1(2): 226-230.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed