Hiding cliques for cryptographic security
DOI10.1023/A:1008374125234zbMATH Open0965.94015OpenAlexW3139080059MaRDI QIDQ1581792FDOQ1581792
Authors: Ari Juels, Marcus Peinado 
Publication date: 5 August 2001
Published in: Designs, Codes and Cryptography (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1023/a:1008374125234
Recommendations
combinatorial optimizationone-way functionrandom graphscliquescryptographic primitivegraph-based cryptosystems
Random graphs (graph-theoretic aspects) (05C80) Cryptography (94A60) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cited In (19)
- Clustering and Categorization Applied to Cryptanalysis
- The Ehrenfeucht-Fraïssé method and the planted clique conjecture
- Computational barriers in minimax submatrix detection
- Finding hidden cliques in linear time with high probability
- Cryptography from planted graphs: security with logarithmic-size messages
- Finding a planted clique by adaptive probing
- Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning
- Perfect structure on the edge of chaos. Trapdoor permutations from indistinguishability obfuscation
- A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
- On the hardness of designing public signals
- \(k\)-SUM in the sparse regime: complexity and applications
- Hardness self-amplification: simplified, optimized, and unified
- The Complexity of Public-Key Cryptography
- The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs
- Convex optimization for the densest subgraph and densest submatrix problems
- Optimal detection of sparse principal components in high dimension
- White-box vs. black-box complexity of search problems: Ramsey and graph property testing
- Fixed-Parameter Tractability of the (1 + 1) Evolutionary Algorithm on Random Planted Vertex Covers
- Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation
This page was built for publication: Hiding cliques for cryptographic security
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1581792)
