Cryptography from planted graphs: security with logarithmic-size messages

DOI10.1007/978-3-031-48615-9_11MaRDI QIDQ6581792zbMATH OpenFDO

Authors Damiano Abram, Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Varun Narayanan

Publication date 1 August 2024

Full work available at URL https://doi.org/10.1007/978-3-031-48615-9_11

zbMATH Keywords

information-theoretic securitysecret-sharing schemecryptographic primitives

Mathematics Subject Classification ID

Data encryption (aspects in computer science) (68P25) Graph theory (including graph drawing) in computer science (68R10) Information theory (general) (94A15) Cryptography (94A60) Authentication, digital signatures and secret sharing (94A62)

Recommendations

• Hiding cliques for cryptographic security
• scientific article; zbMATH DE number 1303611
• On the Cryptographic Complexity of the Worst Functions
• The complexity of multiparty PSM protocols and related models
• Secret-sharing schemes for very dense graphs

Cites work

• scientific article; zbMATH DE number 5485485 (Why is no real title available?)
• scientific article; zbMATH DE number 3689411 (Why is no real title available?)
• scientific article; zbMATH DE number 1256714 (Why is no real title available?)
• scientific article; zbMATH DE number 1256635 (Why is no real title available?)
• scientific article; zbMATH DE number 1256636 (Why is no real title available?)
• scientific article; zbMATH DE number 1306875 (Why is no real title available?)
• scientific article; zbMATH DE number 1380608 (Why is no real title available?)
• scientific article; zbMATH DE number 5485586 (Why is no real title available?)
• scientific article; zbMATH DE number 7829297 (Why is no real title available?)
• A minimal model for secure computation (extended abstract)
• A nearly tight sum-of-squares lower bound for the planted clique problem
• Bounds on the Threshold Gap in Secret Sharing and its Applications
• Clique is hard on average for regular resolution
• Cliques in random graphs
• Computational and statistical boundaries for submatrix localization in a large noisy matrix
• Computational barriers in minimax submatrix detection
• Conditional disclosure of secrets via non-linear reconstruction
• Corrigendum to: ``Efficient probabilistic checkable proofs and applications to approximation
• Cryptography from planted graphs: security with logarithmic-size messages
• Distributed (correlation) samplers: how to remove a trusted dealer in one round
• Expected complexity of graph partitioning problems
• Feeling the Bern: Adaptive Estimators for Bernoulli Probabilities of Pairwise Comparisons
• Finding and certifying a large hidden clique in a semirandom graph
• Finding cliques using few probes
• Finding hidden cliques in linear time
• Finding hidden cliques in linear time with high probability
• Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
• Hidden Cliques and the Certification of the Restricted Isometry Property
• Hiding cliques for cryptographic security
• How Hard Is It to Approximate the Best Nash Equilibrium?
• How to Generate and Use Universal Samplers
• How to share a secret
• Improved non-approximability results
• Incoherence-Optimal Matrix Completion
• Interactive proofs and the hardness of approximating cliques
• Large Cliques Elude the Metropolis Process
• Limits of local algorithms over sparse random graphs
• Local algorithms for independent sets are half-optimal
• Nuclear norm minimization for the planted clique and biclique problems
• On colouring random graphs
• On the Cryptographic Complexity of the Worst Functions
• On the integrality gap of degree-4 sum of squares for planted clique
• On the power of correlated randomness in secure computation
• On the probable behaviour of some algorithms for finding the stability number of a graph
• Optimal detection of sparse principal components in high dimension
• Programmable distributed point functions
• Proofs of Work from worst-case assumptions
• Public-key cryptography from different assumptions
• Reducibility among combinatorial problems
• Secret sharing schemes for graph-based prohibited structures
• Secure communications over insecure channels
• Statistical algorithms and a lower bound for detecting planted cliques
• Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices
• Succinct computational secret sharing
• Sum-of-squares Lower Bounds for Planted Clique
• The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs
• The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set
• The communication complexity of private simultaneous messages, revisited
• Worst-case hardness for LPN and cryptographic hashing via code smoothing

Cited in

(4)

• Low-degree security of the planted random subgraph problem
• Secret-sharing schemes for high slices
• Cryptography from planted graphs: security with logarithmic-size messages
• Multiparty distributed point functions

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)