×

\(t\)-resilient functions and the partial exposure problem. (English) Zbl 1152.94007

The wire-tap channel II introduced by L. H. Ozarow and A. D. Wyner was the first instance of a partial exposure problem. The partial exposure problem is that an intruder can observe at most \(t\) symbols of his choice from an \(n\)-symbol message. The authors have managed to adapt the use of \(t\)-resilient functions for protecting messages against Partial Exposure. A solution based upon a \(t\)-resilient function has been given by the perfect local pseudo-random generator introduced by Maurer and Massey, but its use needs a secret key shared by the sender and the receiver. In contrast, the authors have been able to provide solutions to protect messages against partial exposure without using secret keys, for various ranges of parameters. Moreover they provide low complexity algorithms.

MSC:

94A60 Cryptography
05B05 Combinatorial aspects of block designs
05E30 Association schemes, strongly regular graphs
94B15 Cyclic codes
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bennett, C., Brassard, G., Robert, J.: Privacy amplification by public discussion. SIAM. J. Comput. 17(2), 210–229 (1988) · Zbl 0644.94010 · doi:10.1137/0217014
[2] Bierbauer, J., Gopalakrishna, K., Stinson, D.: Orthogonal Arrays, resilient functions, error-correcting codes and linear programming bounds. SIAM. J. Discr. Math. 9, 424–452 (1996) · Zbl 0862.05014 · doi:10.1137/S0895480194270950
[3] Camion, P., Carlet, C., Charpin, P., Sendrier, N.: On correlation-immune functions. In: Feigenbaum, J. (ed.) Advances in Cryptology–CRYPTO’91. Lecture Notes in Computer Science, N 576, pp. 86–100. Springer, Heidelberg (1992) · Zbl 0763.94006
[4] Camion, P., Canteaut, A.: Construction of t-Resilient Functions over a Finite Alphabet. In: Ueli Maurer (ed.) Advances in Cryptology–EUROCRYPT’96, N 1070. Lecture Notes in Computer Science, pp. 283–293. Springer, Heidelberg (1996) · Zbl 1304.94038
[5] Camion, P., Canteaut, A.: Generalization of Siegenthaler inequality and Schnorr-Vaudenay multipermutations, In: Koblitz, N. (ed.) Advances in Cryptology–CRYPTO’96. Lecture Notes in Computer Science, N 1109, Springer, Heidelberg (1996) · Zbl 1329.94055
[6] Camion, P.: Codes and association schemes. Handbook of Coding Theory, Chap. 18, pp. 1441–1556, North Holland (1998)
[7] Camion, P., Canteaut, A.: Correlation-immune and resilient functions over a finite alphabet and their applications in cryptography. Designs Codes Cryptography 16(2), 121– (1999) · Zbl 0936.94009 · doi:10.1023/A:1008337029047
[8] Camion, P.: Codes over \({{\mathbb Z}_{p^n}}\) and association schemes. In: Barg, A. Litsyn, S. (eds.) Codes and Association Schemes AMS–DIMACS, 2001, 303 pages, ISBN 0-8218-2074-5. DIMACS/56, American Mathematical Society, Providence, pp. 59–86 (2001) · Zbl 0990.94026
[9] Chor, B., Friedman, J., Golreich, O., Hastad, J., Rudich, S., Smolensky, R.: The bit extraction problem or t-resilient Functions. Proceedings of FOCS, pp. 396–407 (1985)
[10] Delsarte, P.: An algebraic approach to association schemes of coding theory Thesis, Université catholique de Louvain, June 1973 · Zbl 1075.05606
[11] Dodis, Y.: Exposure-Resilient Cryptography PHD Thesis, Massachusetts Institute of Technology, August 2000. http://theory.lcs.mit.edu/yevgen/ps/phd-thesis.ps
[12] Friedman, J.: On the bit extraction Problem. Proceedings of FOCS, pp. 314–319 (1992) · Zbl 0977.68558
[13] Gopalakrishnan, K., Stinson, D.R.: Three characterizations of non-binary correlation-immune and resilient functions. Designs Codes Cryptography. 5, 241–251 (1995) · Zbl 0821.94026 · doi:10.1007/BF01388386
[14] Roger Hammons, A., Vijay Kumar, P., Calderbank, A.R., Sloane, N.J.A., Solé, P.: The \({{\mathbb Z}_{4}}\) -Linearity of Kerdock, Preparata, Goethals and Related Codes. IEEE. Trans. Inf. Theory 40, 301–319 (1994) · Zbl 0811.94039 · doi:10.1109/18.312154
[15] Hedayat, A.S., Sloane, N.J.A., Stufken, J.: Orthogonal arrays: theory and applications. Springer, New York (1999) · Zbl 0935.05001
[16] Lidl, R., Niederreiter, H.: Finite fields, encyclopedia of mathematics and its applications, vol. 20, Cambridge University Press, Cambridge, London (1987)
[17] MacWilliams, F.J., Sloane, N.J.: The theory of error correcting codes. North-Holland (1977) · Zbl 0369.94008
[18] Maurer, U.M., Massey, J.L.: Perfect local randomness in pseudo-random sequences. In: Brassard, G. (ed.) Advances in Cryptology–CRYPTO’89, N 435 in Lecture Notes in Computer Science, pp. 100–112. Springer, Heidelberg (1990) · Zbl 0719.65003
[19] Ozarow, L.H., Wyner, A.D.: Wire-tap Channel II. In: Beth, T., Cot, N., Ingemarson, I. (eds.) Advances in Cryptology–Proceedings of Eurocrypt 84, Lecture Notes in Computer Science, No. 209, pp. 33–50 Springer, Berlin (1985) · Zbl 0596.94007
[20] Rao, C.R.: Factorial experiments derivable from combinatorial arrangements of arrays. J. R. Statist. 9, 128–139 (1947) · Zbl 0031.06201
[21] Schnorr, C.P.: On the construction of random number generators and random function generators. In: Christof G. Gnther (ed.) Advances in Cryptology–Proceedings of EUROCRYPT’88, Lecture Notes in Computer Science, N. 330, pp. 225–232, Springer, Berlin (1988)
[22] Siegenthaler, T.: Correlation-immunity of nonlinear combining functions for cryptographic applications, IEEE Inf. Theory, vol. IT-30, N 5, Sept. 84 · Zbl 0554.94010
[23] Stinson, D.R., Massey, J.L.: An infinite class of counterexamples to a conjecture concerning nonlinear resilient functions. J. Cryptology. 8(3), 157–166 (1995) · Zbl 0840.94019 · doi:10.1007/BF00202271
[24] Xiao, G., Massey, J.L.: A spectral characterization of correlation-immune combining functions. IEEE Trans. Inform. Theory IT-34(3), 569–571 (1988) · Zbl 0653.94011 · doi:10.1109/18.6037
[25] Zhang, X., Zheng, U.: On nonlinear resilient functions. In: Guillou, L., Quisquater, J.J. (eds.) Advances in Cryptology–EUROCRYPT’95, N 921 in Lecture Notes in Computer Science, pp. 274–288. Springer Heidelberg (1995) · Zbl 0973.94518
[26] Wan, Z.-X.: Quaternary Codes. World Scientific (1997)
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.