Boolean Functions Derived from Pseudorandom Binary Sequences

详细信息    查看全文

• 作者：Gottlieb Pirsic (1) gpirsic@gmail.com
  Arne Winterhof (2) arne.winterhof@oeaw.ac.at
• 关键词：Boolean functions – ; sparsity – ; correlation measure – ; combinatorial complexity – ; cryptography – ; nonlinearity – ; pseudorandomness
• 刊名：Lecture Notes in Computer Science
• 出版年：2012
• 出版时间：2012
• 年：2012
• 卷：7280
• 期：1
• 页码：101-109
• 全文大小：175.4 KB
• 参考文献：1. Alon, N., Kohayakawa, Y., Mauduit, C., Moreira, C.G., R枚dl, V.: Measures of pseudorandomness for finite sequences: typical values. Proc. Lond. Math. Soc. 95(3), 778–812 (2007)
  2. Aly, H., Winterhof, A.: Boolean functions derived from Fermat quotients. Cryptogr. Commun. 3, 165–174 (2011)
  3. 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: Ytrehus, 脴. (ed.) WCC 2005. LNCS, vol. 3969, pp. 135–143. Springer, Heidelberg (2006)
  4. Brandst盲tter, N., Winterhof, A.: Some notes on the two-prime generator of order 2. IEEE Trans. Inform. Theory 51, 3654–3657 (2005)
  5. Brandst盲tter, N., Winterhof, A.: Linear complexity profile of binary sequences with small correlation measure. Period. Math. Hungar. 52, 1–8 (2006)
  6. Brandst盲tter, N., Winterhof, A.: Nonlinearity of binary sequences with small autocorrelation. In: Proceedings of the Second International Workshop on Sequence Design and its Applications in Communications (IWSDA 2005), pp. 44–47 (2005)
  7. 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)
  8. Cusick, T.W., Stănică, P.: Cryptographic Boolean functions and applications. Elsevier/Academic Press, Amsterdam (2009)
  9. Harper, L.H., Hsieh, W.N., Savage, J.E.: A class of Boolean functions with linear combinational complexity. Theoret. Comput. Sci. 1, 161–183 (1975)
  10. Lange, T., Winterhof, A.: Arne Interpolation of the discrete logarithm in F q by Boolean functions and by polynomials in several variables modulo a divisor of q − 1. In: International Workshop on Coding and Cryptography (WCC 2001), Paris. Discrete Appl. Math., vol. 128, pp. 193–206 (2003)
  11. 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, 223–229 (2002)
  12. Rivat, J., S谩rk枚zy, A.: Modular constructions of pseudorandom binary sequences with composite moduli. Period. Math. Hungar. 51, 75–107 (2005)
  13. Mauduit, C., S谩rk枚zy, A.: On finite pseudorandom binary sequences. I. Measure of pseudorandomness, the Legendre symbol. Acta Arith. 82, 365–377 (1997)
  14. S谩rk枚zy, A.: On finite pseudorandom binary sequences and their applications in cryptography. Tatra Mt. Math. Publ. 37, 123–136 (2007)
  15. Shparlinski, I.E.: Cryptographic Applications of Analytic Number Theory: Complexity Lower Bounds and Pseudorandomness. Birkh盲user (2003)
  16. Topuzoğlu, A., Winterhof, A.: Pseudorandom sequences. In: Topics in Geometry, Coding Theory and Cryptography. Algebr. Appl., vol. 6, pp. 135–166. Springer, Dordrecht (2007)
• 作者单位：1. Institute for Financial Mathematics, Kepler University Linz, Altenbergerstr. 69, A-4040 Linz, Austria2. Johann Radon Institute for Computational and Applied Mathematics, Austrian Academy of Sciences, Altenberger Str. 69, A-4040 Linz, Austria
• ISSN：1611-3349

文摘

We study measures used to assess Boolean functions, where the functions are understood to be derived from binary sequences. We prove relations between two complexity measures for these Boolean functions and the correlation measure of order k of the corresponding sequence. More precisely, we study sparsity and combinatorial complexity of the Boolean function. Moreover, for a sequence with ’typical’ values of the correlation measure of order k we apply these relations to derive bounds on the complexity measures for the corresponding Boolean function. Finally, we apply our results to Sidelnikov sequences for which nice upper bounds on the correlation measure are known.