SpringerOpen Newsletter

Receive periodic news and updates relating to SpringerOpen.

This article is part of the series Signal Processing in the Encrypted Domain.

Open Access Review Article

A Survey of Homomorphic Encryption for Nonspecialists

Caroline Fontaine* and Fabien Galand

Author Affiliations

CNRS/IRISA-TEMICS, Campus de Beaulieu, Rennes Cedex 35042, France

For all author emails, please log on.

EURASIP Journal on Information Security 2007, 2007:013801  doi:10.1155/2007/13801

The electronic version of this article is the complete one and can be found online at: http://jis.eurasipjournals.com/content/2007/1/013801


Received:30 March 2007
Revisions received:10 July 2007
Accepted:24 October 2007
Published:11 December 2007

© 2007 Fontaine and Galand

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Processing encrypted signals requires special properties of the underlying encryption scheme. A possible choice is the use of homomorphic encryption. In this paper, we propose a selection of the most important available solutions, discussing their properties and limitations.

References

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

  2. E Brickell, Y Yacobi, On privacy homomorphisms. Advances in Cryptology (EUROCRYPT '87), Lecture Notes in Computer Science (Springer, New York, NY, USA, 1987) 304, pp. 117–126

  3. D Rappe, in Homomorphic cryptosystems and their applications, Ph, ed. by . D. thesis (University of Dortmund, Dortmund, Germany, 2004) (http://www, 2004), . rappe.de/doerte/Diss.pdf webcite OpenURL

  4. R Cramer, I Damgård, Zero-knowledge for finite field arthmetic, or: can zeroknowledge be for free? Advances in Cryptology (CRYPTO '98), Lecture Notes in Computer Science (Springer, New York, NY, USA, 1998) 1462, pp. 424–441 Publisher Full Text OpenURL

  5. H Lipmaa, Verifiable homomorphic oblivious transfer and private equality test. Advances in Cryptology (ASIACRYPT '03), Lecture Notes in Computer Science (Springer, New York, NY, USA, 2003) 2894, pp. 416–433 Publisher Full Text OpenURL

  6. P-A Fouque, G Poupard, J Stern, Sharing decryption in the context of voting or lotteries. Proceedings of the 4th International Conference on Financial Cryptography, 2000, Anguilla, British West Indies, Lecture Notes in Computer Science 1962, 90–104

  7. T Sander, C Tschudin, Protecting mobile agents against malicious hosts. Mobile Agents and Security, Lecture Notes in Computer Science (Springer, New York, NY, USA, 1998) 1419, pp. 44–60

  8. P Golle, M Jakobsson, A Juels, P Syverson, Universal re-encryption for mixnets. Proceedings of the RSA Conference Cryptographer's (Track '04), 2004, San Francisco, Calif, USA, Lecture Notes in Computer Science 2964, 163–178

  9. I Damgård, M Jurik, A length-flexible threshold cryptosystem with applications. Proceedings of the 8th Australian Conference on Information Security and Privacy (ACISP '03), 2003, Wollongong, Australia, Lecture Notes in Computer Science 2727

  10. A Adelsbach, S Katzenbeisser, A Sadeghi, Cryptology meets watermarking: detecting watermarks with minimal or zero-knowledge disclosures. Proceedings of the European Signal Processing Conference (EUSIPCO '02), September 2002, Toulouse, France

  11. B Pfitzmann, W Waidner, Anonymous fingerprinting. Advances in Cryptology (EUROCRYPT '97), Lecture Notes in Computer Science (Springer, New York, NY, USA, 1997) 1233, pp. 88–102 Publisher Full Text OpenURL

  12. N Memon, P Wong, A buyer-seller watermarking protocol. IEEE Transactions on Image Processing 10(4), 643–649 (2001). PubMed Abstract | Publisher Full Text OpenURL

  13. C-L Lei, P-L Yu, P-L Tsai, M-H Chan, An efficient and anonymous buyer-seller watermarking protocol. IEEE Transactions on Image Processing 13(12), 1618–1626 (2004). PubMed Abstract | Publisher Full Text OpenURL

  14. M Kuribayashi, H Tanaka, Fingerprinting protocol for images based on aditive homomorphic property. IEEE Transactions on Image Processing 14(12), 2129–2139 (2005). PubMed Abstract OpenURL

  15. V Shoup, A Computational Introduction to Number Theory and Algebra (Cambridge University Press, 2005) (http://www, 2005), . shoup.net/ntb/ webcite OpenURL

  16. A Menezes, P Van Orschot, S Vanstone, Handbook of applied cryptography (CRC Press, 1997) (http://www, 1997), . cacr.math.uwaterloo.ca/hac/ webcite OpenURL

  17. Van Tilborg H (ed.), Encyclopedia of Cryptography and Security (Springer, New York, NY, USA, 2005)

  18. A Kerckhoffs, La cryptographie militaire (part i). Journal des Sciences Militaires 9(1), 5–38 (1883)

  19. A Kerckhoffs, La cryptographie militaire (part ii). Journal des Sciences Militaires 9(2), 161–191 (1883)

  20. J Daemen, V Rijmen, The block cipher RIJNDAEL. (CARDIS '98), Lecture Notes in Computer Science (Springer, New York, NY, USA, 2000) 1820, pp. 247–256 PubMed Abstract | Publisher Full Text OpenURL

  21. J Daemen, V Rijmen, The design of Rijndael. AES—the Advanced Encryption Standard, Informtion Security and Cryptography (Springer, New York, NY, USA, 2002) PubMed Abstract | Publisher Full Text OpenURL

  22. G Vernam, Cipher printing telegraph systems for secret wire and radio telegraphic communications. Journal of the American Institute of Electrical Engineers 45, 109–115 (1926)

  23. P Ekdahl, T Johansson, A new version of the stream cipher SNOW. Selected Areas in Cryptography (SAC '02), Lecture Notes in Computer Science (Springer, New York, NY, USA, 2002) 2595, pp. 47–61

  24. R Rivest, A Shamir, L Adleman, A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM 21(2), 120–126 (1978). Publisher Full Text OpenURL

  25. T ElGamal, A prublic key cryptosystem and a signature scheme based on discrete logarithms. Advances in Cryptology (CRYPTO '84), Lecture Notes in Computer Science (Springer, New York, NY, USA, 1985) 196, pp. 10–18 Publisher Full Text OpenURL

  26. C Shannon, Communication theory of secrecy systems. Bell System Technical Journal 28, 656–715 (1949)

  27. M Ajtai, C Dwork, A public key cryptosystem with worst-case/average-case equivalence. Proceedings of the 29th ACM Symposium on Theory of Computing (STOC '97), 1997, 284–293

  28. P Nguyen, J Stern, Cryptanalysis of the Ajtai-Dwork cryptosystem. Advances in Cryptology (CRYPTO '98), Lecture Notes in Computer Science (Springer, New York, NY, USA, 1999) 1462, pp. 223–242

  29. R Canetti, O Goldreich, S Halevi, The random oracle model, revisited. Proceedings of the 30th ACM Symposium on Theory of Computing (STOC '98), 1998, Berkeley, Calif, USA, 209–218

  30. P Paillier, Impossibility proofs for RSA signatures in the standard model. Proceedings of the RSA Conference 2007, Cryptographers' (Track), 2007, San Fancisco, Calif, USA, Lecture Notes in Computer Science 4377, 31–48

  31. W Diffie, M Hellman, New directions in cryptography. IEEE Transactions on Information Theory 22(6), 644–654 (1976). Publisher Full Text OpenURL

  32. D Kahn, The Codebreakers: The Story of Secret Writing (Macmillan, New York, NY, USA, 1967)

  33. M Bellare, P Rogaway, Optimal asymmetric encryption—how to encrypt with RSA. Advances in Cryptology (EUROCRYPT '94), Lecture Notes in Computer Science (Springer, New York, NY, USA, 1995) 950, pp. 92–111 Publisher Full Text OpenURL

  34. S Goldwasser, S Micali, Probabilistic encryption & how to play mental poker keeping secret all partial information. Proceedings of the 14th ACM Symposium on the Theory of Computing (STOC '82), 1982, New York, NY, USA, 365–377

  35. M Blum, S Goldwasser, An efficient probabilistic public-key encryption scheme which hides all partial information. Advances in Cryptology (EUROCRYPT '84), Lecture Notes in Computer Science (Springer, New York, NY, USA, 1985) 196, pp. 289–299

  36. O Goldreich, A uniform complexity treatment of encryption and zero-knowledge. Journal of Cryptology 6(1), 21–53 (1993). Publisher Full Text OpenURL

  37. M Naor, M Yung, Public-key cryptosystems provably secure against chosen ciphertext attacks. Proceedings of the 22nd ACM Annual Symposium on the Theory of Computing (STOC '90), 1990, Baltimore, Md, USA, 427–437

  38. C Rackoff, D Simon, Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack. Advances in Cryptology (CRYPTO '91), Lecture Notes in Computer Science (Springer, New York, NY, USA, 1991) 576, pp. 433–444

  39. D Dolev, C Dwork, M Naor, Non-malleable cryptography. Proceedings of the 23rd ACM Annual Symposium on the Theory of Computing —(STOC '91), 1991, 542–552

  40. D Dolev, C Dwork, M Naor, Non-malleable cryptography. SIAM Journal of Computing 30(2), 391–437 (2000). Publisher Full Text OpenURL

  41. M Bellare, A Desai, D Pointcheval, P Rogaway, Relations among notions of security for public-key encryption schemes. Advances in Cryptology (CRYPTO '98), Lecture Notes in Computer Science (Springer, New York, NY, USA, 1998) 1462, pp. 26–45 Publisher Full Text OpenURL

  42. M Bellare, A Sahai, Non-malleable encryption: equivalence between two notions, and an indistinguishability-based characterization. Advances in Cryptology (CRYPTO '99), Lecture Notes in Computer Science (Springer, New York, NY, USA, 1999) 1666, pp. 519–536 Publisher Full Text OpenURL

  43. Y Watanabe, J Shikata, H Imai, Equivalence between semantic security and indistinguishability against chosen ciphertext attacks. Public Key Cryptography (PKC '03), Lecture Notes in Computer Science (Springer, New York, NY, USA, 2003) 2567, pp. 71–84

  44. N Ahituv, Y Lapid, S Neumann, Processing encrypted data. Communications of the ACM 30(9), 777–780 (1987). Publisher Full Text OpenURL

  45. D Boneh, R Lipton, Algorithms for black box fields and their application to cryptography. Advances in Cryptology (CRYPTO '96), Lecture Notes in Computer Science (Springer, New York, NY, USA, 1996) 1109, pp. 283–297 Publisher Full Text OpenURL

  46. S Goldwasser, S Micali, Probabilistic encryption. Journal of Computer and System Sciences 28(2), 270–299 (1984). Publisher Full Text OpenURL

  47. P Paillier, Public-key cryptosystems based on composite degree residuosity classes. Advances in Cryptology (EUROCRYPT '99), Lecture Notes in Computer Science (Springer, New York, NY, USA, 1999) 1592, pp. 223–238 Publisher Full Text OpenURL

  48. R Cramer, R Gennaro, B Schoenmakers, A secure and optimally efficient multiauthority election scheme. Advances in Cryptology (EUROCRYPT '97), Lecture Notes in Computer Science (Springer, New York, NY, USA, 1997) 1233, pp. 103–118 Publisher Full Text OpenURL

  49. R McEliece, A public-key cryptosystem based on algebraic coding theory. Dsn progress report (1978)

  50. J Benaloh, in Verifiable secret-ballot elections, Ph, ed. by . D. thesis (Yale University, Department of Computer Science, New Haven, Conn, USA, 1988)

  51. D Naccache, J Stern, A new public-key cryptosystem based on higher residues. Proceedings of the 5th ACM Conference on Computer and Communications Security, November 1998, San Francisco, Calif, USA, 59–66

  52. T Okamoto, S Uchiyama, A new public-key cryptosystem as secure as factoring. Advances in Cryptology (EUROCRYPT '98), Lecture Notes in Computer Science (Springer, New York, NY, USA, 1998) 1403, pp. 308–318 Publisher Full Text OpenURL

  53. T Okamoto, S Uchiyama, E Fujisaki, Epoc: efficient probabilistic publickey encryption (Proposal to IEEE P1363a, http://grouper, 2000), . ieee.org/groups/1363/P1363a/draft.html webcite

  54. M Joye, J-J Quisquater, M Yung, On the power of misbehaving adversaries and security analysis of the original EPOC. Topics in Cryptology CT-RSA 2001, Lecture Notes in Computer Science (Springer, New York, NY, USA, 2001) 2020

  55. R Cramer, V Shoup, Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption. Advances in Cryptology (EUROCRYPT '02), Lecture Notes in Computer Science (Springer, New York, NY, USA, 2002) 2332, pp. 45–64 Publisher Full Text OpenURL

  56. E Bresson, D Catalano, D Pointcheval, A simple public-key cryptosystem with a double trapdoor decryption mechanism and its applications. Advances in Cryptology (ASIACRYPT '03), Lecture Notes in Computer Science (Springer, New York, NY, USA, 2003) 2894, pp. 37–54 Publisher Full Text OpenURL

  57. I Damgård, M Jurik, A generalisation, a simplification and some applications of Paillier's probabilistic public-key system. 4th International Workshop on Practice and Theory in Public-Key Cryptography, Lecture Notes in Computer Science (Springer, New York, NY, USA, 2001) 1992, pp. 119–136

  58. S Galbraith, Elliptic curve paillier schemes. Journal of Cryptology 15(2), 129–138 (2002)

  59. G Castagnos, An efficient probabilistic public-key cryptosystem over quadratic fields quotients (Finite Fields and Their Applications, paper version in press, http://users, 2007), . info.unicaen.fr/~gcastagn/ webcite

  60. G Castagnos, in Quelques schémas de cryptographie asymétrique probabiliste, Ph, ed. by . D. thesis (, Bochum, Germany, 2006) (http://users, 2006), . info.unicaen.fr/~gcastagn/ webcite OpenURL

  61. D Boneh, M Franklin, Identity-based encryption from the Weil pairing. Advances in Cryptology (CRYPTO '01), Lecture Notes in Computer Science (Springer, New York, NY, USA, 2001) 2139, pp. 213–229 Publisher Full Text OpenURL

  62. D Boneh, X Boyen, E-J Goh, Hierarchical identity based encryption with constant size ciphertext. Advances in Cryptology (EUROCRYPT '05), Lecture Notes in Computer Science (Springer, New York, NY, USA, 2005) 3494, pp. 440–456 Publisher Full Text OpenURL

  63. J Domingo-Ferrer, A provably secure additive and multiplicative privacy homomorphism. Proceedings of the 5th International Conference on Information Security (ISC '02), 2002, Sao Paulo, Brazil, Lecture Notes in Computer Science 2433, 471–483

  64. D Wagner, Cryptanalysis of an algebraic privacy homomorphism. Proceedings of the 6th International Conference on Information Security (ISC '03), 2003, Bristol, UK, Lecture Notes in Computer Science 2851

  65. F Bao, Cryptanalysis of a provable secure additive and multiplicative privacy homomorphism. International Workshop on Coding and Cryptograhy (WCC '03), 2003, Versailles, France, 43–49

  66. J Domingo-Ferrer, A new privacy homomorphism and applications. Information Processing Letters 60(5), 277–282 (1996). Publisher Full Text OpenURL

  67. J Cheon, W-H Kim, H Nam, Known-plaintext cryptanalysis of the domingo-ferrer algebraic privacy homomorphism scheme. Information Processing Letters 97(3), 118–123 (2006)

  68. C Castelluccia, E Mykletun, G Tsudik, Efficient aggregation of encrypted data in wireless sensor networks. ACM/IEEE Mobile and Ubiquitous Systems: Networking and Services (Mobiquitous '05), 109–117 (2005)

  69. M Fellows, N Koblitz, Combinatorial cryptosystems galore!. Contemporary Mathematics, Finite Fields: Theory, Applications, and Algorithms, FQ2 168, 51–61 (1993)

  70. L Ly, A public-key cryptosystem based on Polly Cracker, Ph.D. thesis