Abstract
We use the notion of covering sequence, introduced by C. Carlet and Y. Tarannikov, to give a simple characterization of bent functions. We extend it into a characterization of plateaued functions (that is bent and three-valued functions). After recalling why the class of plateaued functions provides good candidates to be used in cryptosystems, we study the known families of plateaued functions and their drawbacks. We show in particular that the class given as new by Zhang and Zheng is in fact a subclass of Maiorana-McFarland’s class. We introduce a new class of plateaued functions and prove its good cryptographic properties.
Chapter PDF
Similar content being viewed by others
Keywords
References
Biham, E., Shamir, A.: Differential Cryptanalysis of DES-like Cryptosystems. In: Menezes, A., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 2–21. Springer, Heidelberg (1990); Journal of Cryptology 4(1) (1991)
Botzas, S., Kumar, P.V.: Binary Sequences with Gold-Like Correlation but Larger Liner Span. IEEE Trans. on Information Theory 40(2), 532–537 (1994)
Camion, P., Carlet, C., Charpin, P., Sendrier, N.: On Correlation-immune Functions. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 86–100. Springer, Heidelberg (1992)
Charpin, P., Pasalic, E.: On propagations characteristics of resilient functions. In: Nyberg, K., Heys, H.M. (eds.) SAC 2002. LNCS, vol. 2595, pp. 175–195. Springer, Heidelberg (2003) (to appear)
Canteaut, A., Carlet, C., Charpin, P., Fontaine, C.: Propagation characteristics and correlation-immunity of highly nonlinear Boolean functions. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 507–522. Springer, Heidelberg (2000)
Canteaut, A., Carlet, C., Charpin, P., Fontaine, C.: On cryptographic properties of the cosets of R(1,m). IEEE Transactions on Information Theory 47(4), 1494–1513 (2001)
Canteaut, A., Charpin, P., Dobbertin, H.: Binary m-sequences with three-valued crosscorrelation: a proof ofWelch’s conjecture. IEEE Transactions on Information Theory 46, 4–8 (2000)
Canteaut, A., Charpin, P., Dobbertin, H.: Weight divisibility of cyclic codes, highly nonlinear functions on F 2m , and crosscorrelation of maximum-length sequences. SIAM Journal of Discrete Mathematics 13(1), 105–138 (2000)
Carlet, C.: Partially-bent functions. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 280–291. Springer, Heidelberg (1993)
Carlet, C.: Two new classes of bent functions. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 77–101. Springer, Heidelberg (1994)
Carlet, C.: Generalized Partial Spreads. IEEE Transactions on Information Theory 41(5), 1482–1487 (1995)
Carlet, C.: A larger Class of Cryptographic Boolean Functions via a Study of the Maiorana-McFarland Construction. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 549–564. Springer, Heidelberg (2002)
Carlet, C., Sarkar, P.: Spectral Domain Analysis of Correlation Immune and Resilient Boolean Functions. Finite Fields and Their Applications 8, 120–130 (2002)
Carlet, C., Tarannikov, Y.: Covering sequences of Boolean functions and their cryptographic significance. Designs Codes and Cryptography 25, 263–279 (2002)
Canteaut, A., Videau, M.: Degree of composition of Highly Nonlinear Functions and Applications to Higher Order Differential Cryptanalysis. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 518–533. Springer, Heidelberg (2002)
Cusik, T.W., Dobbertin, H.: Some new three-valued crosscorrelation functions for binary m-sequences. IEEE Transaction of Information Theory 42, 1238–1240 (1996)
Dillon, J.F.: Elementary Hadamard Difference sets, Phd Thesis, University of Maryland (1974)
Dobbertin, H.: Constructions of bent functions and balanced Boolean functions with high nonlinearity. In: Preneel, B. (ed.) FSE 1994. LNCS, vol. 1008, pp. 61–74. Springer, Heidelberg (1995)
Gold, R.: Maximal recursive sequences with 3-valued recursive cross-correlation functions. IEEE Transaction of Information Theory 14, 154–156 (1968)
Helleseth, T.: Some results about the cross-correlation function between two maximal linear sequences. Discrete Mathematics 16, 209–232 (1976)
Helleseth, T.: Correlation of m-Sequences and Related Topics. In: Sequences and their Qpplicqtions SETA 1998, pp. 49–66 (1999)
Helleseth, T., Vijay Kumar, P.: Sequences with low correlation. In: Pless, V., Huffman, W.C. (eds.) Handbook of Coding Theory, pp. 1765–1855. Elsevier, Amsterdam (1998)
Helleseth, T., Martinsen, H.: Sequences with ideal autocorrelation and Difference sets. In: Proceedings of International Meeting on Coding Theory and Cryptography (September 1999)
Hollmann, H.D.L., Xiang, Q.: A proof of the Welch and Niho conjectures on crosscorrelation of binary m-sequences. Finite Fields and Their applications 7 (2001)
Knudsen, L.R.: Truncated and higher order differentials. In: Preneel, B. (ed.) FSE 1994. LNCS, vol. 1008, pp. 196–211. Springer, Heidelberg (1995)
Lai, X.: Higher order derivatives and differential cryptanalysis. In: Proc. Symposium on Communication, Coding and Cryptography, in honor of J. L. Massey on the occasion of his 60’th birthday (1994)
Matsui, M.: Linear cryptanalysis method for DES cipher. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 386–397. Springer, Heidelberg (1994)
Sarkar, P., Maitra, S.: Nonlinearity bounds and construction pf resilient Boolean functions. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 512–532. Springer, Heidelberg (2000)
McFarland, R.L.: A family of noncyclic difference sets. Journal of Combinatorial Theory (15), 1–10 (1973)
Pasalic, E., Maitra, S., Johanson, T., Sarkar, P.: New Constructions of Resilient and Correlation Immune Boolean Functions Achieving Upper Bound on Nonlinearity. In: Workshop on Coding and Cryptography. Electronic Notes in Discrete Mathematics. Elsevier, Amsterdam (2001)
Pless, V.S., Huffman, W.C.: Handbook of coding theory. Elsevier, Amsterdam (1998)
Preneel, B., Van Leekwijck, W., Van Linden, L., Govaerts, R., Vandevalle, J.: Propagation characteristics of Boolean functions. In: Damgård, I.B. (ed.) EUROCRYPT 1990. LNCS, vol. 473, pp. 161–173. Springer, Heidelberg (1991)
Sarkar, P., Maitra, S.: Constructions of nonlinear Boolean functions with important cryptographic properties. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 485–506. Springer, Heidelberg (2000)
Sarkar, P., Maitra, S.: Nonlinearity bounds and constructions of resilient Boolean functions. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 515–532. Springer, Heidelberg (2000)
Mac Williams, F.J., Sloane, N.J.: The theory of error-correcting codes. North-Holland, Amsterdam (1977)
Tarannikov, Y.: On resilient Boolean functions with maximum nonlinearity. In: Roy, B., Okamoto, E. (eds.) INDOCRYPT 2000. LNCS, vol. 1977, pp. 19–30. Springer, Heidelberg (2000)
Xiao, G.-Z., Ding, C., Shan, W.: The Stability Theory of Stream Ciphers. LNCS, vol. 561. Springer, Heidelberg (1991)
Guo-Zhen, X., Massey, J.L.: A Spectral Characterization of Correlation- Immune Combining Functions. IEEE Trans. Inf. Theory IT 34(3), 569–571 (1988)
Zheng, Y., Zhang, X.: Improved upper bound on the nonlinearity of high order correlation immune functions. In: Stinson, D.R., Tavares, S. (eds.) SAC 2000. LNCS, vol. 2012, pp. 262–274. Springer, Heidelberg (2001)
Zheng, Y., Zhang, X.M.: Plateaued functions. In: Varadharajan, V., Mu, Y. (eds.) ICICS 1999. LNCS, vol. 1726, pp. 284–300. Springer, Heidelberg (1999)
Zheng, Y., Zhang, X.M.: Improved upper bound on the nonlinearity of high order correlation immune functions. In: Stinson, D.R., Tavares, S. (eds.) SAC 2000. LNCS, vol. 2012, pp. 264–274. Springer, Heidelberg (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Carlet, C., Prouff, E. (2003). On Plateaued Functions and Their Constructions. In: Johansson, T. (eds) Fast Software Encryption. FSE 2003. Lecture Notes in Computer Science, vol 2887. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-39887-5_6
Download citation
DOI: https://doi.org/10.1007/978-3-540-39887-5_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20449-7
Online ISBN: 978-3-540-39887-5
eBook Packages: Springer Book Archive