學術產出-Theses
Article View/Open
Publication Export
-
題名 一個可降低Gentry全同態加密演算法公鑰個數之提案
An Improvement of Gentry’s “Fully Homomorphic Encryption Scheme” by Reducing the Number of Public Keys作者 陳漢光 貢獻者 左瑞麟
陳漢光關鍵詞 全同態加密
密碼學
秘密計算
雲端運算
隱私保護日期 2011 上傳時間 30-Oct-2012 11:28:20 (UTC+8) 摘要 "全同態加密法"(Fully Homomorphic Encryption (FHE))一詞的介紹以及架構源於西元2009年由Gentry所提出。它讓加密後的密文執行特定的運算再將其解密即可得出該對應的明文運算結果，除此之外，全同態與同態最大的不同是它允許兩種或是多種以上的運算元進行資料運算，期間必須可以處理大量的資料並且保護其資料隱私性使其無洩漏之虞。也因為上述特點使得它可被廣泛使用在許多資料庫或是資料儲存上的應用，像是ASP、雲端運算或是雙方相等性驗證上，然而在Gentry的全同態加密中，它需要大量的空間來儲存所需要的公鑰，因此在實作上仍有一定的難度。為了解決上述問題，本文提供了一種新的改良方案使其更有效率來達到全同態加密的實作性，除此之外，我們也會在文章中提出安全性分析來證明本改良方案並不會對安全性造成影響，並且提出系統效能測試，說明本方案除了可減少公鑰儲存空間之外，在時間上，更可降低公鑰生成以及系統加密的時間，讓其全同態運算更具效率。
C. Gentry in 2009 proposed the first practical scheme which can compute arbitrary functions of encrypted data. This scheme is named “Fully Homomorphic Encryption (FHE)”. FHE allows a worker without the secret decryption key to compute any result of the data on one hand and still keep the data privacy on the other hand. It can be widely used in data storage application or database application, such as ASP, cloud computing and two-party equality testing. However, one drawback of Gentry’s fully homomorphic encryption scheme is that the size of public keys used in this system is extremely large. This means that a lot of space is required in order to store those public keys. This problem causes Gentry’s FHE hard to be implemented. In this thesis, we address the problem above, and give an improvement encryption scheme. Our improvement scheme needs less space to store the public keys which also makes the new scheme more efficient than Gentry’s original scheme. We also give a rigorous security proof to show that our improvement scheme is as secure as Gentry’s original scheme. A system performance test is also provided which shows that our scheme can not only reduce the numbers of public keys, but also reduce the time for public key generation and for encryption. Therefore, our improvement scheme can make fully homomorphic encryption more practical.參考文獻 [1]B.Applebaum, D.Cash, C.Peikert, and A.Sahai. Fast cryptographic primitives and circular-secure encryption based on hard learning problems. In CRYPTO2009, vol.5677 of LNCS, pp 595–618. Springer,2009.[2]D.Boneh, E-J.Goh, and K.Nissim. Evaluating 2-DNF formulas on ciphertexts. In CRYPTO 2005, vol. 3378 of LNCS, pp 325–342, Springer,2005.[3]D.Boneh, G. D Crescenzo,R.Ostrovsky, G.Persiano: Public key encryption with keyword search. In EUROCRYPT 2004., vol. 3027 of LNCS,pp. 506–522.Springer,2004.[4]E. Biham, A.Shamir: Differential cryptanalysis of DES-like cryptosystems.In CRYPTO1990 : vol.4 of LNCS, pp. 2-21. Springer,1991. [5]Z.Brakerski and V.Vaikuntanathan. Fully homomorphic encryption from ring-LWE and security for key dependent messages. In CRYPTO 2011, vol. 5677of LNCS,pp 505-524.Springer 2011.[6]J.Coron, A.Mandal, D.Naccache, and M.Tibouchi. Fully-homomorphic encryption over the integers with shorter public-keys. In CRYPTO 2011, vol.6841 of LNCS, pp. 487-504. Springer,2011[7]N.Courtois, J.Pieprzyk, Cryptanalysis of block ciphers with overdefined systems of equations. In ASIACRYPT 2002,vol. 2501of LNCS, pp267–287.Springer 2002. [8]S.Ciou and R.Tso A privacy preserved two-party equality testing protocol,In ICGEC 2011,pp.220-223,2011.[9]T.ElGamal.A Public key cryptosystem and a signature scheme based on discrete logarithm. In IEEEE Trans.Inform.Theory,vol.31,pp469-472,1985.[10]M.van Dijk, C.Gentry, S.Halevi, and V.Vaikuntanathan. Fully homomorphic encryption over the integers. In EUROCRYPT’10, vol.6110 of LNCS, pp.24–43. Springer 2010.[11]C.Gentry. A fully homomorphic encryption scheme. PhD thesis, Stanford University, 2009.crypto.stanford.edu/craig. available at: https://docs.google.com/viewer?url=http%3A%2F%2Fcrypto.stanford.edu%2Fcraig%2Fcraig-thesis.pdf[12]C.Gentry. Fully homomorphic encryption using ideal lattices. In STOC’09, pp 169–178. ACM, 2009.[13]C.Gentry and S.Halevi. Implementing gentry’s fully-homomorphic encryption scheme. In EUROCRYPT, vol.6632 of LNCS, pp 129–148. Springer, 2011.[14]S.Goldwasser and S.Micali. Probabilistic encryption & how to play mental poker keeping secret all partial information.In STOC’82,pp365-377.ACM1982. [15]Y.Ishai and A.Paskin. Evaluating branching programs on encrypted data. In TCC, vol.4392 of LNCS, pp 575–594. Springer, 2007.[16]V.Lyubashevsky, C.Peikert, and O.Regev. On ideal lattices and learning with errors over rings. In EUROCRYPT, vol.6110 of LNCS, pp 1–23.Springer,2010.[17]C.A.Melchor, P.Gaborit, and J.Herranz. Additively homomorphic encryption with -operand multiplications. In CRYPTO, vol.6223 of LNCS, pp 138–154. Springer, 2010.[18]C.Peikert. Public-key cryptosystems from the worst-case shortest vector problem: extended abstract. In STOC’09, pp 333–342. ACM, 2009.[19]P.Paillier. Public-key cryptosystem based on composite degree residuocity classes.In EUROCRYPT1999.vol.1592 of LNCS,pp223-238. Springer,1999.[20]O.Regev. On lattices, learning with errors, random linear codes, and cryptography. In STOC’05, pp 84–93. ACM, 2005.[21]O.Regev. The learning with errors problem. In IEEE Conference on Computational Complexity, pp 191–204. IEEE Computer Society, 2010.[22]R.Rivest,A.Shamir and L.Adleman.A method for obtaining digital signatures and public-key cryptosystem.In Commun’77,vol.21,pp120-126.ACM1977.[23]Y.Tsiounis and M.Yung. On the security of ElGamal based encryption. In Public Key Cryptography 1998.vol.1431 of LNCS.pp117-134. Springer,1998.[24]B.Waters: Efficient identity-based encryption without random oracles. In EUROCRYPT 2005. vol. 3494 of LNCS, pp. 114–127. Springer,2005.[25]吳承鋒、陳漢光、左瑞麟 利用ElGamal加密的雙方相等性驗證協議 全國計算機會議,pp183-191,2011. 描述 碩士
國立政治大學
資訊科學學系
99753024
100資料來源 http://thesis.lib.nccu.edu.tw/record/#G0099753024 資料類型 thesis dc.contributor.advisor 左瑞麟 zh_TW dc.contributor.author (Authors) 陳漢光 zh_TW dc.creator (作者) 陳漢光 zh_TW dc.date (日期) 2011 en_US dc.date.accessioned 30-Oct-2012 11:28:20 (UTC+8) - dc.date.available 30-Oct-2012 11:28:20 (UTC+8) - dc.date.issued (上傳時間) 30-Oct-2012 11:28:20 (UTC+8) - dc.identifier (Other Identifiers) G0099753024 en_US dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/54651 - dc.description (描述) 碩士 zh_TW dc.description (描述) 國立政治大學 zh_TW dc.description (描述) 資訊科學學系 zh_TW dc.description (描述) 99753024 zh_TW dc.description (描述) 100 zh_TW dc.description.abstract (摘要) "全同態加密法"(Fully Homomorphic Encryption (FHE))一詞的介紹以及架構源於西元2009年由Gentry所提出。它讓加密後的密文執行特定的運算再將其解密即可得出該對應的明文運算結果，除此之外，全同態與同態最大的不同是它允許兩種或是多種以上的運算元進行資料運算，期間必須可以處理大量的資料並且保護其資料隱私性使其無洩漏之虞。也因為上述特點使得它可被廣泛使用在許多資料庫或是資料儲存上的應用，像是ASP、雲端運算或是雙方相等性驗證上，然而在Gentry的全同態加密中，它需要大量的空間來儲存所需要的公鑰，因此在實作上仍有一定的難度。為了解決上述問題，本文提供了一種新的改良方案使其更有效率來達到全同態加密的實作性，除此之外，我們也會在文章中提出安全性分析來證明本改良方案並不會對安全性造成影響，並且提出系統效能測試，說明本方案除了可減少公鑰儲存空間之外，在時間上，更可降低公鑰生成以及系統加密的時間，讓其全同態運算更具效率。 zh_TW dc.description.abstract (摘要) C. Gentry in 2009 proposed the first practical scheme which can compute arbitrary functions of encrypted data. This scheme is named “Fully Homomorphic Encryption (FHE)”. FHE allows a worker without the secret decryption key to compute any result of the data on one hand and still keep the data privacy on the other hand. It can be widely used in data storage application or database application, such as ASP, cloud computing and two-party equality testing. However, one drawback of Gentry’s fully homomorphic encryption scheme is that the size of public keys used in this system is extremely large. This means that a lot of space is required in order to store those public keys. This problem causes Gentry’s FHE hard to be implemented. In this thesis, we address the problem above, and give an improvement encryption scheme. Our improvement scheme needs less space to store the public keys which also makes the new scheme more efficient than Gentry’s original scheme. We also give a rigorous security proof to show that our improvement scheme is as secure as Gentry’s original scheme. A system performance test is also provided which shows that our scheme can not only reduce the numbers of public keys, but also reduce the time for public key generation and for encryption. Therefore, our improvement scheme can make fully homomorphic encryption more practical. en_US dc.description.tableofcontents 1. 緒論: 11.1 雲端運算 11.2 解決方法 31.3 全同態加密應用 41.4 研究動機及貢獻 51.5 論文架構 62. 預備知識 72.1 近代密碼學 72.1.1 對稱式金鑰密碼系統 (Symmetric Key Cryptosystem) 72.1.2 非對稱式金鑰密碼系統 (Asymmetric Key Cryptosystem) 82.2 同態加密 102.2.1 加法同態 102.2.2 乘法同態 122.3 Genrty對稱式全同態加密方案 162.4 AGCD問題(Approximate Greatest Common Divisor Problem) 182.5 語意安全(Semantic Secure) 193. Gentry全同態加密方案回顧 213.1 Gentry 全同態加密演算法 213.2 同態加密的正確性 233.3 探討Gentry方案 244. 改進過後的FHE方案 254.1 我們提出的FHE方案 254.2 改進方案的貢獻 274.3 正確性分析 285. 安全性證明 305.1 A-GCD問題 305.2 語意安全 335.3 為何需要Axk 346. 系統效能分析與比較 356.1 金鑰生成所需時間 356.2 加密過程所需時間 387. 全同態加密之應用 417.1 邱姓學者提出的雙方相等性驗證 417.2 FNP隱私性交集相等性驗證 447.3 相等性驗證之應用 468. 結論及未來展望 479. 參考資料 48 zh_TW dc.language.iso en_US - dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0099753024 en_US dc.subject (關鍵詞) 全同態加密 zh_TW dc.subject (關鍵詞) 密碼學 zh_TW dc.subject (關鍵詞) 秘密計算 zh_TW dc.subject (關鍵詞) 雲端運算 zh_TW dc.subject (關鍵詞) 隱私保護 zh_TW dc.title (題名) 一個可降低Gentry全同態加密演算法公鑰個數之提案 zh_TW dc.title (題名) An Improvement of Gentry’s “Fully Homomorphic Encryption Scheme” by Reducing the Number of Public Keys en_US dc.type (資料類型) thesis en dc.relation.reference (參考文獻) [1]B.Applebaum, D.Cash, C.Peikert, and A.Sahai. Fast cryptographic primitives and circular-secure encryption based on hard learning problems. In CRYPTO2009, vol.5677 of LNCS, pp 595–618. Springer,2009.[2]D.Boneh, E-J.Goh, and K.Nissim. Evaluating 2-DNF formulas on ciphertexts. In CRYPTO 2005, vol. 3378 of LNCS, pp 325–342, Springer,2005.[3]D.Boneh, G. D Crescenzo,R.Ostrovsky, G.Persiano: Public key encryption with keyword search. In EUROCRYPT 2004., vol. 3027 of LNCS,pp. 506–522.Springer,2004.[4]E. Biham, A.Shamir: Differential cryptanalysis of DES-like cryptosystems.In CRYPTO1990 : vol.4 of LNCS, pp. 2-21. Springer,1991. [5]Z.Brakerski and V.Vaikuntanathan. Fully homomorphic encryption from ring-LWE and security for key dependent messages. In CRYPTO 2011, vol. 5677of LNCS,pp 505-524.Springer 2011.[6]J.Coron, A.Mandal, D.Naccache, and M.Tibouchi. Fully-homomorphic encryption over the integers with shorter public-keys. In CRYPTO 2011, vol.6841 of LNCS, pp. 487-504. Springer,2011[7]N.Courtois, J.Pieprzyk, Cryptanalysis of block ciphers with overdefined systems of equations. In ASIACRYPT 2002,vol. 2501of LNCS, pp267–287.Springer 2002. [8]S.Ciou and R.Tso A privacy preserved two-party equality testing protocol,In ICGEC 2011,pp.220-223,2011.[9]T.ElGamal.A Public key cryptosystem and a signature scheme based on discrete logarithm. In IEEEE Trans.Inform.Theory,vol.31,pp469-472,1985.[10]M.van Dijk, C.Gentry, S.Halevi, and V.Vaikuntanathan. Fully homomorphic encryption over the integers. In EUROCRYPT’10, vol.6110 of LNCS, pp.24–43. Springer 2010.[11]C.Gentry. A fully homomorphic encryption scheme. PhD thesis, Stanford University, 2009.crypto.stanford.edu/craig. available at: https://docs.google.com/viewer?url=http%3A%2F%2Fcrypto.stanford.edu%2Fcraig%2Fcraig-thesis.pdf[12]C.Gentry. Fully homomorphic encryption using ideal lattices. In STOC’09, pp 169–178. ACM, 2009.[13]C.Gentry and S.Halevi. Implementing gentry’s fully-homomorphic encryption scheme. In EUROCRYPT, vol.6632 of LNCS, pp 129–148. Springer, 2011.[14]S.Goldwasser and S.Micali. Probabilistic encryption & how to play mental poker keeping secret all partial information.In STOC’82,pp365-377.ACM1982. [15]Y.Ishai and A.Paskin. Evaluating branching programs on encrypted data. In TCC, vol.4392 of LNCS, pp 575–594. Springer, 2007.[16]V.Lyubashevsky, C.Peikert, and O.Regev. On ideal lattices and learning with errors over rings. In EUROCRYPT, vol.6110 of LNCS, pp 1–23.Springer,2010.[17]C.A.Melchor, P.Gaborit, and J.Herranz. Additively homomorphic encryption with -operand multiplications. In CRYPTO, vol.6223 of LNCS, pp 138–154. Springer, 2010.[18]C.Peikert. Public-key cryptosystems from the worst-case shortest vector problem: extended abstract. In STOC’09, pp 333–342. ACM, 2009.[19]P.Paillier. Public-key cryptosystem based on composite degree residuocity classes.In EUROCRYPT1999.vol.1592 of LNCS,pp223-238. Springer,1999.[20]O.Regev. On lattices, learning with errors, random linear codes, and cryptography. In STOC’05, pp 84–93. ACM, 2005.[21]O.Regev. The learning with errors problem. In IEEE Conference on Computational Complexity, pp 191–204. IEEE Computer Society, 2010.[22]R.Rivest,A.Shamir and L.Adleman.A method for obtaining digital signatures and public-key cryptosystem.In Commun’77,vol.21,pp120-126.ACM1977.[23]Y.Tsiounis and M.Yung. On the security of ElGamal based encryption. In Public Key Cryptography 1998.vol.1431 of LNCS.pp117-134. Springer,1998.[24]B.Waters: Efficient identity-based encryption without random oracles. In EUROCRYPT 2005. vol. 3494 of LNCS, pp. 114–127. Springer,2005.[25]吳承鋒、陳漢光、左瑞麟 利用ElGamal加密的雙方相等性驗證協議 全國計算機會議,pp183-191,2011. zh_TW
