本文提出了一種解決基於RLWE的私有資訊檢索（PIR）方案效率瓶頸的方法。由於基於RLWE的PIR在查詢產生和回應擷取過程中耗費大量時間，單位時間內可擷取的資料量受到固有限制。為了克服這一瓶頸，我們引入了一種權衡機制，允許在單次查詢中檢索多個資料項，同時僅略微增加往返時間。這種方法有效地提高了可檢索資料量的上限，從而在不損害PIR隱私保障的前提下，顯著提升了整體查詢效率。

In this paper, we propose a method to address the efficiency limitations of RLWE-based PIR (Private Information Retrieval) schemes. Since RLWEbased PIR consumes substantial time during query generation and reply extraction, the amount of data retrievable per unit time is inherently constrained. To overcome this bottleneck, we introduce a trade-off mechanism that allows multiple data items to be retrieved within a single query while only slightly increasing the round-trip time. This approach effectively raises the upper bound of retrievable data volume, thereby significantly improving overall query efficiency without compromising the privacy guarantees of PIR.

[1] O. G. M. S. B Chor, E Kushilevitz, “Private information retrieval.” Journal of the ACM (JACM), pp. 41–41, 1995.

[2] E. Kushilevitz and R. Ostrovsky, “Replication is not needed: Single database, computationally-private information retrieval,” Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS), pp. 364–373, 1997.

[3] P. Paillier, “Public-key cryptosystems based on composite degree residuosity classes,” PhD Thesis, Université de Paris 8, 1999.

[4] C. Gentry, “Fully homomorphic encryption using ideal lattices,” Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), pp. 169–178, 2009.

[5] L. F. CA Melchor, J Barrier and M. Killijian, “Xpir : Private information retrieval for everyone,” Proceedings on Privacy Enhancing Technologies, 2016.

[6] C. Aguilar-Melchor, J. Barrier, S. Guelton, A. Guinet, M. Killijian, and T. Lepoint, “SEALPIR: A practical pir construction,” Proceedings on Privacy Enhancing Technologies (PETS), pp. 26–44, 2018.

[7] R. Creutzburg and theoretic transforms denburg, UniversityV. Labunets, “The (ntt) – a bibliography of Applied Sciences,early papersuntil 1991,” Departmenton numberFH Branof Comput-ingMedia, 1996, accessed: 2025-11-13. [Online]. Available:https://www.academia.edu/20635244/THE_EARLY_PAPERS_ON_NUMBER_ THEORETIC_TRANSFORMS_NTT_A_BIBLIOGRAPHY_UNTIL_1991

and

[8] Z. Liang and Y. Zhao, “Number theoretic transform and its applications in lattice-based cryptosystems: A survey,” arXiv preprint arXiv:2211.13546, 2022, accessed: 2025-11-13. [Online]. Available: https://arxiv.org/abs/2211.13546

[9] H. C.-G. S. M. V. V. A Henzinger MM Hong, “One server for the price of two:

Simple and fast single-server private information retrieval,” 32nd USENIX Security Symposium (USENIX Security 23), 2023.

[10] S. Patel, J. Y. Seo, and K. Yeo, “Don’t be dense: Efficient keyword PIR for sparse databases,” Proceedings of the 32nd USENIX Security Symposium (USENIX Security ’23), pp. 3853–3870, Aug. 2023. [Online]. Available: https: //www.usenix.org/conference/usenixsecurity23/presentation/patel

[11] H. Asi and E. Yaakobi, “Nearly optimal constructions of pir and batch codes,” arXiv preprint arXiv:1701.07206, 2017.

[12] K. L.-S. S. S Angel, H Chen, “Pir with compressed queries and amortized queryprocessing.” 2018 IEEE symposium on security and privacy (SP),, vol. 41, no. 6, pp. 1–16, 2018.

[13] S. S. S Angel, “Unobservable communication over fully untrusted infrastructure,” 12th USENIX Symposium on Operating Systems, 2016.

[14] Z.-Y. L. Hsiang-Chen Hsu and K. C. Raylin Tso, “A study on multi-message private information retrieval using homomorphic encryption.” IEEE, 2020.

[15] S. J. H Sun, “The capacity of symmetric private information retrieval,” IEEE Transactions on Information Theory,, 2018.

[16] W. Tzeng, “E￿cient 1-out-n oblivious transfer schemes,” Public Key Cryptography:

5th International Workshop on Practice and Theory in …,, 2002.

[17] C. P. . O. R. Vadim Lyubashevsky, “On ideal lattices and learning with errors over rings,” EUROCRYPT 2010, 2010.

[18] Z. Brakerski1 and V. Vaikuntanathan, “Fully homomorphic encryption from ring-lwe and security for key dependent messages,” Annual cryptology conference, 2011.

[19] O. Regev, “On lattices, learning with errors, random linear codes, and cryptography,” Journal of the ACM, vol. 56, no. 6, pp. 1–40, 2009.

[20] D. Micciancio and O. Regev, “Lattice-based cryptography,” in Post-Quantum Cryptography. Springer, 2009, pp. 147–191.

[21] L. Euler, “Theoremata arithmetica nova methodo demonstrata,” Novi Commentarii academiae scientiarum Petropolitanae, vol. 8, pp. 74–104, 1763.

[22] K. H. Rosen, Elementary Number Theory and Its Applications, 6th ed.Pearson,2010.

[23] R. O. W. E. S. III†, “A survey of single-database pir: Techniques and applications,” International Workshop on Public Key Cryptography, Springer, 2007.

[24] A. Yerukhimovich, “A general framework for one database private information retrieval,” 2008, available at https://www2.seas.gwu.edu/~arkady/publications/ pircomp.pdf.

[25] G. L. Miller, “Riemann’s hypothesis and tests for primality,” STOC ’75: Proceedings of the seventh annual ACM symposium on Theory of computing Pages 234 - 23, 05 May 1975.

[26] M. Rabin, “Probabilistic algorithm for testing primality,” Journal of number theory, 1980.

[27] P. L. Chebyshev, “Mémoire sur les nombres premiers,” Journal de Mathématiques Pures et Appliquées, vol. 17, pp. 366–390, 1850.

[28] V. V. Z Brakerski, C Gentry, “(leveled) fully homomorphic encryption without bootstrapping,” ACM transactions on computation theory., 2014.

[29] V. W. Gianira N. Alfarano, Karan Khathuria, “A survey on single server private information retrieval in a coding theory perspective,” Applicable Algebra in Engineering, Communication and Computing (2023), Received: 12 December 2020 / Accepted: 27 March 2021 /.

[30] H. Riesel, “Prime numbers and computer methods for factorization,” book, 1994.

[31] F. Olumofin and I. Goldberg, “Revisiting the computational practicality of private information retrieval,” Financial Cryptography and Data Security (FC 2011), pp. 158–172, 2011.