Welcome to the resource topic for
**2024/1497**

**Title:**

Low-degree Security of the Planted Random Subgraph Problem

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

**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 Erdos-Renyi 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\leq n^{1 - \Omega(1)}. This improves over Abram et al.'s analysis for k \leq n^{1/2 - \Omega(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.

**ePrint:**
https://eprint.iacr.org/2024/1497

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .