Abstract
We present a fully homomorphic encryption scheme which has both relatively small key and ciphertext size. Our construction follows that of Gentry by producing a fully homomorphic scheme from a “somewhat” homomorphic scheme. For the somewhat homomorphic scheme the public and private keys consist of two large integers (one of which is shared by both the public and private key) and the ciphertext consists of one large integer. As such, our scheme has smaller message expansion and key size than Gentry’s original scheme. In addition, our proposal allows efficient fully homomorphic encryption over any field of characteristic two.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Buchmann, J.: Zur Komplexität der Berechungung von Einheiten und Klassenzahlen algebraischer Zahlkörper, Habilitationsschrift (1987)
Buchmann, J.: A subexponential algorithm for the determination of class groups and regulators of algebraic number fields. Séminaire de Théorie des Nombres – Paris 1988-89, 27–41 (1990)
Buchmann, J., Maurer, M., Möller, B.: Cryptography based on number fields with large regulator. Journal de Théorie des Nombres de Bordeaux 12, 293–307 (2000)
Cohen, H.: A Course in Computational Algebraic Number Theory. Springer GTM 138 (1993)
Ding, J., Lindner, R.: Identifying ideal lattices. IACR eprint 2009/322
Von Zur Gathen, J., Gerhard, J.: Modern Computer Algebra. Cambridge University Press, Cambridge (1999)
Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Symposium on Theory of Computing – STOC 2009, pp. 169–178. ACM, New York (2009)
Gentry, C.: A fully homomorphic encryption scheme, (manuscript) (2009)
Goldreich, O., Goldwasser, S., Halevi, S.: Public-key cryptosystems from lattice reduction problems. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 112–131. Springer, Heidelberg (1997)
Hallgren, S.: Fast quantum algorithms for computing the unit group and class group of a number field. In: Symposium on Theory of Computing – STOC 2005, pp. 468–474. ACM, New York (2005)
Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: a ring-based public key cryptosystem. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol. 1423, pp. 267–288. Springer, Heidelberg (1998)
Lenstra, A.K., Lenstra Jr., H.W., Lovász, L.: Factoring polynomials with rational coefficients. Mathematische Ann. 261, 513–534 (1982)
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)
Thiel, C.: On the complexity of some problems in algorithmic algebraic number theory. PhD thesis, Universität des Saarlandes, Saarbrücken, Germany (1995)
de Weger, B.M.M.: Algorithms for Diophantine Equations. PhD thesis, University of Leiden (1987)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Smart, N.P., Vercauteren, F. (2010). Fully Homomorphic Encryption with Relatively Small Key and Ciphertext Sizes. In: Nguyen, P.Q., Pointcheval, D. (eds) Public Key Cryptography – PKC 2010. PKC 2010. Lecture Notes in Computer Science, vol 6056. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-13013-7_25
Download citation
DOI: https://doi.org/10.1007/978-3-642-13013-7_25
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-13012-0
Online ISBN: 978-3-642-13013-7
eBook Packages: Computer ScienceComputer Science (R0)