Hiding cliques for cryptographic security

DOI10.1023/A:1008374125234MaRDI QIDQ1581792zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

cliquescombinatorial optimizationcryptographic primitivegraph-based cryptosystemsone-way functionrandom graphs

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1303611
• scientific article; zbMATH DE number 1303602
• scientific article; zbMATH DE number 1380608
• Finding and certifying a large hidden clique in a semirandom graph
• Finding hidden cliques in linear time with high probability

Cited in

(27)

• Convex optimization for the densest subgraph and densest submatrix problems
• On the hardness of designing public signals
• Computational barriers in minimax submatrix detection
• Perfect structure on the edge of chaos. Trapdoor permutations from indistinguishability obfuscation
• The Ehrenfeucht-Fraïssé method and the planted clique conjecture
• Clustering and Categorization Applied to Cryptanalysis
• Optimal detection of sparse principal components in high dimension
• scientific article; zbMATH DE number 1303611 (Why is no real title available?)
• A nearly tight sum-of-squares lower bound for the planted clique problem
• The Complexity of Public-Key Cryptography
• Finding a planted clique by adaptive probing
• The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs
• White-box vs. black-box complexity of search problems: Ramsey and graph property testing
• Finding hidden cliques in linear time with high probability
• Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning
• Fixed-Parameter Tractability of the (1 + 1) Evolutionary Algorithm on Random Planted Vertex Covers
• Hardness self-amplification: simplified, optimized, and unified
• Cryptography from planted graphs: security with logarithmic-size messages
• \(k\)-SUM in the sparse regime: complexity and applications
• Maximum chordal subgraphs of random graphs
• Fine-grained complexity in a world without cryptography
• The average-case complexity of counting cliques in Erdős-Rényi hypergraphs
• Low-degree security of the planted random subgraph problem
• Almost-linear planted cliques elude the Metropolis process
• Exact recovery of planted cliques in semi-random graphs
• The planted orthogonal vectors problem
• 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)