Abstract
Polynomial functions are widely used in the design of cryptographic transformations such as block ciphers, hash functions and stream ciphers, which belong to the category of T-functions. When a polynomial function is used as state transition function in a pseudorandom generator, it is usually required that the polynomial function generates a single cycle. In this paper, we first present another proof of the sufficient and necessary condition on a polynomial function \(f(\mathbf{x})=c_0+c_1\mathbf{x}+c_2\mathbf{x}^2+\cdots+c_m\mathbf{x}^m \bmod 2^n(n \geq 3)\) being a single cycle T-function. Then we give a general linear equation on the sequences {x i } generated by these T-functions, that is,
where A i,2 is a sequence of period 4, a and b are constants determined by the coefficients c i . This equation shows that the sequences generated by polynomial single cycle T-functions have potential secure problems.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Hong, J., Lee, D.H., Yeom, Y., Han, D.: A New Class of Single Cycle T-Functions. In: Gilbert, H., Handschuh, H. (eds.) FSE 2005. LNCS, vol. 3557, pp. 68–82. Springer, Heidelberg (2005)
Klimov, A., Shamir, A.: A New Class of Invertible Mappings. In: Kaliski Jr., B.S., Koç, Ç.K., Paar, C. (eds.) CHES 2002. LNCS, vol. 2523, pp. 470–483. Springer, Heidelberg (2003)
Klimov, A., Shamir, A.: Cryptographic Applications of T-Functions. In: Matsui, M., Zuccherato, R.J. (eds.) SAC 2003. LNCS, vol. 3006, pp. 248–261. Springer, Heidelberg (2004)
Klimov, A., Shamir, A.: New Cryptographic Primitives Based on Multiword T-Functions. In: Roy, B., Meier, W. (eds.) FSE 2004. LNCS, vol. 3017, pp. 1–15. Springer, Heidelberg (2004)
Klimov, A.: Application of T-functions in Cryptography, PhD Thesis, Weizmann Institute of Science (2005)
Larin, M.V.: Transitive Polynomial Transformations of Residue Class Rings. Discrete Mathematics and Applications, 141–154 (February 2002)
Molland, H., Helleseth, T.: Linear properties in T-functions. IEEE Trans. Inform. Theory, 5151–5157 (November 2006)
Rivest, R.: Permutation Polynomials Modulo 2ω. Finite Fields and their Applications, 287–292 (September 2001)
Wang, J.S., Qi, W.F.: Trace Presentation of Bent Sequence Families. Journal of Communications(China), 8–13 (January 2006)
Wang, J.S., Qi, W.F.: Analysis of Design Interleaved ZCZ Sequence Family. In: Gong, G., Helleseth, T., Song, H.-Y., Yang, K. (eds.) SETA 2006. LNCS, vol. 4086, pp. 129–140. Springer, Heidelberg (2006)
Wang, J.S., Qi, W.F.: A Class of Binary ZCZ Sequence Families Constructed by Extending Period Twice. Journal of Electronics(China), 301–304 (May 2007)
Zhang, W.Y., Wu, C.K.: The Algebraic Normal Form, Linear Complexity and k-Error Linear Complexity of Single-Cycle T-Function. In: Gong, G., Helleseth, T., Song, H.-Y., Yang, K. (eds.) SETA 2006. LNCS, vol. 4086, pp. 391–401. Springer, Heidelberg (2006)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Wang, JS., Qi, WF. (2008). Linear Equation on Polynomial Single Cycle T-Functions. In: Pei, D., Yung, M., Lin, D., Wu, C. (eds) Information Security and Cryptology. Inscrypt 2007. Lecture Notes in Computer Science, vol 4990. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-79499-8_21
Download citation
DOI: https://doi.org/10.1007/978-3-540-79499-8_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-79498-1
Online ISBN: 978-3-540-79499-8
eBook Packages: Computer ScienceComputer Science (R0)