Document Open Access Logo

P₄-free Partition and Cover Numbers & Applications

Authors Alexander R. Block, Simina Brânzei, Hemanta K. Maji, Himanshi Mehta, Tamalika Mukherjee, Hai H. Nguyen

PDF
Thumbnail PDF

File

LIPIcs.ITC.2021.16.pdf
  • Filesize: 0.89 MB
  • 25 pages

Document Identifiers

Author Details

Alexander R. Block
  • Department of Computer Science, Purdue University, West Lafayette, IN, USA
Simina Brânzei
  • Department of Computer Science, Purdue University, West Lafayette, IN, USA
Hemanta K. Maji
  • Department of Computer Science, Purdue University, West Lafayette, IN, USA
Himanshi Mehta
  • Department of Computer Science, Purdue University, West Lafayette, IN, USA
Tamalika Mukherjee
  • Department of Computer Science, Purdue University, West Lafayette, IN, USA
Hai H. Nguyen
  • Department of Computer Science, Purdue University, West Lafayette, IN, USA

Funding

Alexander R. Block is supported in part by NSF CCF #1910659. Alexander R. Block, Hemanta K. Maji, Tamalika Mukherjee, and Hai H. Nguyen are supported in part by an NSF CRII Award CNS-1566499, NSF SMALL Awards CNS-1618822 and CNS-2055605, the IARPA HECTOR project, MITRE Innovation Program Academic Cybersecurity Research Awards (2019-2020, 2020-2021), a Purdue Research Foundation (PRF) Award, and The Center for Science of Information, an NSF Science and Technology Center, Cooperative Agreement CCF-0939370.

Cite As Get BibTex

