×

Boolean functions derived from Fermat quotients. (English) Zbl 1235.06014

Summary: We study Boolean functions derived from Fermat quotients modulo \(p\) using the Legendre symbol. We prove bounds on several complexity measures for these Boolean functions: the nonlinearity, sparsity, average sensitivity, and combinatorial complexity. Our main tools are bounds on character sums of Fermat quotients modulo \(p\).

MSC:

06E30 Boolean functions
94A60 Cryptography
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Brandstätter, N., Lange, T., Winterhof, A.: On the non-linearity and sparsity of Boolean functions related to the discrete logarithm in finite fields of characteristic two. In: Coding and Cryptography. Lect. Notes Comput. Sci., vol. 3969, pp. 135–143. Springer, Berlin (2006) · Zbl 1151.94487
[2] Carlet, C.: Boolean functions for cryptography and error correcting codes. In: Crama, Y., Hammer, P.L. (eds.) Boolean Models and Methods in Mathematics, Computer Science, and Engineering, pp. 257–397. Cambridge University Press (2010) · Zbl 1209.94035
[3] Carlet, C., Helleseth, T.: Sequences, Boolean functions, and cryptography. In: Boztas, S., et al. (eds.) CRC Handbook of Sequences, Codes and Applications. Chapman and Hall/CRC Press (to appear)
[4] Chen, Z., Ostafe, A., Winterhof, A.: Structure of pseudorandom numbers derived from Fermat quotients. In: Hasan, M.A., Helleseth, T. (eds.) WAIFI 2010. Lect. Notes Comput. Sci. vol. 6087, pp. 73–85. Springer, Berlin (2010) · Zbl 1230.11092
[5] Ernvall, R., Metsänkylä, T.: On the p-divisibility of Fermat quotients. Math. Comput. 66(219), 1353–1365 (1997) · Zbl 0903.11002 · doi:10.1090/S0025-5718-97-00843-0
[6] Gomez, D., Winterhof, A.: Multiplicative character sums of Fermat quotients and pseudorandomness. Period. Math. Hung. (to appear) · Zbl 1263.11110
[7] Granville, A.: Some conjectures related to Fermat’s last theorem. Number Theory, pp. 177–192. W. de Gruyter, NY (1990) · Zbl 0702.11015
[8] Heath-Brown, D.: An estimate for Heilbronn’s exponential sum. In: Analytic Number Theory, Proc. Conf. in Honor of Heini Halberstam, pp. 541–463. Birkhäuser, Boston (1996) · Zbl 0857.11041
[9] Lange, T., Winterhof, A.: Interpolation of the discrete logarithm in F q by Boolean functions and by polynomials in several variables modulo a divisor of q1. International Workshop on Coding and Cryptography (WCC 2001) (Paris). Discrete Appl. Math. 128(1), 193–206 (2003) · Zbl 1039.94007 · doi:10.1016/S0166-218X(02)00445-6
[10] Lange, T., Winterhof, A.: Incomplete character sums over finite fields and their application to the interpolation of the discrete logarithm by Boolean functions. Acta Arith. 101(3), 223–229 (2002) · Zbl 0998.11070 · doi:10.4064/aa101-3-3
[11] Ostafe, A., Shparlinski, I.: Pseudorandomness and dynamics of Fermat quotients. SIAM J. Discrete Math. 25, 50–71 (2011) · Zbl 1263.11003 · doi:10.1137/100798466
[12] Rodier, F.: Asymptotic nonlinearity of Boolean functions. Des. Codes Cryptogr. 40(1), 59–70 (2006) · Zbl 1261.94029 · doi:10.1007/s10623-005-6363-8
[13] Shparlinski, I.E.: Cryptographic Applications of Analytic Number Theory: Complexity Lower Bounds and Pseudorandomness. Birkhäuser (2003) · Zbl 1036.94001
[14] Shparlinski, I.E.: Character sums of Fermat quotients. Quart. J. Math. (to appear) · Zbl 1273.11126
[15] Shparlinski, I.E.: Bounds of multiplicative character sums with Fermat quotients of primes. Bull. Aust. Math. Soc. (to appear) · Zbl 1221.11004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.