SCIENCE CHINA Information Sciences, Volume 63 , Issue 1 : 112105(2020) https://doi.org/10.1007/s11432-018-9789-y

Polynomial AND homomorphic cryptosystem and applications

• AcceptedFeb 14, 2019
• PublishedDec 25, 2019
Share
Rating

Abstract

Homomorphic cryptosystems are fundamental and highly effective cryptographic primitives for addressing security problems arising in information processing, data analysis and data applications, particularly in secure cloud computing and secure multiparty computation. To privately compute functions such as $E(x_1\wedge~\cdots\wedge~x_t)$, $E(x_1\vee~\cdots\vee~x_t)$ and $E[(x_{11}\wedge\cdots~\wedge~x_{m1})\vee~\cdots~\vee(x_{1n}\wedge~\cdots~\wedge~x_{mn})]$ ($m$ disjunctive normal form ($m$DNF)) on $E(x_1),\ldots,~E(x_t)$ and $E(x_{11}),\ldots,~E(x_{mn})$ without knowing the decryption key, Boolean homomorphic cryptosystems are necessary. Exploring new homomorphic cryptosystems to solve these problems is appealing, and is of high theoretical and practical significance. To solve problems such as these, we propose a polynomial AND homomorphic cryptosystem based on the ideal theory of abstract algebra; the scheme can be obtained from available multiplicatively homomorphic cryptosystems such as the ElGamal. We prove that the cryptosystem is semantically secure. This polynomial AND homomorphic cryptosystem is a highly effective tool for designing various cryptographic protocols. As examples, we demonstrate its applications to privately compute any DNF (i.e., $P(X_1,\ldots,~X_m)~=E[(x_{11}\wedge\cdots~\wedge~x_{m1})\vee~\cdots~\vee(x_{1n}\wedge~\cdots~\wedge~x_{mn})]$ on ciphertexts $E(x_{ij})$ of $x_{ij}$ without knowing the decryption key) and the intersection and union of certain private sets.

References

[1] Rivest R L, Adleman L, Dertouzos M L. On data banks and privacy homomorphisms. Found Secure Comput, 1978, 4: 169--180. Google Scholar

[2] López-Alt A, Tromer E, Vaikuntanathan V. On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption. In: Proceedings of the 44th ACM Symposium on Theory of Computing, 2012. 1219--1234. Google Scholar

[3] Atayero A A, Feyisetan O. Security issues in cloud computing: The potentials of homomorphic encryption. J Emerg Trends Comput Inf Sci, 2011, 2: 546--552. Google Scholar

[4] Zhang R, Ma H, Lu Y. Provably secure cloud storage for mobile networks with less computation and smaller overhead. Sci China Inf Sci, 2017, 60: 122104 CrossRef Google Scholar

[5] Kuang L W, Yang L T, Feng J. Secure Tensor Decomposition Using Fully Homomorphic Encryption Scheme. IEEE Trans Cloud Comput, 2018, 6: 868-878 CrossRef Google Scholar

[6] Anunay K, Akshay R, Matthew D. Cryptographically Secure Multiparty Computation and Distributed Auctions Using Homomorphic Encryption. Cryptography, 2017, 1: 25 CrossRef Google Scholar

[7] Lin H Y, Tzeng W G. An efficient solution to the millionaires' problem based on homomorphic encryption. In: Proceedings of the 3rd International Conference Applied Cryptography and Network Security, 2005. 456--466. Google Scholar

[8] Jiang B, Zhang Y. Securely min and k-th min computations with fully homomorphic encryption. Sci China Inf Sci, 2018, 61: 058103 CrossRef Google Scholar

[9] Wang W, Hu Y, Chen L. Exploring the Feasibility of Fully Homomorphic Encryption. IEEE Trans Comput, 2015, 64: 698-706 CrossRef Google Scholar

[10] Cramer R, Damgård I B, Nielsen J B. Secure Multiparty Computation. Cambridge: Cambridge University Press, 2015. Google Scholar

[11] Rivest R L, Shamir A, Adleman L. A method for obtaining digital signatures and public-key cryptosystems. Commun ACM, 1978, 21: 120-126 CrossRef Google Scholar

[12] ElGamal T. A public key cryptosystem and a signature scheme based on discrete logarithms. In: Proceedings of Annual International Cryptology Conference, Santa Barbara, 1984. 10--18. Google Scholar