Alexander R. Block, Simina Brânzei, Hemanta K. Maji, Himanshi Mehta, Tamalika Mukherjee, and Hai H. Nguyen. P₄-free Partition and Cover Numbers & Applications. In 2nd Conference on Information-Theoretic Cryptography (ITC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 199, pp. 16:1-16:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ITC.2021.16

Abstract

P₄-free graphs- also known as cographs, complement-reducible graphs, or hereditary Dacey graphs-have been well studied in graph theory. Motivated by computer science and information theory applications, our work encodes (flat) joint probability distributions and Boolean functions as bipartite graphs and studies bipartite P₄-free graphs. For these applications, the graph properties of edge partitioning and covering a bipartite graph using the minimum number of these graphs are particularly relevant. Previously, such graph properties have appeared in leakage-resilient cryptography and (variants of) coloring problems. 
Interestingly, our covering problem is closely related to the well-studied problem of product (a.k.a., Prague) dimension of loopless undirected graphs, which allows us to employ algebraic lower-bounding techniques for the product/Prague dimension. We prove that computing these numbers is NP-complete, even for bipartite graphs. We establish a connection to the (unsolved) Zarankiewicz problem to show that there are bipartite graphs with size-N partite sets such that these numbers are at least ε⋅N^{1-2ε}, for ε ∈ {1/3,1/4,1/5,...}. Finally, we accurately estimate these numbers for bipartite graphs encoding well-studied Boolean functions from circuit complexity, such as set intersection, set disjointness, and inequality.
For applications in information theory and communication & cryptographic complexity, we consider a system where a setup samples from a (flat) joint distribution and gives the participants, Alice and Bob, their portion from this joint sample. Alice and Bob’s objective is to non-interactively establish a shared key and extract the left-over entropy from their portion of the samples as independent private randomness. A genie, who observes the joint sample, provides appropriate assistance to help Alice and Bob with their objective. Lower bounds to the minimum size of the genie’s assistance translate into communication and cryptographic lower bounds. We show that (the log₂ of) the P₄-free partition number of a graph encoding the joint distribution that the setup uses is equivalent to the size of the genie’s assistance. Consequently, the joint distributions corresponding to the bipartite graphs constructed above with high P₄-free partition numbers correspond to joint distributions requiring more assistance from the genie. 
As a representative application in non-deterministic communication complexity, we study the communication complexity of nondeterministic protocols augmented by access to the equality oracle at the output. We show that (the log₂ of) the P₄-free cover number of the bipartite graph encoding a Boolean function f is equivalent to the minimum size of the nondeterministic input required by the parties (referred to as the communication complexity of f in this model). Consequently, the functions corresponding to the bipartite graphs with high P₄-free cover numbers have high communication complexity. Furthermore, there are functions with communication complexity close to the naïve protocol where the nondeterministic input reveals a party’s input. Finally, the access to the equality oracle reduces the communication complexity of computing set disjointness by a constant factor in contrast to the model where parties do not have access to the equality oracle. To compute the inequality function, we show an exponential reduction in the communication complexity, and this bound is optimal. On the other hand, access to the equality oracle is (nearly) useless for computing set intersection.

Subject Classification

ACM Subject Classification
  • Security and privacy → Mathematical foundations of cryptography
  • Security and privacy → Information-theoretic techniques
  • Theory of computation → Communication complexity
  • Mathematics of computing → Graph theory
Keywords
  • Secure keys
  • Secure private randomness
  • Gray-Wyner system
  • Cryptographic complexity
  • Nondeterministic communication complexity
  • Leakage-resilience
  • Combinatorial optimization
  • Product dimension
  • Zarankiewicz problem
  • Algebraic lower-bounding techniques
  • P₄-free partition number
  • P₄-free cover number

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Rudolf Ahlswede and Imre Csiszár. Common randomness in information theory and cryptography - I: secret sharing. IEEE Trans. Inf. Theory, 39(4):1121-1132, 1993. URL: https://doi.org/10.1109/18.243431.
  2. Rudolf Ahlswede and Imre Csiszár. Common randomness in information theory and cryptography - part II: CR capacity. IEEE Trans. Inf. Theory, 44(1):225-240, 1998. URL: https://doi.org/10.1109/18.651026.
  3. I. Algor and Noga Alon. The star arboricity of graphs. Discret. Math., 75(1-3):11-22, 1989. URL: https://doi.org/10.1016/0012-365X(89)90073-3.
  4. Noga Alon. Covering graphs by the minimum number of equivalence relations. Combinatorica, 6(3):201-206, 1986. Google Scholar
  5. Noga Alon and Ryan Alweiss. On the product dimension of clique factors. European Journal of Combinatorics, 86:103097, 2020. Google Scholar
  6. Noga Alon, Lajos Rónyai, and Tibor Szabó. Norm-graphs: Variations and applications. J. Comb. Theory, Ser. B, 76(2):280-290, 1999. URL: https://doi.org/10.1006/jctb.1999.1906.
  7. James Aspnes, Richard Beigel, Merrick L. Furst, and Steven Rudich. The expressive power of voting polynomials. In 23rd Annual ACM Symposium on Theory of Computing, pages 402-409, New Orleans, LA, USA, May 6-8 1991. ACM Press. URL: https://doi.org/10.1145/103418.103461.
  8. Amos Beimel, Yuval Ishai, Ranjit Kumaresan, and Eyal Kushilevitz. On the cryptographic complexity of the worst functions. In Yehuda Lindell, editor, TCC 2014: 11th Theory of Cryptography Conference, volume 8349 of Lecture Notes in Computer Science, pages 317-342, San Diego, CA, USA, February 24-26 2014. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-642-54242-8_14.
  9. Alexander R. Block, Hemanta K. Maji, and Hai H. Nguyen. Secure computation based on leaky correlations: High resilience setting. In Jonathan Katz and Hovav Shacham, editors, Advances in Cryptology - CRYPTO 2017, Part II, volume 10402 of Lecture Notes in Computer Science, pages 3-32, Santa Barbara, CA, USA, August 20-24 2017. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-319-63715-0_1.
  10. Andrej Bogdanov and Elchanan Mossel. On extracting common random bits from correlated sources. IEEE Trans. Inf. Theory, 57(10):6351-6355, 2011. URL: https://doi.org/10.1109/TIT.2011.2134067.
  11. Béla Bollobás. Extremal graph theory. Courier Corporation, 2004. Google Scholar
  12. W. G. Brown. On graphs that do not contain a thomsen graph. Canadian Mathematical Bulletin, 9(3):281–285, 1966. URL: https://doi.org/10.4153/CMB-1966-036-2.
  13. Ignacio Cascudo, Ivan Damgård, Felipe Lacerda, and Samuel Ranellucci. Oblivious transfer from any non-trivial elastic noisy channel via secret key agreement. In Martin Hirt and Adam D. Smith, editors, TCC 2016-B: 14th Theory of Cryptography Conference, Part I, volume 9985 of Lecture Notes in Computer Science, pages 204-234, Beijing, China, October 31 - November 3 2016. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-662-53641-4_9.
  14. Siu On Chan, Elchanan Mossel, and Joe Neeman. On extracting common random bits from correlated sources on large alphabets. IEEE Trans. Inf. Theory, 60(3):1630-1637, 2014. URL: https://doi.org/10.1109/TIT.2014.2301155.
  15. G. Chen, S. Fujita, A. Gyarfas, J. Lehel, and A. Toth. Around a biclique cover conjecture, 2012. URL: http://arxiv.org/abs/1212.6861.
  16. Claude Crépeau and Joe Kilian. Achieving oblivious transfer using weakened security assumptions (extended abstract). In 29th Annual Symposium on Foundations of Computer Science, pages 42-52, White Plains, NY, USA, October 24-26 1988. IEEE Computer Society Press. URL: https://doi.org/10.1109/SFCS.1988.21920.
  17. Claude Crépeau and Joe Kilian. Weakening security assumptions and oblivious transfer (abstract). In Shafi Goldwasser, editor, Advances in Cryptology - CRYPTO'88, volume 403 of Lecture Notes in Computer Science, pages 2-7, Santa Barbara, CA, USA, August 21-25 1990. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/0-387-34799-2_1.
  18. Claude Crépeau, Kirill Morozov, and Stefan Wolf. Efficient unconditional oblivious transfer from almost any noisy channel. In Carlo Blundo and Stelvio Cimato, editors, SCN 04: 4th International Conference on Security in Communication Networks, volume 3352 of Lecture Notes in Computer Science, pages 47-59, Amalfi, Italy, September 8-10 2005. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-540-30598-9_4.
  19. Ivan Damgård, Joe Kilian, and Louis Salvail. On the (im)possibility of basing oblivious transfer and bit commitment on weakened security assumptions. In Jacques Stern, editor, Advances in Cryptology - EUROCRYPT'99, volume 1592 of Lecture Notes in Computer Science, pages 56-73, Prague, Czech Republic, May 2-6 1999. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/3-540-48910-X_5.
  20. Paul Erdös and Joel Spencer. Probabilistic methods in combinatorics, volume 17. Academic Press New York, 1974. Google Scholar
  21. Herbert Fleischner, Egbert Mujuni, Daniël Paulusma, and Stefan Szeider. Covering graphs with few complete bipartite subgraphs. Theoretical Computer Science, 410(21):2045-2053, 2009. URL: https://doi.org/10.1016/j.tcs.2008.12.059.
  22. DJ Foulis. Empirical logic, xeroxed course notes. University of Massachusetts, Amherst, Massachusetts (1969-1970), 1969. Google Scholar
  23. Alan Frieze and Michał Karoński. Introduction to random graphs. Cambridge University Press, 2016. Google Scholar
  24. Zoltán Füredi and Miklós Simonovits. The history of degenerate (bipartite) extremal graph problems. In Erdős Centennial, pages 169-264. Springer, 2013. Google Scholar
  25. Peter Gács and János Körner. Common information is far less than mutual information. Problems of Control and Information Theory, 2(2):149-162, 1973. Google Scholar
  26. Mikael Goldmann. On the power of a threshold gate at the top. Inf. Process. Lett., 63(6):287-293, 1997. URL: https://doi.org/10.1016/S0020-0190(97)00141-5.
  27. Oded Goldreich, Silvio Micali, and Avi Wigderson. How to play any mental game or A completeness theorem for protocols with honest majority. In Alfred Aho, editor, 19th Annual ACM Symposium on Theory of Computing, pages 218-229, New York City, NY, USA, May 25-27 1987. ACM Press. URL: https://doi.org/10.1145/28395.28420.
  28. Daniel Gonçalves and Pascal Ochem. On star and caterpillar arboricity. Discret. Math., 309(11):3694-3702, 2009. URL: https://doi.org/10.1016/j.disc.2008.01.041.
  29. Parikshit Gopalan and Rocco A. Servedio. Learning and lower bounds for ac^0 with threshold gates. In Maria J. Serna, Ronen Shaltiel, Klaus Jansen, and José D. P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010. Proceedings, volume 6302 of Lecture Notes in Computer Science, pages 588-601. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-15369-3_44.
  30. Richard Hammack, Wilfried Imrich, and Sandi Klavžar. Handbook of product graphs. CRC press, 2011. Google Scholar
  31. Chinh T. Hoàng and Van Bang Le. P_4-Colorings and P_4-Bipartite Graphs. Discrete Mathematics and Theoretical Computer Science, 4(2):109-122, 2001. URL: https://hal.inria.fr/hal-00958951.
  32. Russell Impagliazzo, Leonid A. Levin, and Michael Luby. Pseudo-random generation from one-way functions (extended abstracts). In 21st Annual ACM Symposium on Theory of Computing, pages 12-24, Seattle, WA, USA, May 15-17 1989. ACM Press. URL: https://doi.org/10.1145/73007.73009.
  33. Jeffrey C. Jackson, Adam Klivans, and Rocco A. Servedio. Learnability beyond AC0. In 34th Annual ACM Symposium on Theory of Computing, pages 776-784, Montréal, Québec, Canada, May 19-21 2002. ACM Press. URL: https://doi.org/10.1145/509907.510018.
  34. Minghui Jiang. Trees, paths, stars, caterpillars and spiders. Algorithmica, 80(6):1964-1982, 2018. Google Scholar
  35. Stasys Jukna. Boolean Function Complexity: Advances and Frontiers. Springer Publishing Company, Incorporated, 2012. Google Scholar
  36. Heinz A Jung. On a class of posets and the corresponding comparability graphs. Journal of Combinatorial Theory, Series B, 24(2):125-133, 1978. Google Scholar
  37. Sebastian Kaiser. Biclustering: methods, software and application. PhD thesis, lmu, 2011. Google Scholar
  38. Richard M. Karp. Reducibility among combinatorial problems. In Raymond E. Miller and James W. Thatcher, editors, Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA, The IBM Research Symposia Series, pages 85-103. Plenum Press, New York, 1972. URL: https://doi.org/10.1007/978-1-4684-2001-2_9.
  39. Dakshita Khurana, Hemanta K. Maji, and Amit Sahai. Secure computation from elastic noisy channels. In Marc Fischlin and Jean-Sébastien Coron, editors, Advances in Cryptology - EUROCRYPT 2016, Part II, volume 9666 of Lecture Notes in Computer Science, pages 184-212, Vienna, Austria, May 8-12 2016. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-662-49896-5_7.
  40. Joe Kilian. Founding cryptography on oblivious transfer. In 20th Annual ACM Symposium on Theory of Computing, pages 20-31, Chicago, IL, USA, May 2-4 1988. ACM Press. URL: https://doi.org/10.1145/62212.62215.
  41. Joe Kilian. A general completeness theorem for two-party games. In 23rd Annual ACM Symposium on Theory of Computing, pages 553-560, New Orleans, LA, USA, May 6-8 1991. ACM Press. URL: https://doi.org/10.1145/103418.103475.
  42. Joe Kilian. More general completeness theorems for secure two-party computation. In 32nd Annual ACM Symposium on Theory of Computing, pages 316-324, Portland, OR, USA, May 21-23 2000. ACM Press. URL: https://doi.org/10.1145/335305.335342.
  43. János Kollár, Lajos Rónyai, and Tibor Szabó. Norm-graphs and bipartite turán numbers. Combinatorica, 16(3):399-406, 1996. URL: https://doi.org/10.1007/bf01261323.
  44. Eyal Kushilevitz and Noam Nisan. Communication complexity. Cambridge University Press, 1997. Google Scholar
  45. H Lerchs. On cliques and kernels. Department of Computer Science, University of Toronto, 1971. Google Scholar
  46. H Lerchs. On the clique-kernel structure of graphs. Dept. of Computer Science, University of Toronto, 1972. Google Scholar
  47. László Lovász, J Nešetšil, and Ales Pultr. On a product dimension of graphs. Journal of Combinatorial Theory, Series B, 29(1):47-67, 1980. Google Scholar
  48. Sara C Madeira and Arlindo L Oliveira. Biclustering algorithms for biological data analysis: a survey. IEEE/ACM transactions on computational biology and bioinformatics, 1(1):24-45, 2004. Google Scholar
  49. Ueli M. Maurer. Perfect cryptographic security from partially independent channels. In 23rd Annual ACM Symposium on Theory of Computing, pages 561-571, New Orleans, LA, USA, May 6-8 1991. ACM Press. URL: https://doi.org/10.1145/103418.103476.
  50. Ueli M. Maurer. A universal statistical test for random bit generators. Journal of Cryptology, 5(2):89-105, January 1992. URL: https://doi.org/10.1007/BF00193563.
  51. Ueli M. Maurer. Secret key agreement by public discussion from common information. IEEE Trans. Inf. Theory, 39(3):733-742, 1993. URL: https://doi.org/10.1109/18.256484.
  52. Elchanan Mossel and Ryan O'Donnell. Coin flipping from a cosmic source: On error correction of truly random bits. Random Structures & Algorithms, 26(4):418-436, 2005. URL: https://doi.org/10.1002/rsa.20062.
  53. Elchanan Mossel, Ryan O'Donnell, Oded Regev, Jeffrey E Steif, and Benny Sudakov. Non-interactive correlation distillation, inhomogeneous markov chains, and the reverse bonami-beckner inequality. Israel Journal of Mathematics, 154(1):299-336, 2006. Google Scholar
  54. J Nešetřil and Ales Pultr. A dushnik-miller type dimension of graphs and its complexity. In International Conference on Fundamentals of Computation Theory, pages 482-493. Springer, 1977. Google Scholar
  55. Jaroslav Nešetřil and Vojtěch Rōdl. A simple proof of the galvin-ramsey property of the class of all finite graphs and a dimension of a graph. Discrete Mathematics, 23(1):49-55, 1978. Google Scholar
  56. Noam Nisan and David Zuckerman. More deterministic simulation in logspace. In 25th Annual ACM Symposium on Theory of Computing, pages 235-244, San Diego, CA, USA, May 16-18 1993. ACM Press. URL: https://doi.org/10.1145/167088.167162.
  57. James Orlin. Contentment in graph theory: Covering graphs with cliques. Indagationes Mathematicae (Proceedings), 80(5):406-424, 1977. URL: https://doi.org/10.1016/1385-7258(77)90055-5.
  58. Trevor Pinto. Biclique covers and partitions. arXiv preprint arXiv:1307.6363, 2013. Google Scholar
  59. Svatopluk Poljak, D Rödl, and Ales Pultr. On a product dimension of bipartite graphs. Journal of graph theory, 7(4):475-486, 1983. Google Scholar
  60. Dieter Seinsche. On a property of the class of n-colorable graphs. Journal of Combinatorial Theory, Series B, 16(2):191-193, 1974. Google Scholar
  61. Claude E Shannon. A mathematical theory of communication. The Bell system technical journal, 27(3):379-423, 1948. Google Scholar
  62. David P Sumner. Dacey graphs. Journal of the Australian Mathematical Society, 18(4):492-502, 1974. Google Scholar
  63. Douglas Brent West et al. Introduction to graph theory, volume 2. Prentice hall Upper Saddle River, NJ, 1996. Google Scholar
  64. Jürg Wullschleger. Oblivious-transfer amplification. In Moni Naor, editor, Advances in Cryptology - EUROCRYPT 2007, volume 4515 of Lecture Notes in Computer Science, pages 555-572, Barcelona, Spain, May 20-24 2007. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-540-72540-4_32.
  65. Jürg Wullschleger. Oblivious transfer from weak noisy channels. In Omer Reingold, editor, TCC 2009: 6th Theory of Cryptography Conference, volume 5444 of Lecture Notes in Computer Science, pages 332-349. Springer, Heidelberg, Germany, March 15-17 2009. URL: https://doi.org/10.1007/978-3-642-00457-5_20.
  66. Aaron Wyner. The common information of two dependent random variables. IEEE Transactions on Information Theory, 21(2):163-179, 1975. URL: https://doi.org/10.1109/TIT.1975.1055346.
  67. Ke Yang. On the (im)possibility of non-interactive correlation distillation. In Martin Farach-Colton, editor, LATIN 2004: Theoretical Informatics, 6th Latin American Symposium, volume 2976 of Lecture Notes in Computer Science, pages 222-231, Buenos Aires, Argentina, April 5-8 2004. Springer, Heidelberg, Germany. Google Scholar
  68. Andrew Chi-Chih Yao. Protocols for secure computations (extended abstract). In 23rd Annual Symposium on Foundations of Computer Science, pages 160-164, Chicago, Illinois, November 3-5 1982. IEEE Computer Society Press. URL: https://doi.org/10.1109/SFCS.1982.38.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact