Low-degree Security of the Planted Random Subgraph Problem
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917785376915456 |
|---|---|
| author | Bogdanov, Andrej Jones, Chris Rosen, Alon Zadik, Ilias |
| author_facet | Bogdanov, Andrej Jones, Chris Rosen, Alon Zadik, Ilias |
| contents | 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 - Ω(1)}$. This improves over Abram et al.'s analysis for $k \leq n^{1/2 - Ω(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 + ε)\log n$ for any $ε> 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(ε\log n)^{1/(r-1)}$ parties. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_16227 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Low-degree Security of the Planted Random Subgraph Problem Bogdanov, Andrej Jones, Chris Rosen, Alon Zadik, Ilias Cryptography and Security Data Structures and Algorithms Statistics Theory 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 - Ω(1)}$. This improves over Abram et al.'s analysis for $k \leq n^{1/2 - Ω(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 + ε)\log n$ for any $ε> 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(ε\log n)^{1/(r-1)}$ parties. |
| title | Low-degree Security of the Planted Random Subgraph Problem |
| topic | Cryptography and Security Data Structures and Algorithms Statistics Theory |
| url | https://arxiv.org/abs/2409.16227 |