Cryptography from planted graphs: security with logarithmic-size messages
From MaRDI portal
Publication:6581792
DOI10.1007/978-3-031-48615-9_11zbMATH Open1544.94211MaRDI QIDQ6581792
Amos Beimel, Eyal Kushilevitz, Damiano Abram, Yuval Ishai, Varun Narayanan
Publication date: 1 August 2024
Graph theory (including graph drawing) in computer science (68R10) Cryptography (94A60) Data encryption (aspects in computer science) (68P25) Information theory (general) (94A15) Authentication, digital signatures and secret sharing (94A62)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Optimal detection of sparse principal components in high dimension
- Nuclear norm minimization for the planted clique and biclique problems
- Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
- Secret sharing schemes for graph-based prohibited structures
- Expected complexity of graph partitioning problems
- Hiding cliques for cryptographic security
- Proofs of Work from worst-case assumptions
- Conditional disclosure of secrets via non-linear reconstruction
- Local algorithms for independent sets are half-optimal
- Distributed (correlation) samplers: how to remove a trusted dealer in one round
- Worst-case hardness for LPN and cryptographic hashing via code smoothing
- Computational barriers in minimax submatrix detection
- Computational and statistical boundaries for submatrix localization in a large noisy matrix
- Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices
- Secure communications over insecure channels
- Improved non-approximability results
- A minimal model for secure computation (extended abstract)
- Corrigendum to: ``Efficient probabilistic checkable proofs and applications to approximation
- Public-key cryptography from different assumptions
- Sum-of-squares Lower Bounds for Planted Clique
- How to Generate and Use Universal Samplers
- Incoherence-Optimal Matrix Completion
- Hidden Cliques and the Certification of the Restricted Isometry Property
- How Hard Is It to Approximate the Best Nash Equilibrium?
- On the probable behaviour of some algorithms for finding the stability number of a graph
- How to share a secret
- On independent sets in random graphs
- Large Cliques Elude the Metropolis Process
- On colouring random graphs
- Cliques in random graphs
- Interactive proofs and the hardness of approximating cliques
- On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique
- A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
- The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set
- On the Power of Correlated Randomness in Secure Computation
- Finding and certifying a large hidden clique in a semirandom graph
- Reducibility among Combinatorial Problems
- Finding cliques using few probes
- The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs
- Feeling the Bern: Adaptive Estimators for Bernoulli Probabilities of Pairwise Comparisons
- Clique is hard on average for regular resolution
- Bounds on the Threshold Gap in Secret Sharing and its Applications
- Finding Hidden Cliques in Linear Time with High Probability
- Statistical algorithms and a lower bound for detecting planted cliques
- On the Cryptographic Complexity of the Worst Functions
- Limits of local algorithms over sparse random graphs
- The communication complexity of private simultaneous messages, revisited
- Programmable distributed point functions
- Succinct computational secret sharing
- Cryptography from planted graphs: security with logarithmic-size messages
Related Items (1)
This page was built for publication: Cryptography from planted graphs: security with logarithmic-size messages
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6581792)
