Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-27T21:35:06.286Z Has data issue: false hasContentIssue false
  • English
  • Français

On the nonlinearity of the sequence of signs of Kloosterman sums

Published online by Cambridge University Press:  17 April 2009

Igor E. Shparlinski
Igor E. Shparlinski
Affiliation:
Department of Computing, Macquarie University, Sydney, NSW 2109, Australia, e-mail: [email protected]
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

It is known that Kloosterman sums with prime denominator p take real values, so one can define a sequence of signs of such sums. Several pseudorandom properties of this sequence have recently been studied by Fouvry, Michel, Rivat and Sárközy. Here we use one of their results to estimate a certain important characteristic of this sequence which is also of cryptographic interest.

Type
Research Article
Information
Bulletin of the Australian Mathematical Society , Volume 71 , Issue 3 , June 2005 , pp. 405 - 409
Copyright
Copyright © Australian Mathematical Society 2005

References

[1]Bernasconi, A., ‘On the complexity of balanced Boolean functions’, Inform. Process Lett. 70 (1999), 157–163.CrossRefGoogle Scholar
[2]Boppana, R.B., ‘The average sensitivity of bounded-depth circuits’, Inform. Process Lett. 63 (1997), 257–261.CrossRefGoogle Scholar
[3]Carlet, C., ‘On cryptographic complexity of Boolean functions’, in Finite Fields with Applications to Coding Theory, Cryptography and Related Areas (Springer-Verlag, Berlin, 2002), pp. 53–69.CrossRefGoogle Scholar
[4]Carlet, C., ‘On the degree, nonlinearity, algebraic thickness, and nonnormality of Boolean functions, with developments on symmetric functions’, IEEE Trans. Inform. Theory 50 (2004), 2178–2185.CrossRefGoogle Scholar
[5]Carlet, C. and Ding, C., ‘Highly nonlinear mappings’, J. Complexity 20 (2004), 205–244.CrossRefGoogle Scholar
[6]Carlet, C. and Sarkar, P., ‘Spectral domain analysis of correlation immune and resilient Boolean functions’, Finite Fields Appl. 8 (2002), 120–130.CrossRefGoogle Scholar
[7]Carlet, C. and Tarannikov, Y., ‘Covering sequences of Boolean functions and their cryptographic significance’, Des. Codes Cryptogr. 25 (2002), 263–279.CrossRefGoogle Scholar
[8]Fouvry, É., Michel, P., Rivat, J. and Sárközy, A., ‘On the pseudorandomness of the signs of Kloosterman sums’, J. Austral. Math. Soc. 77 (2004), 425–436.CrossRefGoogle Scholar
[9]Goldmann, M., ‘Communication complexity and lower bounds for simulating threshold circuits’, in Theoretical Advances in Neural Computing and Learning (Kluwer Acad. Publ., Dordrecht, 1994), pp. 85–125.CrossRefGoogle Scholar
[10]Linial, N., Mansour, Y. and Nisan, N., ‘Constant depth circuits, Fourier transform, and learnability’, J. Assoc. Comput. Mach. 40 (1993), 607–620.CrossRefGoogle Scholar
[11]Mansour, Y., ‘Learning Boolean functions via the Fourier transform’, in Theoretical Advances in Neural Computing and Learning (Kluwer Academic Publ., Dordrecht, 1994), pp. 391–424.CrossRefGoogle Scholar
[12]Roychowdhry, V., Siu, K.-Y. and Orlitsky, A., ‘Neural models and spectral methods’, in Theoretical Advances in Neural Computing and Learning (Kluwer Academic Publ., Dordrecht, 1994), pp. 3–36.CrossRefGoogle Scholar
[13]Shparlinski, I.E., Cryptographic applications of analytic number theory (Birkhäuser, Basel, 2003).CrossRefGoogle Scholar
[14]Štanikǎ, P., ‘Nonlinearity, local and global avalanche characteristics of balanced Boolean functions’, Discrete Math. 248 (2002), 181–193.CrossRefGoogle Scholar
[15]Zheng, Y., and Zhang, X.M., ‘Connections among nonlinearity, avalanche and correlation immunity’, Theoret. Comput. Sci. 292 (2003), 697–710.CrossRefGoogle Scholar