Article

Fully homomorphic encryption over the integers

Authors:

Marten van Dijk,

Vinod VaikuntanathanAuthors Info & Claims

EUROCRYPT'10: Proceedings of the 29th Annual international conference on Theory and Applications of Cryptographic Techniques

Pages 24 - 43

https://doi.org/10.1007/978-3-642-13190-5_2

Published: 30 May 2010 Publication History

Abstract

We construct a simple fully homomorphic encryption scheme, using only elementary modular arithmetic. We use Gentry’s technique to construct a fully homomorphic scheme from a “bootstrappable” somewhat homomorphic scheme. However, instead of using ideal lattices over a polynomial ring, our bootstrappable encryption scheme merely uses addition and multiplication over the integers. The main appeal of our scheme is the conceptual simplicity.

We reduce the security of our scheme to finding an approximate integer gcd – i.e., given a list of integers that are near-multiples of a hidden integer, output that hidden integer. We investigate the hardness of this task, building on earlier work of Howgrave-Graham.

References

[1]

Alexi, W., Chor, B., Goldreich, O., Schnorr, C.-P.: Rsa and rabin functions: Certain parts are as hard as the whole. SIAM J. Comput. 17(2), 194-209 (1988)

Digital Library

[2]

Boyar, J., Peralta, R., Pochuev, D.: On the multiplicative complexity of boolean functions over the basis (?,?, 1). Theor. Comput. Sci. 235(1), 43-57 (2000)

Digital Library

[3]

Cachin, C., Micali, S., Stadler, M.: Computationally private information retrieval with polylogarithmic communication. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 402-414. Springer, Heidelberg (1999)

Digital Library

[4]

Coppersmith, D.: Small solutions to polynomial equations, and low exponent RSA vulnerabilities. J. Cryptology 10(4), 233-260 (1997)

Digital Library

[5]

Gentry, C.: A fully homomorphic encryption scheme. PhD thesis, Stanford University (2009), http://crypto.stanford.edu/craig

Digital Library

[6]

Gentry, C.: Fully homomorphic encryption using ideal lattices. In: STOC 2009, pp. 169-178. ACM, New York (2009)

Digital Library

[7]

Goldwasser, S., Micali, S.: Probabilistic encryption. Journal of Computer and System Sciences 28(2), 270-299 (1984)

[8]

Håstad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A pseudorandom generator from any one-way function. SIAM J. Comput. 28(4), 1364-1396 (1999)

Digital Library

[9]

Howgrave-Graham, N.: Approximate integer common divisors. In: Silverman, J.H. (ed.) CaLC 2001. LNCS, vol. 2146, pp. 51-66. Springer, Heidelberg (2001)

Digital Library

[10]

Ishai, Y., Paskin, A.: Evaluating branching programs on encrypted data. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 575-594. Springer, Heidelberg (2007)

Digital Library

[11]

Karp, R.M., Ramachandran, V.: A Survey of Parallel Algorithms for Shared-Memory Machines. Technical Report CSD-88-408, UC Berkeley (1988)

Digital Library

[12]

Knuth, D.E.: Seminumerical Algorithms, 3rd edn. The Art of Computer Programming, vol. 2. Addison-Wesley, Reading (1997)

Digital Library

[13]

Lagarias, J.C.: The computational complexity of simultaneous diophantine approximation problems. SIAM J. Comput. 14(1), 196-209 (1985)

Digital Library

[14]

Lenstra, A.K.: Factoring multivariate polynomials over algebraic number fields. SIAM J. Comput. 16(3), 591-598 (1987)

Digital Library

[15]

Lindell, Y., Pinkas, B.: A proof of security of yao's protocol for two-party computation. J. Cryptology 22(2) (2009)

Digital Library

[16]

Nguyen, P.Q., Shparlinski, I.: On the insecurity of a server-aided RSA protocol. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 21-35. Springer, Heidelberg (2001)

Digital Library

[17]

Nguyen, P.Q., Stern, J.: The two faces of lattices in cryptology. In: Silverman, J.H. (ed.) CaLC 2001. LNCS, vol. 2146, pp. 146-180. Springer, Heidelberg (2001)

Digital Library

[18]

Nguyen, P.Q., Stern, J.: Adapting density attacks to low-weight knapsacks. In: Roy, B. (ed.) ASIACRYPT 2005. LNCS, vol. 3788, pp. 41-58. Springer, Heidelberg (2005)

Digital Library

[19]

Regev, O.: New lattice-based cryptographic constructions. JACM 51(6), 899-942 (2004)

Digital Library

[20]

Rivest, R., Adleman, L., Dertouzos, M.: On data banks and privacy homomorphisms. In: Foundations of Secure Computation, pp. 169-177. Academic Press, London (1978)

[21]

van Dijk, M., Gentry, C., Halevi, S., Vaikuntanathan, V.: Fully homomorphic encryption over the integers. Cryptology ePrint Archive, Report 2009/616 (2009), http://eprint.iacr.org/2009/616

[22]

Yao, A.C.: Protocols for secure computations. In: 23rd Annual Symposium on Foundations of Computer Science - FOCS 1982, pp. 160-164. IEEE, Los Alamitos (1982)

Digital Library

Cited By

