nach oben

Erschienen in:

2025 | OriginalPaper | Buchkapitel

Low-Degree Security of the Planted Random Subgraph Problem

verfasst von : Andrej Bogdanov, Chris Jones, Alon Rosen, Ilias Zadik

Erschienen in: Theory of Cryptography

Verlag: Springer Nature Switzerland

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

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

Nächstes Kapitel 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)

Titel: Low-Degree Security of the Planted Random Subgraph Problem
verfasst von: Andrej Bogdanov
Chris Jones
Alon Rosen
Ilias Zadik
Verlag: Springer Nature Switzerland
Buch: Theory of Cryptography
Print ISBN: 978-3-031-78016-5

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

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

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"