Low-degree security of the planted random subgraph problem

DOI10.1007/978-3-031-78017-2_9MaRDI QIDQ6952847zbMATH OpenFDO

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

Publication date 25 July 2025

Full work available at URL https://doi.org/10.1007/978-3-031-78017-2_9

zbMATH Keywords

cryptographic primitivesinformation-theoretic securityrandom subgraph detection conjecturesecret-sharing scheme

Mathematics Subject Classification ID

Hypergraphs (05C65) Random graphs (graph-theoretic aspects) (05C80) Cryptography (94A60)

Cites work

• A minimal model for secure computation (extended abstract)
• A nearly tight sum-of-squares lower bound for the planted clique problem
• A new approach to the planted clique problem
• Almost-Linear Planted Cliques Elude the Metropolis Process
• Conditional disclosure of secrets via non-linear reconstruction
• Cryptography from planted graphs: security with logarithmic-size messages
• Expected complexity of graph partitioning problems
• Hiding cliques for cryptographic security
• scientific article; zbMATH DE number 1380608 (Why is no real title available?)
• Large Cliques Elude the Metropolis Process
• Lower bounds for secret-sharing schemes for \(k\)-hypergraphs
• Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
• Secret-sharing schemes for general and uniform access structures
• Statistical algorithms and a lower bound for detecting planted cliques
• The communication complexity of private simultaneous messages, revisited
• The size of a share must be large
• Threshold secret sharing requires a linear-size alphabet

Cited in

(1)

• Multiparty distributed point functions

This page was built for publication: Low-degree security of the planted random subgraph problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6952847)