Abstract
We study a corpus of particular Boolean functions: the idempotents. They enable us to construct functions which achieve the best possible tradeoffs between the cryptographic fundamental properties: balancedness, correlation-immunity, a high degree and a high nonlinearity (that is a high distance from the affine functions). They all represent extremely secure cryptographic primitives to be implemented in stream ciphers.
Chapter PDF
References
D. Augot and N. Sendrier. Idempotents and the BCH bound. IEEE Transactions on Information Theory, 40(1):204–207, 1994.
E. R. Berlekamp and L. R. Welch. Weight distributions of the cosets of the (32,6) Reed-Muller code. IEEE Transactions on Information Theory, 18(1):203–207, January 1972.
R. A. Brualdi, N. Cai, and V. S. Pless. Orphan structure of the first-order Reed-Muller codes. Discrete Mathematics, (102):239–247, 1992.
P. Camion, C. Carlet, P. Charpin, and N. Sendrier. On correlation-immune functions. In J. Feigenbaum, editor, Advances in Cryptology — CRYPT0'91, number 576 in Lecture Notes in Computer Science, pages 86–100. Springer-Verlag, 1992.
V. Chepyzhov and B. Smeets. On a fast correlation attack on certain stream ciphers. In D.W. Davis, editor, Advances in Cryptology — EUROCRYPT'91, number 547 in Lecture Notes in Computer Science, pages 176–185. Springer-Verlag, 1991.
H. Dobbertin. Construction of bent functions and balanced Boolean functions with high nonlinearity. In B. Preneel, editor, Fast Software Encryption, number 1008 in Lecture Notes in Computer Science, pages 61–74. Springer-Verlag, 1994.
C. Fontaine. The nonlinearity of a class of Boolean functions with short representation. In J. PŘibyl, editor, PRAGOCRYPT'96, pages 129–144. CTU Publishing House, 1996.
J. Golic and M. Mihaljevic. A fast iterative algorithm for a shift register initial state reconstruction given the noisy output sequence. In Advances in Cryptology — AUSCRYPT'90, number 453 in Lecture Notes in Computer Science, pages 165–175. Springer-Verlag, 1990.
J. Golic and M. Mihaljevic. A generalized correlation attack on a class of stream ciphers based on the Levenshtein distance. Journal of Cryptology, (3):201–212, 1991.
J. Golic and M. Mihaljevic. Convergence of a Bayesian iterative error-correction procedure on a noisy shift register sequence. In Advances in Cryptology — EUROCRYPT'92, number 658 in Lecture Notes in Computer Science, pages 124–137. Springer-Verlag, 1993.
F.J. MacWilliams and N.J.A. Sloane. The Theory of Error Correcting Codes. North-Holland, 1992.
J. L. Massey. Some applications of Coding Theory in Cryptography. In P.G. Farrel, editor, Codes and Cyphers: Cryptography and Coding IV, pages 33–47, 1995.
W. Meier and O. Staffelbach. Fast correlation attacks on stream ciphers. In C.G. Günther, editor, Advances in Cryptology — EUROCRYPT'88, number 330 in Lecture Notes in Computer Science, pages 301–314. Springer-Verlag, 1988.
W. Meier and O. Staffelbach. Nonlinearity criteria for cryptographic functions. In J.Vandewalle J.-J.Quisquater, editor, Advances in Cryptology — EUROCRYPT'89, number 434 in Lecture Notes in Computer Science, pages 549–562. Springer-Verlag, 1990.
J. Mykkeltveit. The covering radius of the [128,8] Reed-Muller code is 56. IEEE Transactions on Information Theory, 26(3):358–362, May 1980.
N.J. Patterson and D. H. Wiedemann. The covering radius of the [215,16] Reed-Muller code is at least 16276. IEEE Transactions on Information Theory, 29(3):354–356, May 1983.
N.J. Patterson and D. H. Wiedemann. Correction to [16]. IEEE Transactions on Information Theory, 36(2):443, March 1990.
O.S. Rothaus. On bent functions. Journal of Combinatorial Theory, (20):300–305, 1976.
R. A. Rueppel. Analysis and Design of Stream Ciphers. Springer-Verlag, 1986.
R. A. Rueppel. Contemporary Cryptology: the science of Information Integrity, chapter Stream Ciphers, pages 65–134. IEEE Press, 1992.
B. Schneier. Applied Cryptography. Wiley, second edition, 1996.
T. Siegenthaler. Correlation-immunity of nonlinear combining functions for cryptographic applications. IEEE Transactions on Information Theory, 30(5):776–780, September 1984.
T. Siegenthaler. Decrypting a class of stream ciphers using ciphertext only. IEEE Transactions on Computers, 34(1):81–84, January 1985.
K. Zeng and M. Huang. On the linear syndrome method in cryptanalysis. In S. Goldwasser, editor, Advances in Cryptology — CRYPTO'88, number 403 in Lecture Notes in Computer Science, pages 469–478. Springer-Verlag, 1990.
K. Zeng, C. H. Yang, and T. R. Rao. An improved linear syndrome algorithm in cryptanalysis with applications. In A.J. Menezes S.A. Vanstone, editor, Advances in Cryptology — CRYPTO'90, number 537 in Lecture Notes in Computer Science, pages 34–47, 1991.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Filiol, E., Fontaine, C. (1998). Highly nonlinear balanced Boolean functions with a good correlation-immunity. In: Nyberg, K. (eds) Advances in Cryptology — EUROCRYPT'98. EUROCRYPT 1998. Lecture Notes in Computer Science, vol 1403. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0054147
Download citation
DOI: https://doi.org/10.1007/BFb0054147
-
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64518-4
Online ISBN: 978-3-540-69795-4
eBook Packages: Springer Book Archive