Using Linearly-Homomorphic Encryption to Evaluate Degree-2 Functions on Encrypted Data

被引:59
作者
Catalano, Dario [1 ]
Fiore, Dario [2 ]
机构
[1] Univ Catania, Catania, Italy
[2] IMDEA Software Inst, Madrid, Spain
来源
CCS'15: PROCEEDINGS OF THE 22ND ACM SIGSAC CONFERENCE ON COMPUTER AND COMMUNICATIONS SECURITY | 2015年
关键词
Homomorphic Encryption; Secure Computation; PUBLIC-KEY CRYPTOSYSTEM; MULTIPARTY COMPUTATION; SECURE;
D O I
10.1145/2810103.2813624
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
We show a technique to transform a linearly-homomorphic encryption into a scheme capable of evaluating degree-2 computations on ciphertexts. Our transformation is surprisingly simple and requires only one very mild property on the underlying linearly-homomorphic scheme: the message space must be a public ring in which it is possible to sample elements uniformly at random. This allows us to instantiate our transformation with virtually all existing number-theoretic linearly-homomorphic schemes, such as Goldwasser-Micali, Paillier, or ElGamal. Our resulting schemes achieve circuit privacy and are compact when considering a subclass of degree-2 polynomials where the number of additions of degree-2 terms is bounded by a constant. As an additional contribution we extend our technique to build a protocol for outsourcing computation on encrypted data using two (non-communicating) servers. Somewhat interestingly, in this case we can boost a linearly-homomorphic scheme to support the evaluation of any degree-2 polynomial while achieving full compactness.
引用
收藏
页码:1518 / 1529
页数:12
相关论文
共 36 条
[1]  
[Anonymous], 2014813 CRYPT EPRINT
[2]  
[Anonymous], LNCS
[3]  
[Anonymous], LNCS
[4]  
[Anonymous], 2014, ACM T COMPUTATION TH
[5]   How to Garble Arithmetic Circuits [J].
Applebaum, Benny ;
Ishai, Yuval ;
Kushilevitz, Eyal .
2011 IEEE 52ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2011), 2011, :120-129
[6]  
Boneh D, 2005, LECT NOTES COMPUT SC, V3378, P325
[7]   Short group signatures [J].
Boneh, D ;
Boyen, X ;
Shacham, H .
ADVANCES IN CRYPTOLOGY - CRYPTO 2004, PROCEEDINGS, 2004, 3152 :41-55
[8]  
Brakerski Z, 2011, LECT NOTES COMPUT SC, V6841, P505, DOI 10.1007/978-3-642-22792-9_29
[9]  
Bresson E, 2003, LECT NOTES COMPUT SC, V2894, P37
[10]  
Cachin C, 2000, LECT NOTES COMPUT SC, V1853, P512