[13] Rabin M O. Digitalized signatures and public-key functions as intractable as factorization. Massachusetts INST of Tech Cambridge Lab For Computer Science, Technical Report, No. ADA078415. Cambridge, 1979. Google Scholar

[14] Okamoto T, Uchiyama S. A new public-key cryptosystem as secure as factoring. In: Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques, Espoo, 1998. 308--318. Google Scholar

[15] Paillier P. Public-key cryptosystems based on composite degree residuosity classes. In: Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques, Prague, 1999. 223--238. Google Scholar

[16] Miller V. Use of elliptic curves in cryptography. In: Proceedings of Annual International Cryptology Conference, Santa Barbara, 1985. 417--426. Google Scholar

[17] Hoffstein J, Pipher J, Silverman J H. NTRU: a ring-based public key cryptosystem. In: Proceedings of the 3rd International Symposium on Algorithmic Number Theory, Portland, 1998. 267--288. Google Scholar

[18] Goldreich O, Goldwasser S, Halevi S. Public-key cryptosystems from lattice reduction problems. In: Proceedings of Annual International Cryptology Conference, Santa Barbara, 1997. 112--131. Google Scholar

[19] Hu Y P, Jia H W. Cryptanalysis of GGH map. In: Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, 2016. 537--565. Google Scholar

[20] Benaloh J. Dense probabilistic encryption. In: Proceedings of the Workshop on Selected Areas of Cryptography, Kingston, 1994. 120--128. Google Scholar

[21] Naccache D, Stern J. A new public key cryptosystem based on higher residues. In: Proceedings of the 5th ACM conference on Computer and Communications Security, San Francisco, 1998. 59--66. Google Scholar

[22] Damgård I, Jurik M. A generalisation, a simplification and some applications of Paillier's probabilistic public-key system. In: Proceedings of Public Key Cryptosystem, 2001. 119--136. Google Scholar

[23] Ishai Y, Paskin A. Evaluating branching programs on encrypted data. In: Proceedings of International Theory of Cryptography Conference, Amsterdam, 2007. 575--594. Google Scholar

[24] Goldwasser S, Micali S. Probabilistic encryption. J Comput Syst Sci, 1984, 28: 270-299 CrossRef Google Scholar

[25] Boneh D, Goh E J, Nissim K. Evaluating 2-DNF formulas on ciphertexts. In: Proceedings of International Theory of Cryptography Conference, Cambridge, 2005. 325--341. Google Scholar

[26] Gentry C. Fully homomorphic encryption using ideal lattices. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, Bethesda, 2009. 169--178. Google Scholar

[27] Brakerski Z, Gentry C, Vaikuntanathan V. (Leveled) fully homomorphic encryption without bootstrapping. ACM Transactions on Computation Theory, 2014, 6(3): 13:1-13:36 doi: 10.1145/2090236.2090262. Google Scholar

[28] Brakerski Z, Vaikuntanathan V. Efficient Fully Homomorphic Encryption from (Standard) $\mathsf{LWE}$. SIAM J Comput, 2014, 43: 831-871 CrossRef Google Scholar

[29] Brakerski Z, Gentry C, Vaikuntanathan V. (Leveled) fully homomorphic encryption without bootstrapping. In: Proceedings of Innovations in Theoretical Computer Science, Cambridge, 2012. 309--325. Google Scholar

[30] Fan J F, Vercauteren F. Somewhat practical fully homomorphic encryption. Cryptology ePrint Archive, Report 2012/144. http://eprint.iacr.org/. Google Scholar

[31] Cheon J H, Kim A, Kim M, et al. Homomorphic encryption for arithmetic of approximate numbers. In: Proceedings of International Conference on the Theory and Application of Cryptology and Information Security, 2017. 409--437. Google Scholar

[32] Chillotti I, Gama N, Georgieva M, et al. Faster fully homomorphic encryption: bootstrapping in less than 0.1 seconds. In: Proceedings of International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, 2016. 3--33. Google Scholar

[33] Chillotti I, Gama N, Georgieva M, et al. Faster packed homomorphic operations and efficient circuit bootstrapping for TFHE. In: Proceedings of International Conference on the Theory and Application of Cryptology and Information Security, 2017. 377--408. Google Scholar

[34] Chillotti I, Gama N, Georgieva M, et al. TFHE: fast fully homomorphic encryption over the torus. IACR Cryptology ePrint Archive 2018: 421 (2018). Google Scholar

