×

Benaloh’s dense probabilistic encryption revisited. (English) Zbl 1280.94055

Nitaj, Abderrahmane (ed.) et al., Progress in cryptology – AFRICACRYPT 2011. 4th international conference on cryptology in Africa, Dakar, Senegal, July 5–7, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-21968-9/pbk). Lecture Notes in Computer Science 6737, 348-362 (2011).
Summary: In 1994, Josh Benaloh [Dense Probabilistic Encryption. In: Proceedings of the Workshop on Selected Areas of Cryptography, 120–128 (1994)] proposed a probabilistic homomorphic encryption scheme, enhancing the poor expansion factor provided by Goldwasser and Micali’s scheme. Since then, numerous papers have taken advantage of Benaloh’s homomorphic encryption function, including voting schemes, private multi-party trust computation, non-interactive verifiable secret sharing, online poker. In this paper we show that the original description of the scheme is incorrect, because it can result in ambiguous decryption of ciphertexts. Then we show on several applications that a bad choice in the key generation phase of Benaloh’s scheme has a real impact on the behaviour of the application. For instance in an e-voting protocol, it can inverse the result of an election. Our main contribution is a corrected description of the scheme (we provide a complete proof of correctness). Moreover we also compute the probability of failure of the original scheme. Finally we show how to formulate the security of the corrected scheme in a generic setting suitable for several homomorphic encryptions.
For the entire collection see [Zbl 1216.94004].

MSC:

94A60 Cryptography

Software:

