Loading...
|
Please use this identifier to cite or link to this item:
https://nccur.lib.nccu.edu.tw/handle/140.119/131636
|
| Title: | 基於同態加密之多訊息私密資訊擷取機制之研究
A Study on Multi-Message Private Information Retrievalusing Homomorphic Encryption |
| Authors: | 徐珦朕
Hsu, Hsiang-Chen |
| Contributors: | 左瑞麟
Tso, Ray-lin
徐珦朕
Hsu, Hsiang-Chen |
| Keywords: | 私密資訊擷取
通訊複雜度
同態加密
Homomorphic encryption
Private Information Retrieval
Communication complexity |
| Date: | 2020 |
| Issue Date: | 2020-09-02 12:16:24 (UTC+8) |
| Abstract: | 私密資訊擷取(Private Information Retrieval，PIR)為使用者在對資料庫取用資料時對使用者的隱私保護。透過私密資訊擷取，可以讓資料庫管理者沒有辦法得知使用者所取出的資料為哪一個。自從Chor等人以及Kushilevitz與Ostrovsky過去的研究，私密資訊擷取已經在過去二十年中有著廣泛的研究(尤其是單一資料庫的私密資訊擷取)，但是大多數的架構僅允許使用者一次只能存取一筆資料，這會導致較高的通訊成本。而為了解決這個問題，本篇論文設計的改良版同態加密之多訊息私密資訊擷取架構能使使用者一次的詢問便可取回多個n位元資料，以提升私密資訊擷取的效率。除此之外，我們完成了架構的分析，提出正確性及安全性的證明，並且分析了通訊複雜度。
Private information retrieval (PIR) is a privacy protection that allows users to retrieve information from a database without revealing any information about the retrieved data to the server.
Since the pioneering work of Chor \\textit{et al}. and of Kushilevitz and Ostrovsky, PIR has been extensively studied (especially the single database setting) in the past two decades. However, most protocols only allow users to retrieve only one data at a time, which leads to high communication costs. To solve this issue, this work proposes a multi-value private information retrieval protocol using group homomorphic encryption, which allows users to retrieve multiple values at a time.
We compared our work with that of Ostrovsky and Skeith and show that retrieving multiple data at a time can significantly reduce communication costs. Furthermore, we analyze the structure, provide a rigorous proof that if the underlying group homomorphic encryption is secure, and discuss the communication complexity. |
| Reference: | [1] C. Aguilar-Melchor, J. Barrier, L. Fousse, and M.-O. Killijian. XPIR : Private Information Retrieval for Everyone. Proceedings on Privacy Enhancing Technologies, (2):155–174, 2016.
[2] C. Aguilar-Melchor, P. Gaborit, and J. Herranz. Additively Homomorphic Encryption with D-operand Multiplications. In Annual Cryptology Conference, pages 138–154, 2008.
[3] Y. Arkady. A General Framework for One Database Private Information Retrieval. Online at http://www.cs.umd.edu/Grad/scholarlypapers/papers/Arkady-pircomp.pdf, 2015.
[4] A. Beimel and Y. Ishai. Information-theoretic Private Information Retrieval: A Unified Construction. In International Colloquium on Automata, Languages, and Programming, pages 912–926, 2001.
[5] G. Brassard, C. Crepeau, and J. Robert. All-or-nothing Disclosure of Secrets. In Conference on the Theory and Application of Cryptographic Techniques, 1986.
[6] J. Bringer, H. Chabanne1, D. Pointcheval, and Q. Tang. Extended Private Information Retrieval
and Its Application in Biometrics Authentications. In International Conference on Cryptology
and Network Security, pages 175–193, 2007.
[7] C. Cachin, S. Micali, and M. Stadler. Computationally Private Information Retrieval with Polylogarithmic Communication. In International Conference on the Theory and Applications of Cryptographic Techniques, pages 402–414, 1999.
[8] J. Camenisch, M. Dubovitskaya, and G. Neven. Unlinkable Priced Oblivious Transfer with Rechargeable Wallets. Proceedings of FC 2010, January 2010.
[9] A.-M. Carlos and G. Philippe. A Lattice-based Computationally-efficient Private Information Retrieval Protocol. Cryptol. ePrint Arch., Report, page 446, 2007.
[10] Y. Chang. Single Database Private Information Retrieval with Logarithmic Communication. In Australasian Conference on Information Security and Privacy, pages 50–61, 2004.
[11] D. Changyu and L. Chen. A Fast Single Server Private Information Retrieval Protocol with Low Communication Cost. In M. Kutyłowski and J. Vaidya, editors, Computer Security - ESORICS 2014, pages 380–399, Cham, 2014. Springer International Publishing.
[12] B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan. Private Information Retrieval. In Proceedings of IEEE 36th Annual Symposium on Foundations of Computer Science, pages 41–50, 1995.
[13] B. Chor, E. Kushilevitz, O. Goldreich, and M. Sudan. Private Information Retrieval. J.ACM, vol. 45, no. 6, pages 965–981, 1998.
[14] C.-K. Chu and W.-G. Tzeng. Efficient K-out-of-n Oblivious Transfer Schemes. Journal of Universal Computer Science, 2008.
[15] G. Craig. Fully Homomorphic Encryption Using Ideal Lattices. In Proceedings of the FortyFirst Annual ACM Symposium on Theory of Computing, STOC ’09, pages 169–178, New York, NY, USA, 2009. Association for Computing Machinery.
[16] G. D. Crescenzo, T. Malkin, and R. Ostrovsky. Single Database Private Information Retrieval Implies Oblivious Transfer. In International Conference on the Theory and Applications of Cryptographic Techniques, pages 122–138, 2000.
[17] C. Devet, I. Goldberg, and N. Heninger. Optimally Robust Private Information Retrieval. In Presented as part of the 21st USENIX Security Symposium (USENIX Security 12), pages 269– 283, 2012.
[18] S. Even, O. Goldreich, and A. Lempel. A Randomized Protocol for Signing Contracts. Communications of the ACM, 1985.
[19] K. Eyal and O. Rafail. Replication is Not Needed: Single Database, Computationally-private Information Retrieval. In Proceedings 38th Annual Symposium on Foundations of Computer Science, pages 364–373. IEEE, 1997.
[20] Y. Gentner, Y. Ishai, E. Kushilevitz, and T. Malkin. Protecting Data Privacy in Private Information Retrieval Schemes. Journal of Computer and System Sciences, 60(3), pages 592–629, 2000.
[21] C. Gentry. Fully Homomorphic Encryption Scheme. PhD Thesis, Stanford University,, 2009.
[22] C. Gentry. Fully Homomorphic Encryption using Ideal Lattices. Proc. STOC ’09, pages 169–178, 2009.
[23] C. Gentry. Computing Arbitrary Functions of Encrypted Data. Communications of the ACM, pages 97–105, 2010.
[24] C. Gentry. Toward Basing Fully Homomorphic Encryption on Worst-case Hardness. Proc. CRYPTO ’10, pages 116–137, 2010.
[25] C. Gentry and Z. R. S. Single Database Private Information Retrieval with Constant Communication Rate. In International Colloquium on Automata, Languages, and Programming, pages 803–815, 2005.
[26] O. Goldreich. Foundations of Cryptography: volume 1, Basic Tools. Cambridge University Press, 2007.
[27] A. Heidarzadeh, S. Kadhe, S. El Rouayheb, and A. Sprintson. Single-server Multi-Message Individually-Private Information Retrieval with Side Information. In 2019 IEEE International Symposium on Information Theory (ISIT), pages 1042–1046, 2019.
[28] E. Kushilevitz and R. Ostrovsky. One-way Trapdoor Permutations are Sufficient for Non-trivial Single-server Private Information Retrieval. In International Conference on the Theory and Applications of Cryptographic Techniques, pages 104–121, 2000.
[29] W. Lifei, Z. Haojin, C. Zhenfu, D. Xiaolei, W. Jia, C. Yunlu, and V. A. V. Security and Privacy for Storage and Computation in Cloud Computing. Information Sciences, pages 371–386, 2014.
[30] H. Lipmaa. An Oblivious Transfer Protocol with Log-squared Communication. In International Conference on Information Security, pages 314–328, 2005.
[31] H. Lipmaa. First CPIR Protocol with Data-dependent Computation. In International Conference on Information Security and Cryptology, pages 193–210, 2009.
[32] A. Lliev and S. W. Smith. Protecting Client Privacy with Trusted Computing at the Server. In IEEE Security & Privacy, pages 20–28, 2005.
[33] M. Naor and B. Pinkas. Oblivious Transfer and Polynomial Evaluation. In Proceedings of the thirty-first annual ACM symposium on Theory of computing, pages 245 254, 1999.
[34] M. Naor and B. Pinkas. Oblivious Transfer with Adaptive Queries. In Annual International Cryptology Conference, pages 573–590, 1999.
[35] K. Nesrine and L. Maryline. Data Security and Privacy Preservation in Cloud Storage Environments based on Cryptographic Mechanisms. Computer Communications, pages 120–141, 2017.
[36] F. G. Olumofin. Practical Private Information Retrieval. University of Waterloo, 2011.
[37] P. Pascal. Public-key Cryptosystems based on Composite Degree Residuosity Classes. In International Conference on the Theory and Applications of Cryptographic Techniques, pages 223– 238. Springer, 1999.
[38] P. Pascal and P. David. Efficient Public-Key Cryptosystems Provably Secure against Active Adversaries. In K.-Y. Lam, E. Okamoto, and C. Xing, editors, Advances in Cryptology - ASIACRYPT’99, pages 165–179. Springer Berlin Heidelberg, 1999.
[39] M. O. Rabin. How to Exchange Secrets by Oblivious Transfer. Technical Report TR-81, 1981.
[40] O. Rafail and W. E. Skeith. A Survey of Single-database Private Information Retrieval: Techniques and Applications. In T. Okamoto and X. Wang, editors, Public Key Cryptography – PKC 2007, pages 393–411. Springer Berlin Heidelberg”, 2007.
[41] R. L. Rivest, A. Shamir, and L. Adleman. A Method for Obtaining Digital Signatures and Publickey Cryptosystems. Communications of the ACM, pages 120–126, 1978.
[42] F. Saint-Jean. Java Implementation of a Single-database Computationally Symmetric Private Information Retrieval (cSPIR) protocol. 2005.
[43] R. Sion and B. Carbunar. On the Computational Practicality of Private Information Retrieval. Proceedings of the Network and Distributed Systems Security Symposium, 2007.
[44] J. Stern. A New and Efficient All-or-nothing Disclosure of Secrets Protocol. In International Conference on the Theory and Application of Cryptology and Information Security, pages 357–371, 1998.
[45] Z. Sun, J. Yu, P. Wang, and L. Xu. Symmetrically Private Information Retrieval based on Blind Quantum Computing. Physical Review A, 91(5):052303, 2015.
[46] C. Wang, Q. Wang, K. Ren, and W. Lou. Privacy-Preserving Public Auditing for Data Storage Security in Cloud Computing. In 2010 Proceedings IEEE INFOCOM, pages 1–9, 2010.
[47] S. Wang and X. Ding. Private Information Retrieval using Trusted Hardware. In D. Gollmann, J. Meier, and A. Sabelfeld, editors, Computer Security–ESORICS 2006, pages 49–64. Springer, Berlin, Heidelberg, 2006.
[48] G. Yael, I. Yuval, K. Eyal, and M. Tal. Protecting Data Privacy in Private Information Retrieval Schemes. Journal of Computer and System Sciences, 60(3):592–629, 2000.
[49] X. Yi, M. Kaosar, R. Paulet, and E. Bertino. Single-database Private Information Retrieval from Fully Homomorphic Encryption. IEEE Trans. on Knowledge and Data Eng., pages 1125–1134, 2013.
[50] X. Yi, R. Paulet, and E. Bertino. Private Information Retrieval. Morgan & Claypool, 2013. |
| Description: | 碩士
國立政治大學
資訊科學系
107753036 |
| Source URI: | http://thesis.lib.nccu.edu.tw/record/#G0107753036 |
| Data Type: | thesis |
| DOI: | 10.6814/NCCU202001380 |
| Appears in Collections: | [資訊科學系] 學位論文
|
Files in This Item:
| File |
Description |
Size | Format | |
|---|
| 303601.pdf | | 672Kb | Adobe PDF2 | 108 | View/Open |
|
All items in 政大典藏 are protected by copyright, with all rights reserved.
|