Cheng KZou ZWang ZYang JChen S(2024)QFL: Federated Learning Acceleration Based on QAT Hardware AcceleratorProceedings of the International Conference on Computing, Machine Learning and Data Science10.1145/3661725.3661747(1-7)Online publication date: 12-Apr-2024
https://dl.acm.org/doi/10.1145/3661725.3661747
Shiriaev ENazarov AKucherov NBabenko M(2024)Analytical Review of Confidential Artificial Intelligence: Methods and Algorithms for Deployment in Cloud ComputingProgramming and Computing Software10.1134/S036176882470011750:4(304-314)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1134/S0361768824700117
Huang YWan JJiang ZZhou JFang JCao Z(2024)An Efficient Integer-Wise ReLU on TFHEInformation Security and Privacy10.1007/978-981-97-5025-2_9(161-179)Online publication date: 15-Jul-2024
https://dl.acm.org/doi/10.1007/978-981-97-5025-2_9
Show More Cited By

Fully homomorphic encryption over the integers

Recommendations

Bootstrappable Identity-Based Fully Homomorphic Encryption
Proceedings of the 13th International Conference on Cryptology and Network Security - Volume 8813

It has been an open problem for a number of years to construct an identity-based fully homomorphic encryption IBFHE scheme first mentioned by Naccache at CHES/CRYPTO 2010. At CRYPTO 2013, Gentry, Sahai and Waters largely settled the problem by ...
CRT-based fully homomorphic encryption over the integers

In 1978, Rivest, Adleman and Dertouzos introduced the basic concept of privacy homomorphism that allows computation on encrypted data without decryption. It was an interesting work whose idea precedes the recent development of fully homomorphic ...
CCA-Secure Keyed-Fully Homomorphic Encryption
Proceedings, Part I, of the 19th IACR International Conference on Public-Key Cryptography --- PKC 2016 - Volume 9614

To simultaneously achieve CCA security and homomorphic property for encryption, Emura et al. introduced a new cryptographic primitive named keyed-homomorphic encryption, in which homomorphic ciphertext manipulations can only be performed by someone ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

EUROCRYPT'10: Proceedings of the 29th Annual international conference on Theory and Applications of Cryptographic Techniques

May 2010

692 pages

ISBN:3642131891

Editor:
Henri Gilbert
Orange Labs/MAPS/STT, 38-40 rue du Général Leclerc, Issy les Moulineaux Cedex 9, France

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 30 May 2010

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

284
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Cheng KZou ZWang ZYang JChen S(2024)QFL: Federated Learning Acceleration Based on QAT Hardware AcceleratorProceedings of the International Conference on Computing, Machine Learning and Data Science10.1145/3661725.3661747(1-7)Online publication date: 12-Apr-2024
https://dl.acm.org/doi/10.1145/3661725.3661747
Shiriaev ENazarov AKucherov NBabenko M(2024)Analytical Review of Confidential Artificial Intelligence: Methods and Algorithms for Deployment in Cloud ComputingProgramming and Computing Software10.1134/S036176882470011750:4(304-314)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1134/S0361768824700117
Huang YWan JJiang ZZhou JFang JCao Z(2024)An Efficient Integer-Wise ReLU on TFHEInformation Security and Privacy10.1007/978-981-97-5025-2_9(161-179)Online publication date: 15-Jul-2024
https://dl.acm.org/doi/10.1007/978-981-97-5025-2_9
Huang TMa SWang AWang X(2024)Approximate Methods for the Computation of Step Functions in Homomorphic EncryptionInformation Security and Privacy10.1007/978-981-97-5025-2_12(217-237)Online publication date: 15-Jul-2024
https://dl.acm.org/doi/10.1007/978-981-97-5025-2_12
Chaturvedi BChakraborty AChatterjee AMukhopadhyay D(2024)“Ask and Thou Shall Receive”: Reaction-Based Full Key Recovery Attacks on FHEComputer Security – ESORICS 202410.1007/978-3-031-70903-6_23(457-477)Online publication date: 16-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-70903-6_23
Eriguchi RKurosawa KNuida K(2024)Efficient and Generic Methods to Achieve Active Security in Private Information Retrieval and More Advanced Database SearchAdvances in Cryptology – EUROCRYPT 202410.1007/978-3-031-58740-5_4(92-121)Online publication date: 26-May-2024
https://dl.acm.org/doi/10.1007/978-3-031-58740-5_4
Wang RWen YLi ZLu XWei BLiu KWang K(2024)Circuit Bootstrapping: Faster and SmallerAdvances in Cryptology – EUROCRYPT 202410.1007/978-3-031-58723-8_12(342-372)Online publication date: 26-May-2024
https://dl.acm.org/doi/10.1007/978-3-031-58723-8_12
Zhao DDing HLi ZZhang ZLi ZGao J(2023)CRT-Based Homomorphic Encryption over the FractionSecurity and Communication Networks10.1155/2023/31069272023Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1155/2023/3106927
Yang MZhong ZGhobadi M(2023)On-Fiber Photonic ComputingProceedings of the 22nd ACM Workshop on Hot Topics in Networks10.1145/3626111.3628177(263-271)Online publication date: 28-Nov-2023
https://dl.acm.org/doi/10.1145/3626111.3628177
Ryan KHe KSullivan GHeninger NMeng WJensen CCremers CKirda E(2023)Passive SSH Key Compromise via LatticesProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3616629(2886-2900)Online publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1145/3576915.3616629
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents