Top

Published in:

2025 | OriginalPaper | Chapter

Low-Degree Security of the Planted Random Subgraph Problem

Authors : Andrej Bogdanov, Chris Jones, Alon Rosen, Ilias Zadik

Published in: Theory of Cryptography

Publisher: Springer Nature Switzerland

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The planted random subgraph detection conjecture of Abram et al. (TCC 2023) asserts the pseudorandomness of a pair of graphs (H, G), where G is an Erdős-Rényi random graph on n vertices, and H is a random induced subgraph of G on k vertices. Assuming the hardness of distinguishing these two distributions (with two leaked vertices), Abram et al. construct communication-efficient, computationally secure (1) 2-party private simultaneous messages (PSM) and (2) secret sharing for forbidden graph structures.

We prove the low-degree hardness of detecting planted random subgraphs all the way up to \(k\le n^{1 - \varOmega (1)}\). This improves over Abram et al.’s analysis for \(k \le n^{1/2 - \varOmega (1)}\). The hardness extends to r-uniform hypergraphs for constant r.

Our analysis is tight in the distinguisher’s degree, its advantage, and in the number of leaked vertices. Extending the constructions of Abram et al., we apply the conjecture towards (1) communication-optimal multiparty PSM protocols for random functions and (2) bit secret sharing with share size \((1 + \epsilon )\log n\) for any \(\epsilon > 0\) in which arbitrary minimal coalitions of up to r parties can reconstruct and secrecy holds against all unqualified subsets of up to \(\ell = o(\epsilon \log n)^{1/(r-1)}\) parties.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Bit Security: Optimal Adversaries, Equivalence Results, and a Toolbox for Computational-Statistical Security Analysis

next chapter Sparse Linear Regression and Lattice Problems

A similar yet different model where one observes the union of a copy of H with an instance of G(n, 1/2) has also been recently analyzed in the statistical inference literature [Hul22, MNWS+23, YZZ24]. For this work, we solely focus on the “induced” variant, where H appears as an induced subgraph of G..

Noise-robustness means that the planted structure is resilient to small random perturbations [Hop18, HW21].

[ABF+19]

Applebaum, B., Beimel, A., Farràs, O., Nir, O., Peter, N.: Secret-sharing schemes for general and uniform access structures. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11478, pp. 441–471. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17659-4_15CrossRef

[ABI+23]

Abram, D., Beimel, A., Ishai, Y., Kushilevitz, E., Narayanan, V.: Cryptography from planted graphs: security with logarithmic-size messages. In: Theory of Cryptography Conference, pp. 286–315. Springer, Cham (2023)

[AHMS18]

Applebaum, B., Holenstein, T., Mishra, M., Shayevitz, O.: The communication complexity of private simultaneous messages, revisited. In: EUROCRYPT (2), pp. 261–286. Springer, Cham (2018)

[AKS98]

Alon, N., Krivelevich, M., Sudakov, B.: Finding a large hidden clique in a random graph. Rand. Struct. Algorithms 13(3–4), 457–466 (1998)MathSciNetCrossRef

[BB20]

Brennan, M., Bresler, G.: Reducibility and statistical-computational gaps from secret leakage. In: Abernethy, J., Agarwal, S. (eds.) Proceedings of Thirty Third Conference on Learning Theory, Proceedings of Machine Learning Research, vol. 125, pp. 648–847. PMLR (2020)

[Bei23]

Beimel, A.: Lower bounds for secret-sharing schemes for \(k\)-hypergraphs. In: 4th Conference on Information-Theoretic Cryptography (ITC 2023), vol. 267, pp. 16:1–16:13 (2023)

[BGK20]

Bogdanov, A., Guo, S., Komargodski, I.: Threshold secret sharing requires a linear-size alphabet. Theory Comput. 16(2), 1–18 (2020)MathSciNetCrossRef

[BHK+19]

Barak, B., Hopkins, S., Kelner, J., Kothari, P.K., Moitra, A., Potechin, A.: A nearly tight sum-of-squares lower bound for the planted clique problem. SIAM J. Comput. 48(2), 687–735 (2019)MathSciNetCrossRef

[CMZ23]

Chen, Z., Mossel, E., Zadik, I.: Almost-linear planted cliques elude the Metropolis process. In: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 4504–4539. SIAM (2023)

[COGHK+22]

Coja-Oghlan, A., Gebhard, O., Hahn-Klimroth, M., Wein, A.S., Zadik, I.: Statistical and computational phase transitions in group testing. In: Conference on Learning Theory, pp. 4764–4781. PMLR (2022)

[Csi97]

Csirmaz, L.: The size of a share must be large. J. Cryptol. 10(4), 223–231 (1997)MathSciNetCrossRef

[FGR+17]

Feldman, V., Grigorescu, E., Reyzin, L., Vempala, S.S., Xiao, Y.: Statistical algorithms and a lower bound for detecting planted cliques. J. ACM 64(2) (2017)

[FK08]

Frieze, A., Kannan, R.: A new approach to the planted clique problem. In: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008)

[FKN94]

Feige, U., Kilian, J., Naor, M.: A minimal model for secure computation (extended abstract). In: Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing (STOC 1994) pp. 554–563. Association for Computing Machinery, New York (1994)

[GZ19]

Gamarnik , D., Zadik, I.: The landscape of the planted clique problem: dense subgraphs and the overlap gap property. arXiv preprint arXiv:1904.07174 (2019)

[Hop18]

Hopkins, S.: Statistical Inference and the Sum of Squares Method. Ph.D. thesis, Cornell University (2018)

[HS24]

Hirahara, S., Shimizu, N.: Planted clique conjectures are equivalent. In: Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC 2024), pp. 358–366 (2024)

[Hul22]

Huleihel, W.: Inferring hidden structures in random graphs. IEEE Trans. Signal Inf. Process. Netw. 8, 855–867 (2022)MathSciNet

[HW21]

Holmgren, J., Wein, A.S.: Counterexamples to the low-degree conjecture. In: 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), vol. 185, pp. 75:1–75:9 (2021)

[Jer92]

Jerrum, M.: Large cliques elude the metropolis process. Rand. Struct. Algorithms 3, 347–360 (1992)MathSciNetCrossRef

[JP97]

Juels, A., Peinado, M.: Hiding cliques for cryptographic security. Des. Codes Crypt. 20, 11 (1997)MathSciNet

[KN90]

Kilian, J., Nisan, N.: Unpublished (1990)

[Kuc95]

Kucera, L.: Expected complexity of graph partitioning problems. Discrete Appl. Math. 57(2–3), 193–212 (1995)MathSciNetCrossRef

[KWB19]

Kunisky, D., Wein, A.S., Bandeira, A.S.: Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio. In: ISAAC Congress (International Society for Analysis, its Applications and Computation), pp. 1–50. Springer, Cham (2019)

[LVW17]

Liu, T., Vaikuntanathan, V., Wee, H.: Conditional disclosure of secrets via non-linear reconstruction. In: CRYPTO, pp. 758–790. Springer, Cham (2017)

[MNWS+23]

Mossel, E., Niles-Weed, J., Sohn, Y., Sun, N., Zadik, I.: Sharp thresholds in inference of planted subgraphs. In: The Thirty Sixth Annual Conference on Learning Theory, pp. )5573–5577. PMLR (2023)

[YZZ24]

Yu, X., Zadik, I., Zhang, P.: Counting stars is constant-degree optimal for detecting any planted subgraph. arXiv preprint arXiv:2403.17766 (2024)

[ZSWB22]

Zadik, I., Song, M.J., Wein, A.S., Bruna, J.: Lattice-based methods surpass sum-of-squares in clustering. In: Conference on Learning Theory, pp. 1247–1248. PMLR (2022)

Title: Low-Degree Security of the Planted Random Subgraph Problem
Authors: Andrej Bogdanov
Chris Jones
Alon Rosen
Ilias Zadik
Publisher: Springer Nature Switzerland
Book: Theory of Cryptography
Print ISBN: 978-3-031-78016-5

Electronic ISBN: 978-3-031-78017-2

Copyright Year: 2025
DOI: https://doi.org/10.1007/978-3-031-78017-2_9

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"