Novel Recursive Construction Method for Resilient S-Boxes

Abstract:

Resilient S-boxes have many applications in quantum cryptographic key distribution, random sequence generation for stream ciphers, and fault-tolerant distributed computing. In this paper, we provide a novel method of constructing new resilient S-boxes from old ones. The proposed method is a simple modification on the recursive construction technique for resilient S-boxes due to Zhang and Zheng. The modified Zhang-Zheng construction has better performance since it increases the output dimensions of S-boxes, whereas having the same resiliency as the existing method. Using this new method, given an (n, m, t)-resilient S-box, one can construct an ((h+1)^kn, (h+1)^km, 2^k(1+t) -1)-resilient S-box for all h = 2, 3,…, and k =1, 2,….

• Periodical: Advanced Materials Research (Volumes 225-226)
• Pages: 1149-1152
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.225-226.1149
• Online since: April 2011
• Authors: Sheng Gao, Wen Ping Ma
• Keywords: Boolean Function, Construction, Cryptography, Resilient, S-Box

References

[1] B. Chor, O. Goldreich, J. Hastad, J. Friedman, S. Rudich, and R. Smolensky: The bit extraction problem or t-resilient functions, in Proc. 26th IEEE Symp. Foundations of Computer Science, Vol. 26, pp.396-407. (1985).

DOI: 10.1109/sfcs.1985.55

[2] C.H. Bennett, G. Brassard, and J.M. Robert: Privacy amplification by public discussion, SIAM Journal on Computing, Vol. 17, No. 2, pp.210-229. (1988).

DOI: 10.1137/0217014

[3] T. Siegenthaler: Correlation-immunity of nonlinear combining functions for cryptographic applications, IEEE Trans. Inf. Theory., Vol. 30, No. 5, pp.776-780. (1984).

DOI: 10.1109/tit.1984.1056949

[4] R.A. Rueppel: Analysis and design of stream ciphers (Springer-Verlag, 1986).

[5] X.M. Zhang and Y. Zheng: Cryptographically resilient functions, IEEE Trans. Inf. Theory., Vol. 43, No. 5, pp.1740-1747. (1997).

DOI: 10.1109/18.623184

[6] L.S. Chen and F.W. Fu: On the constructions of new resilient functions from old ones, IEEE Trans. Inf. Theory., Vol. 45, No. 6, pp.2077-2082. (1999).

DOI: 10.1109/18.782141

[7] K. Kurosawa, T. Satok, and K. Yamamoto: Highly nonlinear t-resilient functions, Journal of Universal Computer Science, Vol. 3, No. 6, pp.721-729. (1997).

[8] J.H. Cheon: Nonlinear vector resilient functions, in Advances in Cryptology-CRYPTO 2001, Santa Barbara, California, USA, Springer-Verlag, LNCS 2139, pp.458-469. (2001).

DOI: 10.1007/3-540-44647-8_27

[9] E. Pasalic and S. Maitra: Linear codes in generalized construction of resilient functions with very high nonlinearity, IEEE Trans. Inf. Theory., Vol. 48, No. 8, pp.2182-2191. (2002).

DOI: 10.1109/tir.2002.800492

[10] T. Johansson and E. Pasalic: A construction of resilient functions with high nonlinearity, IEEE Trans. Inf. Theory., Vol. 49, No. 2, pp.494-501. (2003).

DOI: 10.1109/tit.2002.807297

[11] K.C. Gupta and P. Sarkar: Improved construction of nonlinear resilient S-boxes, IEEE Trans. Inf. Theory., Vol. 51, No. 1, pp.339-348. (2005).

DOI: 10.1109/tit.2004.839524

[12] K.C. Gupta and P. Sarkar: Construction of high degree resilient S-boxes with improved nonlinearity, Information Processing Letters, Vol. 95, No. 3, pp.413-417. (2005).

DOI: 10.1016/j.ipl.2005.02.014

[13] F.J. Macwillams and N.J.A. Sloane: The Theory of Error Correcting Codes, North-Holland, Amsterdam. (1977).

[14] G.Z. Xiao and J.L. Massey: A spectral characterization of correlation-immune combining functions, IEEE Trans. Inf. Theory., Vol. 34, No. 3, pp.569-571. (1988).

DOI: 10.1109/18.6037