Bounds for Resilient Functions and Orthogonal Arrays

Extended Abstract
  • Jürgen Bierbrauer
  • K. Gopalakrishnan
  • D. R. Stinson
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 839)


Orthogonal arrays (OAs) are basic combinatorial structures, which appear under various disguises in cryptology and the theory of algorithms. Among their applications are universal hashing, authentication codes, resilient and correlation-immune functions, derandomization of algorithms, and perfect local randomizers. In this paper, we give new bounds on the size of orthogonal arrays using Delsarte’s linear programming method. Then we derive bounds on resilient functions and discuss when these bounds can be met.


Orthogonal Array Linear Code Stream Cipher Congruence Class Binary Linear Code 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


  1. 1.
    C. H. Bennett, G. Brassard, A. K. Ekert: Quantum cryptography. Scientific American 267(4) (1992), 26–33CrossRefGoogle Scholar
  2. 2.
    C. H. Bennett, G. Brassard, J. M. Robert: Privacy amplification by public discussion. SIAM J. Computing 17 (1988), 210–229CrossRefMathSciNetGoogle Scholar
  3. 3.
    J. Bierbrauer: Bounds on orthogonal arrays and codes. PreprintGoogle Scholar
  4. 4.
    A. E. Brouwer, T. Verhoeff: An updated table of minimum-distance bounds for binary linear codes. IEEE Transactions on Information Theory 39 (1993), 662–677zbMATHCrossRefMathSciNetGoogle Scholar
  5. 5.
    P. Camion, C. Carlet, P. Charpin, N. Sendrier: On correlation-immune functions. In: Advances in Cryptology — CRYPTO’ 91. Lecture Notes in Computer Science 576 (1992), 86–100CrossRefGoogle Scholar
  6. 6.
    B. Chor, O. Goldreich, J. Håstad, J. Friedman, S. Rudich, R. Smolensky: The bit extraction problem or t—resilient functions. In: 26th IEEE Symposium on Foundations of Computer Science, 1985, pp. 396–407Google Scholar
  7. 7.
    P. Delsarte: Four fundamental parameters of a code and their combinatorial significance. Information and Control 23 (1973), 407–438CrossRefzbMATHMathSciNetGoogle Scholar
  8. 8.
    J. Friedman: On the bit extraction problem. In: 33rd IEEE Symposium on Foundations of Computer Science, 1992, pp. 314–319Google Scholar
  9. 9.
    K. Gopalakrishnan, D. R. Stinson: Characterizations of non-binary correlation-immune and resilient functions. Technical Report UNL-CSE-93-010, University of Nebraska, March 1993. Submitted to: Designs, Codes and CryptographyGoogle Scholar
  10. 10.
    K. Gopalakrishnan, D. R. Stinson, J. Bierbrauer: Orthogonal arrays, resilient functions, error correcting codes and linear programming bounds. PreprintGoogle Scholar
  11. 11.
    F. J. MacWilliams, N. J. A. Sloane: The Theory of Error-Correcting Codes, North-Holland, 1977Google Scholar
  12. 12.
    R. J. McEliece, E. R. Rodemich, H. Rumsey, L. R. Welch: New upper bounds on the rate of a code via the Delsarte-McWilliams inequalities. IEEE Trans. on Information Theory 23 (1977), 157–166zbMATHCrossRefMathSciNetGoogle Scholar
  13. 13.
    R. A. Rueppel: Analysis and Design of Stream Ciphers, Springer-Verlag, 1986Google Scholar
  14. 14.
    D. R. Stinson: Resilient functions and large sets of orthogonal arrays. Congressus Numerantium 92 (1993), 105–110MathSciNetGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 1994

Authors and Affiliations

  • Jürgen Bierbrauer
    • 1
  • K. Gopalakrishnan
    • 2
  • D. R. Stinson
    • 2
    • 3
  1. 1.Mathematisches Institut der UniversitätHeidelbergGermany
  2. 2.Department of Computer Science and EngineeringUniversity of Nebraska -LincolnLincoln
  3. 3.Center for Communication and Information ScienceUniversity of Nebraska -LincolnLincoln

Personalised recommendations