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

combinatorial optimizationone-way functionrandom graphscliquescryptographic 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)

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

(19)

• Finding hidden cliques in linear time with high probability
• On the hardness of designing public signals
• The Ehrenfeucht-Fraïssé method and the planted clique conjecture
• Computational barriers in minimax submatrix detection
• Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning
• Hardness self-amplification: simplified, optimized, and unified
• Cryptography from planted graphs: security with logarithmic-size messages
• Convex optimization for the densest subgraph and densest submatrix problems
• \(k\)-SUM in the sparse regime: complexity and applications
• Optimal detection of sparse principal components in high dimension
• The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs
• Finding a planted clique by adaptive probing
• Clustering and Categorization Applied to Cryptanalysis
• White-box vs. black-box complexity of search problems: Ramsey and graph property testing
• A nearly tight sum-of-squares lower bound for the planted clique problem
• The Complexity of Public-Key Cryptography
• Fixed-Parameter Tractability of the (1 + 1) Evolutionary Algorithm on Random Planted Vertex Covers
• Perfect structure on the edge of chaos. Trapdoor permutations from indistinguishability obfuscation
• 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)