Hiding cliques for cryptographic security

被引:49
作者
Juels, A
Peinado, M
机构
[1] RSA Labs, Bedford, MA 01730 USA
[2] Microsoft Corp, Redmond, WA 98052 USA
基金
美国国家科学基金会;
关键词
graph-based crypto systems; random graphs; cliques;
D O I
10.1023/A:1008374125234
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We demonstrate how a well studied combinatorial optimization problem may be used as a new cryptographic primitive. The problem in question is that of finding a "large" clique in a random graph. While the largest clique in a random graph with n vertices and edge probability p is very likely to be of size about 2 log(1/p)n, it is widely conjectured that no polynomial-time algorithm exists which finds a clique of size greater than or equal to (1 + epsilon)\log(1/p)n with significant probability for any constant epsilon > 0. We present a very simple method of exploiting this conjecture by "hiding'' large cliques in random graphs. In particular, we show that if the conjecture is true, then when a large clique-of size, say, (1 + 2 epsilon) log(1/p)n-is randomly inserted ("hidden'') in a random graph, finding a clique of size greater than or equal to (1 + epsilon)\log(1/p)n remains hard. Our analysis also covers the case of high edge probabilities which allows us to insert cliques of size up to n(1/4-epsilon) (epsilon>0). Our result suggests several cryptographic applications, such as a simple one-way function.
引用
收藏
页码:269 / 280
页数:12
相关论文
共 32 条
[1]  
Alon N., 1998, P 9 ANN ACM SIAM S D
[2]  
ALON N, 1992, PROBABILISTIC METHOD
[3]  
Arora S., 1992, Proceedings 33rd Annual Symposium on Foundations of Computer Science (Cat. No.92CH3188-0), P14, DOI 10.1109/SFCS.1992.267823
[4]  
Bellare M, 1995, AN S FDN CO, P422, DOI 10.1109/SFCS.1995.492573
[5]  
Bellare M., 1994, Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, P184, DOI 10.1145/195058.195129
[6]  
BELLARE M, 1993, P 25 ANN ACM S THEOR
[7]   COLORING RANDOM AND SEMI-RANDOM K-COLORABLE GRAPHS [J].
BLUM, A ;
SPENCER, J .
JOURNAL OF ALGORITHMS, 1995, 19 (02) :204-234
[8]  
Bollobas B, 1985, RANDOM GRAPHS
[9]  
Boppana R, 1987, P 28 IEEE S FDN COMP, P280
[10]  
BUI T, 1986, COMBINATORICA, V6