Guessing secrets efficiently via list decoding

ABSTRACT

We consider the guessing secrets problem defined by Chung et al. [2001]. This is a variant of the standard 20 questions game where the player has a set of k > 1 secrets from a universe of N possible secrets. The player is asked Boolean questions about the secret. For each question, the player picks one of the k secrets adversarially, and answers according to this secret.

We present an explicit set of O(log N) questions together with an efficient (i.e., poly(log N) time) algorithm to solve the guessing secrets problem for the case of 2 secrets. This answers the main algorithmic question left unanswered by Chung et al. [2001]. The main techniques we use are small &epsis;-biased spaces and the notion of list decoding.

We also establish bounds on the number of questions needed to solve the k-secrets game for k > 2, and discuss how list decoding can be used to get partial information about the secrets, specifically to find a small core of secrets that must intersect the actual set of k secrets.

REFERENCES

• 1: Alon, N., Bruck, J., Naor, J., Naor, M., and Roth, R. 1992. Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs. IEEE Trans. Inf. Theory 38, 509-- 516.
• 2: Noga Alon , Eldar Fischer , Mario Szegedy, Parent-identifying codes, Journal of Combinatorial Theory Series A, v.95 n.2, p.349-359, August 2001 [doi>10.1006/jcta.2001.3177]
• 3: Alon, N., Goldreich, O., Haastad, J., and Peralta, R. 1992. Simple constructions of almost k-wise independent random variables. Random Struct. Alg. 3, 289--304.
• 4: Noga Alon , Venkatesan Guruswami , Tali Kaufman , Madhu Sudan, Guessing secrets efficiently via list decoding, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.254-262, January 06-08, 2002, San Francisco, California
• 5: Alexander Barg , Gérard Cohen , Sylvia Encheva , Gregory Kabatiansky , Gilles Zémor, A Hypergraph Approach to the Identifying Parent Property: The Case of Multiple Parents, SIAM Journal on Discrete Mathematics, v.14 n.3, p.423-431, 2001 [doi>10.1137/S0895480100376848]
• 6: Benny Chor , Amos Fiat , Moni Naor, Tracing Traitors, Proceedings of the 14th Annual International Cryptology Conference on Advances in Cryptology, p.257-270, August 21-25, 1994
• 7: Chung, F., Graham, R., and Leighton, T. 2001. Guessing secrets. Electron. J. Combinatorics 8, 1, R13.
• 8: Fan Chung , Ronald Graham , Linyuan Lu, Guessing secrets with inner product questions, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.247-253, January 06-08, 2002, San Francisco, California
• 9: Cohen, G. D., Encheva, S. B., and Schaathun, H. G. 2001. On separating codes. Tech. Rep., Ecole Nationale Supérieure des T élécommunications, Paris.
• 10: Erdős, P. and Lovász, L. 1975. In Infinite and Finite Sets, Proceedings of the Colloqmium of the Math Society Janos Bolyai, 10, Problems and results on 3-chromatic hypergraphs and some related questions. North-Holland, Amsterdam, 609--627.
• 11: Anna Gál, A characterization of span program size and improved lower bounds for monotone span programs, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.429-437, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276855]
• 12: Guruswami, V. and Sudan, M. 1999. Improved decoding of Reed-Solomon and algebraic-geometric codes. IEEE Trans. Inf. Theory 45, 1757--1767.
• 13: Venkatesan Guruswami , Madhu Sudan, List decoding algorithms for certain concatenated codes, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.181-190, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335327]
• 14: Guruswami, V. and Sudan, M. 2001. Extensions to the Johnson bound. manuscript. http://people.csail.mit.edu/madhu/papers/johnson.ps.
• 15: Henk D. L. Hollmann , Jack H. van Lint , Jean-Paul Linnartz , Ludo M. G. M. Tolhuizen, On codes with the identifiable parent property, Journal of Combinatorial Theory Series A, v.82 n.2, p.121-133, May 1998 [doi>10.1006/jcta.1997.2851]
• 16: I've Got a Secret. 1952. I've got a secret. http://www.timvp.com/ivegotse.html.
• 17: Kleitman, D. J. and Spencer, J. 1973. Families of k-independent sets. Discrete Math. 6, 255--262.
• 18: János Körner , Gábor Simonyi, Separating partition systems and locally different sequences, SIAM Journal on Discrete Mathematics, v.1 n.3, p.355-359, Aug. 1988 [doi>10.1137/0401035]
• 19: Micciancio, D. and Segerlind, N. 2001. Guessing two secrets with small queries. Tech. Rep. CS2001-0687, Computer Science and Engineering Department, University of California at San Diego. November.
• 20: Micciancio, D. and Segerlind, N. 2004. Using hypergraph homomorphisms to guess three secrets. manuscript.
• 21: Joseph (Seffi) Naor , Moni Naor, Small-bias probability spaces: efficient constructions and applications, SIAM Journal on Computing, v.22 n.4, p.838-856, Aug. 1993 [doi>10.1137/0222053]
• 22: M. Naor , L. J. Schulman , A. Srinivasan, Splitters and near-optimal derandomization, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.182, October 23-25, 1995
• 23: Nielsen, R. R. and Høholdt, T. 2000. Decoding Reed-Solomon codes beyond half the minimum distance. In Coding Theory, Cryptography and Related Areas, Buchmann et al., eds. Springer, Berlin, 221--236.
• 24: Razborov, A. 2005. Guessing more secrets via list decoding. Internet Math. 2, 1, 21--30.
• 25: Roth, R. and Ruckenstein, G. 2000. Efficient decoding of Reed-Solomon codes beyond half the minimum distance. IEEE Trans. Inf. Theory 46, 1 (Jan.), 246--257.
• 26: Segalovich, Y. L. 1994. Separating systems. Problems Inf. Transm. 30, 2, 105--123.
• 27: J. H. Van Lint, Introduction to Coding Theory, Springer-Verlag New York, Inc., Secaucus, NJ, 1998

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms, Theory

Keywords:
&epsis;-biased spaces, 20 questions, k-universal sets, decoding algorithms, error-correcting codes