[35] Chillotti I, Gama N, Georgieva M, et al. Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds. In: Proceedings of International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, 2016. 3--33. Google Scholar

[36] Chillotti I, Gama N, Georgieva M, et al. TFHE: fast fully homomorphic encryption over the torus. https://eprint.iacr.org/2018/421. Google Scholar

[37] Goldreich O. Foundations of Cryptography: Basic Applications. Cambridge: Cambridge University Press, 2004. Google Scholar

[38] Nielsen J B, Nordholt P S, Orlandi C, et al. A new approach to practical active-secure two-party computation. In: Proceedings of Annual International Cryptology Conference, Santa Barbara, 2012. 681--700. Google Scholar

[39] Naehrig M, Lauter K, Vaikuntanathan V. Can homomorphic encryption be practical? In: Proceedings of the 3rd ACM Cloud Computing Security Workshop, Chicago, 2011. 113--124. Google Scholar

[41] Sander T, Young A, Yung M. Non-interactive crypto-computing for NC$^1$. In: Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, 1999. 554--566. Google Scholar

[42] Fischlin M. A cost-effective pay-per-multiplication comparison method for millionaires. In: Proceedings of he Cryptographer's Track at the RSA Conference, San Jose, 2001. 457--471. Google Scholar

[43] Barbulescu R, Gaudry P, Joux A, et al. A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic: improvements over FFS in small to medium characteristic. In: Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques, Copenhagen, 2014. 1--16. Google Scholar

[44] Menezes A, Sarkar P, Singh S. Challenges with assessing the impact of NFS advances on the security of pairing-based cryptography. In: Proceedings of International Conference on Cryptology in Malaysia, Kuala Lumpur, 2016. 83--108. Google Scholar

[45] Thomas W J, Stephen F. Abstract Algebra Theory and Applications. Nacogdoches: Austin State University Press, 2014. Google Scholar

[46] Meadows C. A more efficient cryptographic matchmaking protocol for use in the absence of a continuously available third party. In: Proceedings of 1986 IEEE Symposium on Security and Privacy, Oakland, 1986. 134. Google Scholar

[47] Freedman M J, Hazay C, Nissim K. Efficient Set Intersection with Simulation-Based Security. J Cryptol, 2016, 29: 115-155 CrossRef Google Scholar

[48] Kissner L, Song D. Privacy-preserving set operations. In: Proceedings of Annual International Cryptology Conference, Santa Barbara, 2005. 241--257. Google Scholar

[49] Pinkas B, Schneider T, Segev G, et al. Phasing: Private set intersection using permutation-based hashing. In: Proceedings of the 24th USENIX Security Symposium, Washington, 2015. 515--530. Google Scholar

[50] Pinkas B, Schneider T, Zohner M. Scalable Private Set Intersection Based on OT Extension. ACM Trans Priv Secur, 2018, 21: 1-35 CrossRef Google Scholar

[51] Orr$\acute{u}$ M, Orsini E, Scholl P. Actively secure 1-out-of-$n$ OT extension with application to private set intersection. In: Proceedings of Cryptographers' Track at the RSA Conference, San Francisco, 2017. 381--396. Google Scholar

[52] Chen H, Laine K, Rindal P. Fast private set intersection from homomorphic encryption. In: Proceedings of the ACM SIGSAC Conference on Computer and Communications Security, Dallas, 2017. 1243--1255. Google Scholar

• Figure 1

(Color online) The execution time increases almost linearly as the bits to be encrypted increase and does not significantly increase as the length of the module increases.

• Table 1   Multiplication table for $Z_8$
 $\cdot$ 0 1 2 3 4 5 6 7 0 0 0 0 0 0 0 0 0 1 0 1 2 3 4 5 6 7 2 0 2 4 6 0 2 4 6 3 0 3 6 1 4 7 2 5 4 0 4 0 4 0 4 0 4 5 0 5 2 7 4 1 6 3 6 0 6 4 2 0 6 4 2 7 0 7 6 5 4 3 2 1
• Table 2   Ciphertext expansion and noise comparison
 Cryptosystem G-M O-U Paillier FHE-derived $^{\rm~a)}$ Ours Ciphertext expansion $2k$ $3k$ $4k$ 16000 $2k$

Citations

• 0

Altmetric

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有