SageMath
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Abe, M., Suzuki, K.: M+1-st price auction using homomorphic encryption. In: Naccache, D., Paillier, P. (eds.) PKC 2002. LNCS, vol. 2274, pp. 115–124. Springer, Heidelberg (2002) · Zbl 1055.94510 · doi:10.1007/3-540-45664-3_8
[2] Akinwande, M.: Advances in Homomorphic Cryptosystems. Journal of Universal Computer Science 15(3), 506–522 (2009) · Zbl 1216.94045
[3] Benaloh, J.: Dense Probabilistic Encryption. In: Proceedings of the Workshop on Selected Areas of Cryptography, pp. 120–128 (1994)
[4] Benaloh, J., Tuinstra, D.: Receipt-free Secret-Ballot Elections (extended abstract). In: STOC 1994: Proceedings of the Twenty-sixth Annual ACM Symposium on Theory of Computing, pp. 544–553. ACM, New York (1994) · Zbl 1344.68029 · doi:10.1145/195058.195407
[5] Benaloh, J.D.C.: Verifiable Secret-Ballot Elections. PhD thesis, Yale University, New Haven, CT, USA (1987) · Zbl 1344.68029
[6] Boneh, D., Goh, E.-J., Nissim, K.: Evaluating 2-dnf formulas on ciphertexts. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 325–341. Springer, Heidelberg (2005) · Zbl 1079.94534 · doi:10.1007/978-3-540-30576-7_18
[7] Fontaine, C., Galand, F.: A Survey of Homomorphic Encryption for Nonspecialists. In: EURASIP Journal on Information Security. Hindawi Publishing Corporation (2007)
[8] Chen, X., Lee, B., Kim, K.: Receipt-free electronic auction schemes using homomorphic encryption. In: Lim, J.-I., Lee, D.-H. (eds.) ICISC 2003. LNCS, vol. 2971, pp. 259–273. Springer, Heidelberg (2004) · Zbl 1092.68593 · doi:10.1007/978-3-540-24691-6_20
[9] Cohen, J.D., Fischer, M.J.: A robust and verifiable cryptographically secure election scheme (extended abstract). In: 26th Annual Symposium on Foundations of Computer Science, Portland, Oregon, USA, October 21-23, pp. 372–382. IEEE, Los Alamitos (1985)
[10] Benaloh, J.C.: Secret Sharing Homomorphisms: Keeping Shares of a Secret Secret. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 251–260. Springer, Heidelberg (1987) · Zbl 0637.94013 · doi:10.1007/3-540-47721-7_19
[11] Cramer, R., Gennaro, R., Schoenmakers, B.: A secure and optimally efficient multi-authority election scheme. In: Proc. International Conference on the Theory and Application of Cryptographic Techniques (EUROCRYPT ’97), Konstanz, Germany. lncs, vol. 1233, pp. 103–118. Springer, Heidelberg (1997)
[12] Cramer, R., Damgård, I.B., Nielsen, J.B.: Multiparty computation from threshold homomorphic encryption. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 280–299. Springer, Heidelberg (2001) · Zbl 1010.94553 · doi:10.1007/3-540-44987-6_18
[13] Cramer, R., Franklin, M.K., Schoenmakers, B., Yung, M.: Multi-authority secret-ballot elections with linear work. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 72–83. Springer, Heidelberg (1996) · Zbl 1304.94044 · doi:10.1007/3-540-68339-9_7
[14] Damgård, I., Fazio, N., Nicolosi, A.: Non-interactive zero-knowledge from homomorphic encryption. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 41–59. Springer, Heidelberg (2006) · Zbl 1112.94007 · doi:10.1007/11681878_3
[15] Damgård, I., Jurik, M., Nielsen, J.B.: A generalization of paillier’s public-key system with applications to electronic voting. Int. J. Inf. Sec. 9(6), 371–385 (2010) · doi:10.1007/s10207-010-0119-9
[16] Damgård, I., Nielsen, J.B.: Universally composable efficient multiparty computation from threshold homomorphic encryption. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 247–264. Springer, Heidelberg (2003) · Zbl 1122.94366 · doi:10.1007/978-3-540-45146-4_15
[17] Damgård, I., Jurik, M.: A Generalisation, a Simplification and Some Applications of Paillier’s Probabilistic Public-Key System. In: Kim, K.-c. (ed.) PKC 2001. LNCS, vol. 1992, pp. 119–136. Springer, Heidelberg (2001) · Zbl 0987.94032 · doi:10.1007/3-540-44586-2_9
[18] Dolev, S., Gilboa, N., Kopeetsky, M.: Computing Multi-Party Trust Privately: in O(n) time units sending one (possibly large) message at a time. In: SAC 2010: Proceedings of the 2010 ACM Symposium on Applied Computing, pp. 1460–1465. ACM, New York (2010)
[19] El Gamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. In: Blakely, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 10–18. Springer, Heidelberg (1985) · Zbl 1359.94590 · doi:10.1007/3-540-39568-7_2
[20] Freedman, M.J., Nissim, K., Pinkas, B.: Efficient private matching and set intersection. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 1–19. Springer, Heidelberg (2004) · Zbl 1122.94416 · doi:10.1007/978-3-540-24676-3_1
[21] Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Mitzenmacher, M. (ed.) Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, pp. 169–178. ACM Press, New York (2009) · Zbl 1304.94059
[22] Gentry, C.: Toward basing fully homomorphic encryption on worst-case hardness. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 116–137. Springer, Heidelberg (2010) · Zbl 1280.94059 · doi:10.1007/978-3-642-14623-7_7
[23] Gentry, C., Halevi, S., Vaikuntanathan, V.: i-hop homomorphic encryption and rerandomizable yao circuits. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 155–172. Springer, Heidelberg (2010) · Zbl 1280.94061 · doi:10.1007/978-3-642-14623-7_9
[24] Gjøsteen, K.: Homomorphic cryptosystems based on subgroup membership problems. In: Dawson, E., Vaudenay, S. (eds.) Mycrypt 2005. LNCS, vol. 3715, pp. 314–327. Springer, Heidelberg (2005), http://dx.doi.org/10.1007/11554868_22 · Zbl 1126.94328 · doi:10.1007/11554868_22
[25] Goldwasser, S., Micali, S.: Probabilistic Encryption and How to Play Mental Poker Keeping Secret All Partial Information. In: STOC, pp. 365–377 (1982) · doi:10.1145/800070.802212
[26] Golle, P.: Dealing Cards in Poker Games. In: Proc. of ITCC 2005 E-Gaming Track (2005) · doi:10.1109/ITCC.2005.119
[27] Groth, J.: A verifiable secret shuffle of homomorphic encryptions. J. Cryptology 23(4), 546–579 (2010) · Zbl 1201.94086 · doi:10.1007/s00145-010-9067-9
[28] Hirt, M., Sako, K.: Efficient receipt-free voting based on homomorphic encryption. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 539–556. Springer, Heidelberg (2000) · Zbl 1082.94520 · doi:10.1007/3-540-45539-6_38
[29] Jha, S., Kruger, L., McDaniel, P.: Privacy preserving clustering. In: di Vimercati, S.d.C., Syverson, P.F., Gollmann, D. (eds.) ESORICS 2005. LNCS, vol. 3679, pp. 397–417. Springer, Heidelberg (2005) · doi:10.1007/11555827_23
[30] Kleinjung, T., Aoki, K., Franke, J., Lenstra, A.K., Thomé, E., Gaudry, P., Montgomery, P.L., Osvik, D.A., Riele, H.T., Timofeev, A., Zimmermann, P.: Factorization of a 768-bit RSA modulus (2010)
[31] Lipmaa, H.: Verifiable homomorphic oblivious transfer and private equality test. In: Laih, C.-S. (ed.) ASIACRYPT 2003. LNCS, vol. 2894, pp. 416–433. Springer, Heidelberg (2003) · Zbl 1205.94108 · doi:10.1007/978-3-540-40061-5_27
[32] Naccache, D., Stern, J.: A New Public Key Cryptosystem Based on Higher Residues. In: ACM Conference on Computer and Communications Security, pp. 59–66 (1998) · doi:10.1145/288090.288106
[33] Okamoto, T., Uchiyama, S.: A new public-key cryptosystem as secure as factoring (Lecture Notes in Computer Science). In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 308–318. Springer, Heidelberg (1998) · Zbl 0919.94028 · doi:10.1007/BFb0054135
[34] Paillier, P.: Public-Key Cryptosystems Based on Composite Degree Residuosity Classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223–238. Springer, Heidelberg (1999) · Zbl 0933.94027 · doi:10.1007/3-540-48910-X_16
[35] Pollard, J.M.: Theorems on Factorization and Primality Testing. Mathematical Proceedings of the Cambridge Philosophical Society 76(03), 521–528 (1974), doi:10.1017/S0305004100049252 · doi:10.1017/S0305004100049252
[36] Rappe, D.K.: Homomorphic Cryptosystems and their Applications. Cryptology ePrint Archive, Report 2006/001 (2006), http://eprint.iacr.org/
[37] Rivest, R.L., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21, 120–126 (1978) · Zbl 0368.94005 · doi:10.1145/359340.359342
[38] Ruiz, A., Villar, J.L.: Publicly Verifiable Secret Sharing from Paillier’s Cryptosystem. In: Wolf, C., Lucks, S., Yau, P.-W. (eds.) WEWoRC. LNI, vol. 74, pp. 98–108. GI (2005)
[39] Sako, K., Kilian, J.: Secure Voting Using Partially Compatible Homomorphisms. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 411–424. Springer, Heidelberg (1994) · Zbl 0939.94569 · doi:10.1007/3-540-48658-5_37
[40] Sander, T., Young, A., Yung, M.: Non-Interactive CryptoComputing for NC1. In: FOCS, pp. 554–567 (1999)
[41] Smart, N.P., Vercauteren, F.: Fully homomorphic encryption with relatively small key and ciphertext sizes. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 420–443. Springer, Heidelberg (2010) · Zbl 1281.94055 · doi:10.1007/978-3-642-13013-7_25
[42] Stein, W.A., et al.: Sage Mathematics Software (Version 4.5.1). The Sage Development Team (2010), http://www.sagemath.org
[43] Suzuki, K., Yokoo, M.: Secure generalized vickrey auction using homomorphic encryption. In: Wright, R.N. (ed.) FC 2003. LNCS, vol. 2742, pp. 239–249. Springer, Heidelberg (2003) · Zbl 1274.94118 · doi:10.1007/978-3-540-45126-6_17
[44] Tatebayashi, M., Matsuzaki, N., Newman Jr., D.B.: Key distribution protocol for digital mobile communication systems. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 324–334. Springer, Heidelberg (1990) · doi:10.1007/0-387-34805-0_30
[45] van Dijk, M., Gentry, C., Halevi, S., Vaikuntanathan, V.: Fully homomorphic encryption over the integers. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 24–43. Springer, Heidelberg (2010) · Zbl 1279.94130 · doi:10.1007/978-3-642-13190-5_2
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.