Hiding cliques for cryptographic security

DOI10.1023/A:1008374125234zbMath0965.94015OpenAlexW3139080059MaRDI QIDQ1581792

Marcus Peinado, Ari Juels

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

zbMATH Keywords

combinatorial optimizationrandom graphscliquesone-way functioncryptographic primitivegraph-based cryptosystems

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Cryptography (94A60) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (14)

Optimal detection of sparse principal components in high dimension ⋮ The Ehrenfeucht-Fraïssé Method and the Planted Clique Conjecture ⋮ Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation ⋮ Fixed-Parameter Tractability of the (1 + 1) Evolutionary Algorithm on Random Planted Vertex Covers ⋮ A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem ⋮ The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs ⋮ Finding Hidden Cliques in Linear Time with High Probability ⋮ On the hardness of designing public signals ⋮ Perfect Structure on the Edge of Chaos ⋮ Finding a planted clique by adaptive probing ⋮ Convex optimization for the densest subgraph and densest submatrix problems ⋮ The Complexity of Public-Key Cryptography ⋮ Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning ⋮ Computational barriers in minimax submatrix detection

This page was built for publication: Hiding cliques for cryptographic security