Randomness in distribution protocols

被引：27
作者：
Blundo, C
DeSantis, A
Vaccaro, U
机构：
[1] Dipto. di Info. ed Applicazioni, Università di Salerno
来源：
INFORMATION AND COMPUTATION | 1996年 / 131卷 / 02期
关键词：
D O I：
10.1006/inco.1996.0095
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
Randomness is a useful computation resource due to its ability to enhance the capabilities of other resources. its interaction with resources such as time, space, interaction with provers and its role in several areas of computer science has been extensively studied. In this paper we give a systematic analysis of the amount of randomness needed by secret sharing schemes and secure key distribution schemes. We give both upper and lower bounds on the number of random bits needed by secret sharing schemes. The bounds are tight for several classes of secret sharing schemes. For secure key distribution schemes we provide a lower bound on the amount of randomness needed, thus showing the optimality of a recently proposed key distribution protocol. (C) 1996 Academic Press.
引用
收藏
页码：111 / 139
页数：29
相关论文
共 41 条
[1]  
ARORA S, 1992, AN S FDN CO, P14
[2]  
Bellare M, 1995, AN S FDN CO, P422, DOI 10.1109/SFCS.1995.492573
[3]  
Bellare M., 1994, Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, P184, DOI 10.1145/195058.195129
[4]  
Ben-Or Michael, 1988, P 20 ANN ACM S THEOR, P1, DOI DOI 10.1145/62212.62213
[5]  
BLAKLEY G, 1979, 1979 P AFIPS NAT COM, P313
[6]  
BLAKLEY GR, 1985, ADV CRYPTOLOGY, V196, P411
[7]  
BLOM R, 1985, LECT NOTES COMPUT SC, V209, P335
[8]   On the information rate of secret sharing schemes [J].
Blundo, C ;
DeSantis, A ;
Gargano, L ;
Vaccaro, U .
THEORETICAL COMPUTER SCIENCE, 1996, 154 (02) :283-306
[9]  
Blundo C., 1995, LECT NOTES COMPUTER, V950, P35, DOI 10.1007/BFb0053422
[10]  
BLUNDO C, 1993, LECTURE NOTES COMPUT, V665, P692
12345