Linearly Homomorphic Encryption from $$\mathsf {DDH}$$

详细信息    查看全文

• 作者：Guilhem Castagnos (14)
  Fabien Laguillaumie (15)
  
  14. Institut de Math茅matiques de Bordeaux UMR 5251 ; Universit茅 de Bordeaux ; 351 ; cours de la Lib茅ration ; 33405 ; Talence cedex ; France
  15. CNRS/ENSL/INRIA/UCBL LIP Laboratoire de l鈥橧nformatique du Parall茅lisme ; Universit茅 Claude Bernard Lyon 1 ; 46 All茅e d鈥橧talie ; 69364 ; Lyon ; France
  
• 刊名：Lecture Notes in Computer Science
• 出版年：2015
• 出版时间：2015
• 年：2015
• 卷：9048
• 期：1
• 页码：487-505
• 全文大小：338 KB
• 参考文献：1. Bresson, E, Catalano, D, Pointcheval, D A Simple Public-Key Cryptosystem with a Double Trapdoor Decryption Mechanism and Its Applications. In: Laih, C-S eds. (2003) Advances in Cryptology - ASIACRYPT 2003. Springer, Heidelberg, pp. 37-54 10.1007/978-3-540-40061-5_3" target="_blank" title="It opens in new window">CrossRef
  2. Buchmann, J, D眉llmann, S, Williams, HC On the Complexity and Efficiency of a New Key Exchange System. In: Quisquater, J-J, Vandewalle, J eds. (1990) Advances in Cryptology - EUROCRYPT 鈥?9. Springer, Heidelberg, pp. 597-616 10.1007/3-540-46885-4_57" target="_blank" title="It opens in new window">CrossRef
  3. Benaloh, J. C.: Verifiable Secret-Ballot Elections. PhD thesis, Yale University (1988)
  4. Boneh, D, Goh, E-J, Nissim, K Evaluating 2-DNF Formulas on Ciphertexts. In: Kilian, J eds. (2005) Theory of Cryptography. Springer, Heidelberg, pp. 325-341 10.1007/978-3-540-30576-7_18" target="_blank" title="It opens in new window">CrossRef
  5. Buchmann, J., Hamdy, S.: A survey on IQ-cryptography, Public-Key Cryptography and Computational Number Theory, de Gruyter, 1鈥?5 (2001)
  6. Biasse, J-F, Jacobson, MJ, Silvester, AK Security Estimates for Quadratic Field Based Cryptosystems. In: Steinfeld, R, Hawkes, P eds. (2010) Information Security and Privacy. Springer, Heidelberg, pp. 233-247 10.1007/978-3-642-14081-5_15" target="_blank" title="It opens in new window">CrossRef
  7. Brent, R.P.: Public Key Cryptography with a Group of Unknown Order. Technical Report. Oxford University (2000)
  8. Buchmann, J., Thiel, C., Williams, H.C.: Short Representation of Quadratic Integers. In: Proc. of CANT 1992, Math. Appl., vol. 325. pp. 159鈥?85. Kluwer Academic Press (1995)
  9. Buchmann, J, Vollmer, U (2007) Binary Quadratic Forms. Springer, An Algorithmic Approach
  10. Brakerski, Z, Vaikuntanathan, V (2014) Efficient Fully Homomorphic Encryption from (Standard) LWE. SIAM J. Comput. 43: pp. 831-871 10.1137/120868669" target="_blank" title="It opens in new window">CrossRef
  11. Buchmann, J, Williams, HC (1988) A Key-Exchange System Based on Imaginary Quadratic Fields. J. Cryptology 1: pp. 107-118 10.1007/BF02351719" target="_blank" title="It opens in new window">CrossRef
  12. Castagnos, G, Chevallier-Mames, B Towards a DL-Based Additively Homomorphic Encryption Scheme. In: Garay, JA, Lenstra, AK, Mambo, M, Peralta, R eds. (2007) Information Security. Springer, Heidelberg, pp. 362-375 10.1007/978-3-540-75496-1_24" target="_blank" title="It opens in new window">CrossRef
  13. Catalano, D., Fiore, D.: Boosting Linearly-Homomorphic Encryption to Evaluate Degree-2 Functions on Encrypted Data. Cryptology ePrint Archive, report 2014/813 (2014). 14/813" class="a-plus-plus">http://eprint.iacr.org/2014/813
  14. Cramer, R, Gennaro, R, Schoenmakers, B A Secure and Optimally Efficient Multi-authority Election Scheme. In: Fumy, W eds. (1997) Advances in Cryptology - EUROCRYPT 鈥?7. Springer, Heidelberg, pp. 103-118 10.1007/3-540-69053-0_9" target="_blank" title="It opens in new window">CrossRef
  15. Castagnos, G, Joux, A, Laguillaumie, F, Nguyen, PQ Factoring $$pq^2$$ with Quadratic Forms: Nice Cryptanalyses. In: Matsui, M eds. (2009) Advances in Cryptology 鈥?ASIACRYPT 2009. Springer, Heidelberg, pp. 469-486 10.1007/978-3-642-10366-7_28" target="_blank" title="It opens in new window">CrossRef
  16. Castagnos, G, Laguillaumie, F On the Security of Cryptosystems with Quadratic Decryption: The Nicest Cryptanalysis. In: Joux, A eds. (2009) Advances in Cryptology - EUROCRYPT 2009. Springer, Heidelberg, pp. 260-277 10.1007/978-3-642-01001-9_15" target="_blank" title="It opens in new window">CrossRef
  17. Castagnos, G, Laguillaumie, F Homomorphic Encryption for Multiplications and Pairing Evaluation. In: Visconti, I, Prisco, R eds. (2012) Security and Cryptography for Networks. Springer, Heidelberg, pp. 374-392 10.1007/978-3-642-32928-9_21" target="_blank" title="It opens in new window">CrossRef
  18. Castagnos, G., Laguillaumie, F.: Linearly Homomorphic Encryption from DDH, Extended version, Cryptology ePrint Archive, report 2015/047 (2015). 15/047" class="a-plus-plus">http://eprint.iacr.org/2015/047
  19. Chevallier-Mames, B, Paillier, P, Pointcheval, D Encoding-Free ElGamal Encryption Without Random Oracles. In: Yung, M, Dodis, Y, Kiayias, A, Malkin, T eds. (2006) Public Key Cryptography - PKC 2006. Springer, Heidelberg, pp. 91-104 10.1007/11745853_7" target="_blank" title="It opens in new window">CrossRef
  20. Coron, J-S, Handschuh, H, Naccache, D ECC: Do We Need to Count?. In: Lam, K-Y, Okamoto, E, Xing, C eds. (1999) Advances in Cryptology - ASIACRYPT鈥?9. Springer, Heidelberg, pp. 122-134 10.1007/978-3-540-48000-6_11" target="_blank" title="It opens in new window">CrossRef
  21. Cohen, H.: A Course in Computational Algebraic Number Theory. Springer (2000)
  22. Cox, D.A.: Primes of the form 11"> \(x^2+ny^2\) . John Wiley & Sons (1999)
  23. Damg氓rd, IB, Fujisaki, E A Statistically-Hiding Integer Commitment Scheme Based on Groups with Hidden Order. In: Zheng, Y eds. (2002) Advances in Cryptology - ASIACRYPT 2002. Springer, Heidelberg, pp. 125-142 10.1007/3-540-36178-2_8" target="_blank" title="It opens in new window">CrossRef
  24. Damg氓rd, I., Jurik, M.J.: A Generalisation, a Simplification and some Applications of Paillier鈥檚 Probabilistic Public-Key System. In: Kim, K. (ed.) Proc. of PKC 2001. LNCS, vol. 1992, pp. 119鈥?36. Springer, Heidelberg (2001)
  25. Galbraith, SD (2002) Elliptic Curve Paillier Schemes. J. Cryptology 15: pp. 129-138
  26. Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Proc. of STOC 2009, pp. 169鈥?78. ACM (2009)
  27. Goldwasser, S, Micali, S (1984) Probabilistic Encryption. JCSS 28: pp. 270-299
  28. H眉hnlein, D, Jacobson, MJ, Paulus, S, Takagi, T A Cryptosystem Based on Non-maximal Imaginary Quadratic Orders with Fast Decryption. In: Nyberg, K eds. (1998) Advances in Cryptology - EUROCRYPT 鈥?8. Springer, Heidelberg, pp. 294-307 10.1007/BFb0054134" target="_blank" title="It opens in new window">CrossRef
  29. Hamdy, S, M枚ller, B Security of Cryptosystems Based on Class Groups of Imaginary Quadratic Orders. In: Okamoto, T eds. (2000) Advances in Cryptology - ASIACRYPT 2000. Springer, Heidelberg, pp. 234-247 10.1007/3-540-44448-3_18" target="_blank" title="It opens in new window">CrossRef
  30. Hartmann, M, Paulus, S, Takagi, T NICE - New Ideal Coset Encryption -. In: Ko莽, 脟K, Paar, C eds. (1999) Cryptographic Hardware and Embedded Systems. Springer, Heidelberg, pp. 328-339 10.1007/3-540-48059-5_28" target="_blank" title="It opens in new window">CrossRef
  31. Jacobson, MJ (2000) Computing discrete logarithms in quadratic orders. J. Cryptology 13: pp. 473-492 10.1007/s001450010013" target="_blank" title="It opens in new window">CrossRef
  32. Jacobson, MJ The Security of Cryptosystems Based on Class Semigroups of Imaginary Quadratic Non-maximal Orders. In: Wang, H, Pieprzyk, J, Varadharajan, V eds. (2004) Information Security and Privacy. Springer, Heidelberg, pp. 149-156 10.1007/978-3-540-27800-9_13" target="_blank" title="It opens in new window">CrossRef
  33. Jaulmes, 脡, Joux, A A NICE Cryptanalysis. In: Preneel, B eds. (2000) Advances in Cryptology - EUROCRYPT 2000. Springer, Heidelberg, pp. 382-391 10.1007/3-540-45539-6_26" target="_blank" title="It opens in new window">CrossRef
  34. Joye, M, Libert, B Efficient Cryptosystems from $$2^k$$ -th Power Residue Symbols. In: Johansson, T, Nguyen, PQ eds. (2013) Advances in Cryptology 鈥?EUROCRYPT 2013. Springer, Heidelberg, pp. 76-92 10.1007/978-3-642-38348-9_5" target="_blank" title="It opens in new window">CrossRef
  35. Jacobson, MJ, Scheidler, R, Weimer, D An Adaptation of the NICE Cryptosystem to Real Quadratic Orders. In: Vaudenay, S eds. (2008) Progress in Cryptology 鈥?AFRICACRYPT 2008. Springer, Heidelberg, pp. 191-208 10.1007/978-3-540-68164-9_13" target="_blank" title="It opens in new window">CrossRef
  36. Kaplan, P (1976) Divisibilit茅 par 8 du nombre des classes des corps quadratiques dont le 2-groupe des classes est cyclique, et r茅ciprocit茅 biquadratique. J. Math. Soc. Japan 25: pp. 547-733
  37. Kim, H., Moon, S.: Public-key cryptosystems based on class semigroups of imaginary quadratic non-maximal orders. In: Safavi-Naini, R., Seberry, J. (eds.): ACISP 2003. LNCS, vol. 2727. Springer, Heidelberg (2003)
  38. Naccache, D., Stern, J.: A New Public Key Cryptosystem Based on Higher Residues. In: Proc. of ACM CCS 1998, pp. 546鈥?60 (1998)
  39. Okamoto, T, Uchiyama, S A New Public-Key Cryptosystem as Secure as Factoring. In: Nyberg, K eds. (1998) Advances in Cryptology - EUROCRYPT 鈥?8. Springer, Heidelberg, pp. 308-318 10.1007/BFb0054135" target="_blank" title="It opens in new window">CrossRef
  40. Paillier, P Public-Key Cryptosystems Based on Composite Degree Residuosity Classes. In: Stern, J eds. (1999) Advances in Cryptology - EUROCRYPT 鈥?9. Springer, Heidelberg, pp. 223-238 10.1007/3-540-48910-X_16" target="_blank" title="It opens in new window">CrossRef
  41. Paulus, S, Takagi, T (2000) A New Public-Key Cryptosystem over a Quadratic Order with Quadratic Decryption Time. J. Cryptology 13: pp. 263-272 10.1007/s001459910010" target="_blank" title="It opens in new window">CrossRef
  42. Schielzeth, D, Pohst, ME (2005) On Real Quadratic Number Fields Suitable for Cryptography. Experiment. Math. 14: pp. 189-197 10.1080/10586458.2005.10128914" target="_blank" title="It opens in new window">CrossRef
  43. Sch枚nhage, A.: Fast reduction and composition of binary quadratic forms. In: Proc. of ISSAC 1991, pp. 128鈥?33. ACM (1991)
  44. Wang, L, Wang, L, Pan, Y, Zhang, Z, Yang, Y (2011) Discrete Logarithm Based Additively Homomorphic Encryption and Secure Data Aggregation. Information Sciences 181: pp. 3308-3322 10.1016/j.ins.2011.04.002" target="_blank" title="It opens in new window">CrossRef
  
• 作者单位：Topics in Cryptology 篓C- CT-RSA 2015
• 丛书名：978-3-319-16714-5
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

We design a linearly homomorphic encryption scheme whose security relies on the hardness of the decisional Diffie-Hellman problem. Our approach requires some special features of the underlying group. In particular, its order is unknown and it contains a subgroup in which the discrete logarithm problem is tractable. Therefore, our instantiation holds in the class group of a non maximal order of an imaginary quadratic field. Its algebraic structure makes it possible to obtain such a linearly homomorphic scheme whose message space is the whole set of integers modulo a prime \(p\) and which supports an unbounded number of additions modulo \(p\) from the ciphertexts. A notable difference with previous works is that, for the first time, the security does not depend on the hardness of the factorization of integers. As a consequence, under some conditions, the prime \(p\) can be scaled to fit the application needs.