為了保護資料的機密性, 在上傳至雲端之前, 對資料進行加密已成為一種常見的方式。然而, 加密後的檔案難以進行搜尋, 這對雲端的資料管理和利用帶來了挑戰。可搜尋式加密技術可以解決這個問題, 使資料在保持加密狀態的同時, 仍能有效地進行關鍵字搜尋。隨著量子電腦的快速發展, 抗量子攻擊的加密技術已成為一項不可或缺的關鍵要求。因此本論文提出一種新的加密機制, 該機制不僅能夠抵禦量子電腦攻擊, 並支援AND, OR關鍵字, 加密者可以根據自身需求組合關鍵字, 精準定位關鍵字資訊, 且於密文中設置時間失效機制, 能讓過期的密文無法被使用者搜尋到。其次, 本機制採用代理轉加密的方式, 將加密工作委託給雲端代理伺服器執行, 有效減輕使用者端的計算負擔, 作為一種身份加密機制, 本機制無需額外管理憑證, 降低了管理憑證所造成的計算量與傳輸量。此外, 本論文在理論分析的基礎上, 於 D-RLWE假設下, 完成了所提出機制的安全性證明。最後, 本研究將透過實作驗證, 以驗證該機制能在雲端環境中被有效應用。

The rapid advancement of science and technology has led to the emergence of quantum computers, posing a significant threat to traditional encryption schemes. As a result, there is a pressing need to develop encryption methods that can withstand quantum attacks. This thesis proposes an IBE scheme with a time-invalidation mechanism to revoke expired ciphertext. What sets this scheme apart is its support for multi-keyword search, AND/OR operations and proxy encryption to delegate encryption workload to a proxy server, reducing the computing load on the user side. This IBE scheme eliminates the need for certificates, reducing computation and transmission costs. The proposed scheme's security is based on the D-RLWE assumption. We also validate the proposed scheme through implementation.

Table of Contents
學位審定書（中）. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i
學位審定書（英）. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
誌謝 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi
摘要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii
Chapter 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Thesis Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Chapter 2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.1 Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 Ring Learning-With-Error Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3 Discrete Gaussians . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.4 Lattice Trapdoors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.5 Montgomery Reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.6 Barrett Reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.7 Tree-Based Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
Chapter 3 Related Works. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .16
3.1 Yang et al.’s Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.2 Zhang et al.’s Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.3 Yu et al.’s Scheme. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .19
3.4 Zhuang and Fan’s Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
viii
Chapter 4 The Proposed Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.1 The System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.2 The Security Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.2.1 Ciphertext Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.2.2 Keyword-Search Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.3 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.4 Correctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.4.1 Decryption Correctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.4.2 Search Correctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.5 Security Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.5.1 Ciphertext Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.5.2 Keyword Search Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
Chapter 5 System Implementation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .46
5.1 Data Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
5.2 Matrix Form of Polynomial. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .47
5.3 Computation Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.4 Tree Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5.5 Lattice Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.6 Examples. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .57
Chapter 6 Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
6.1 Transmission Cost . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
6.2 Computation Cost. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .74
6.3 Summary. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .78
Chapter 7 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
Appendix A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
The Implementation Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

