Joint encryption and message-efficient secure computation

被引:40
作者
Franklin, M [1 ]
Haber, S [1 ]
机构
[1] BELLCORE, MORRISTOWN, NJ 07960 USA
关键词
secure computation; privacy; group-oriented cryptography; distributed computing; communication complexity;
D O I
10.1007/s001459900013
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
This paper addresses the message complexity of secure computation in the (passive adversary) privacy setting. We show that O(nC) encrypted bits of communication suffice for n parties to evaluate any boolean circuit of size C privately, under a specific cryptographic assumption. This work establishes a connection between secure distributed computation and group-oriented cryptography, i.e., cryptographic methods in which subsets of individuals can act jointly as single agents. Our secure computation protocol relies on a new group-oriented probablistic public-key encryption scheme with useful algebraic properties.
引用
收藏
页码:217 / 232
页数:16
相关论文
共 14 条
[1]  
CHAUM D, 1988, LECT NOTES COMPUT SC, V293, P87
[2]  
DESMEDT Y, 1990, LECT NOTES COMPUT SC, V435, P307
[3]  
Desmedt Y., 1987, LNCS, V293, P120, DOI DOI 10.1007/3-540-48184-2
[4]   NEW DIRECTIONS IN CRYPTOGRAPHY [J].
DIFFIE, W ;
HELLMAN, ME .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1976, 22 (06) :644-654
[5]   A PUBLIC KEY CRYPTOSYSTEM AND A SIGNATURE SCHEME BASED ON DISCRETE LOGARITHMS [J].
ELGAMAL, T .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1985, 31 (04) :469-472
[6]  
GALIL Z, 1987, LNCS, V293, P135
[7]  
Goldreich O., 1987, P 19 ANN ACM S THEOR, V87, P218, DOI DOI 10.1145/28395.28420
[8]  
GOLDREICH O, 1987, LNCS, V293, P73
[9]   PROBABILISTIC ENCRYPTION [J].
GOLDWASSER, S ;
MICALI, S .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1984, 28 (02) :270-299
[10]  
McCurley K. S., 1988, Journal of Cryptology, V1, P95, DOI 10.1007/BF02351718