logo

Journals Books
Advanced Search
Sign in Register

中文

SCIENCE CHINA Information Sciences
Download PDF
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

Shundong LI 1, Sufang ZHOU 1, Jiawei DOU 2,*, Wenli WANG 1
More info
  • ReceivedAug 17, 2018
  • AcceptedFeb 14, 2019
  • PublishedDec 25, 2019
Previous Table of Contents Next
Share
Rating

Abstract


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

[40] https://www.networkworld.com/article/3196121/security/how-to-make-fully-homomorphic-encryption-practical-and-usable.html. 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

  • Click to view Download high-quality image

    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
    00 00 00 00 0
    1 01 2 3 4 5 6 7
    2 02 4 6 0 2 4 6
    3 03 6 1 4 7 2 5
    4 04 0 4 0 4 0 4
    5 05 2 7 4 1 6 3
    6 06 4 2 0 6 4 2
    7 07 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$