Bibliography
[1] A. Shamir, “Identity-based cryptosystems and signature schemes,” in Advances
in Cryptology: Proceedings of CRYPTO 84 4, pp. 47–53, Springer, 1985.
[2] M. Blaze, G. Bleumer, and M. Strauss, “Divertible protocols and atomic proxy
cryptography,” in International conference on the theory and applications of
cryptographic techniques, pp. 127–144, Springer, 1998.
[3] M. Green and G. Ateniese, “Identity-based proxy re-encryption,” in Applied
Cryptography and Network Security: 5th International Conference, ACNS 2007,
Zhuhai, China, June 5-8, 2007. Proceedings 5, pp. 288–306, Springer, 2007.
[4] D. X. Song, D. Wagner, and A. Perrig, “Practical techniques for searches on
encrypted data,” in Proceeding 2000 IEEE symposium on security and privacy.
S&P 2000, pp. 44–55, IEEE, 2000.
[5] D. Boneh, G. Di Crescenzo, R. Ostrovsky, and G. Persiano, “Public key encryp-
tion with keyword search,” in Advances in Cryptology-EUROCRYPT 2004: In-
ternational Conference on the Theory and Applications of Cryptographic Tech-
niques, Interlaken, Switzerland, May 2-6, 2004. Proceedings 23, pp. 506–522,
Springer, 2004.
[6] O. Regev, “On lattices, learning with errors, random linear codes, and cryp-
tography,” in Journal of the ACM (JACM), vol. 56, pp. 1–40, ACM New York,
NY, USA, 2009.
[7] V. Lyubashevsky, C. Peikert, and O. Regev, “On ideal lattices and learning
with errors over rings,” in Advances in Cryptology–EUROCRYPT 2010: 29th
82
Annual International Conference on the Theory and Applications of Crypto-
graphic Techniques, French Riviera, May 30–June 3, 2010. Proceedings 29,
pp. 1–23, Springer, 2010.
[8] E.-S. Zhuang and C.-I. Fan, “Multi-keyword searchable identity-based proxy
re-encryption from lattices,” Mathematics, vol. 11, no. 18, p. 3830, 2023.
[9] L. Ducas and A. Durmus, “Ring-lwe in polynomial rings,” in Public Key
Cryptography–PKC 2012: 15th International Conference on Practice and The-
ory in Public Key Cryptography, Darmstadt, Germany, May 21-23, 2012. Pro-
ceedings 15, pp. 34–51, Springer, 2012.
[10] M. Ajtai, “Generating hard instances of the short basis problem,” in Au-
tomata, Languages and Programming: 26th International Colloquium, ICALP’
99 Prague, Czech Republic, July 11–15, 1999 Proceedings 26, pp. 1–9, Springer,
1999.
[11] D. Micciancio and C. Peikert, “Trapdoors for lattices: Simpler, tighter, faster,
smaller,” in Annual International Conference on the Theory and Applications
of Cryptographic Techniques, pp. 700–718, Springer, 2012.
[12] N. Genise and D. Micciancio, “Faster gaussian sampling for trapdoor lattices
with arbitrary modulus,” in Advances in Cryptology–EUROCRYPT 2018: 37th
Annual International Conference on the Theory and Applications of Crypto-
graphic Techniques, Tel Aviv, Israel, April 29-May 3, 2018 Proceedings, Part I
37, pp. 174–203, Springer, 2018.
[13] P. Bert, P.-A. Fouque, A. Roux-Langlois, and M. Sabt, “Practical implemen-
tation of ring-SIS/LWE based signature and IBE,” in Post-Quantum Cryptog-
83
raphy: 9th International Conference, PQCrypto 2018, Fort Lauderdale, FL,
USA, April 9-11, 2018, Proceedings 9, pp. 271–291, Springer, 2018.
[14] P. L. Montgomery, “Modular multiplication without trial division,” Mathemat-
ics of computation, vol. 44, no. 170, pp. 519–521, 1985.
[15] Nayuki, “Montgomery reduction algorithm.” https://www.nayuki.io/page/
montgomery-reduction-algorithm, Last updated on 2019.
[16] P. Barrett, “Implementing the rivest shamir and adleman public key encryption
algorithm on a standard digital signal processor,” in Conference on the Theory
and Application of Cryptographic Techniques, pp. 311–323, Springer, 1986.
[17] X. Yu, C. Xu, B. Dou, and Y. Wang, “Multi-user search on the encrypted
multimedia database: lattice-based searchable encryption scheme with time-
controlled proxy re-encryption,” Multimedia Tools and Applications, vol. 80,
pp. 3193–3211, 2021.
[18] E. Zhang, Y. Hou, and G. Li, “A lattice-based searchable encryption scheme
with the validity period control of files,” Multimedia Tools and Applications,
vol. 80, pp. 4655–4672, 2021.
[19] F. Wang, H. Xiao, J. Wang, Y. Wang, and C. Cao, “Efficient secure channel
free identity-based searchable encryption schemes with privacy preserving for
cloud storage service,” Journal of Systems Architecture, p. 103089, 2024.
[20] Y. Yang and M. Ma, “Conjunctive keyword search with designated tester and
timing enabled proxy re-encryption function for e-health clouds,” IEEE Trans-
84
actions on Information Forensics and Security, vol. 11, no. 4, pp. 746–759,
2015.
[21] GCCteam, “Gcc 13 release series.” https://gcc.gnu.org/gcc-13/, Last up-
dated on 2023.
[22] GNUteam, “The gnu multiple precision arithmetic library.” https://gmplib.
org/, Last updated on 2023.
[23] T. IEEE and T. O. Group, “The open group base specifications is-
sue 6.” https://pubs.opengroup.org/onlinepubs/009695399/functions/
gmtime.html, Last updated on 2004.
[24] M. R. Albrecht, R. Player, and S. Scott, “On the concrete hardness of learning
with errors,” Journal of Mathematical Cryptology, vol. 9, no. 3, pp. 169–203,
2015.
[25] B. Applebaum, D. Cash, C. Peikert, and A. Sahai, “Fast cryptographic prim-
itives and circular-secure encryption based on hard learning problems,” in
Advances in Cryptology-CRYPTO 2009: 29th Annual International Cryptol-
ogy Conference, Santa Barbara, CA, USA, August 16-20, 2009. Proceedings,
pp. 595–618, Springer, 2009.