A Searchable Encryption Scheme Based on Approximate Trapdoor Sampling

Qi Lijun; Zhuang Jincheng

doi:10.7544/issn1000-1239.202440482

Journal of Computer Research and Development > 2025 > Accepted Manuscript > DOI: 10.7544/issn1000-1239.202440482 CSTR: 32373.14.issn1000-1239.202440482

Qi Lijun, Zhuang Jincheng. A Searchable Encryption Scheme Based on Approximate Trapdoor Sampling[J]. Journal of Computer Research and Development. DOI: 10.7544/issn1000-1239.202440482

Citation:

Qi Lijun, Zhuang Jincheng. A Searchable Encryption Scheme Based on Approximate Trapdoor Sampling[J]. Journal of Computer Research and Development. DOI: 10.7544/issn1000-1239.202440482

Citation:

Qi Lijun, Zhuang Jincheng. A Searchable Encryption Scheme Based on Approximate Trapdoor Sampling[J]. Journal of Computer Research and Development. DOI: 10.7544/issn1000-1239.202440482

PDF (2341 KB)

A Searchable Encryption Scheme Based on Approximate Trapdoor Sampling

Qi Lijun^{1, 2,},
Zhuang Jincheng^{1, 3, ,}

1.
School of Cyber Science and Technology, Shandong University, Qingdao, Shandong 266237
2.
Key Laboratory of Cryptologic Technology and Information Security (Shandong University), Ministry of Education, Jinan 250100
3.
Quancheng Laboratory, Jinan 250103

Funds: This work was supported by the National Key Research and Development Program of China（2021YFB3100200）.

More Information

Author Bio:
Qi Lijun: born in 1998. PhD candidate. Her main research interests include information security and applied cryptography

Zhuang Jincheng: born in 1987. PhD, professor. His main research interests are in the areas of cryptography and information security.（jzhuang @sdu. edu.cn）
Received Date: June 04, 2024
Revised Date: January 12, 2025
Accepted Date: January 25, 2025
Available Online: January 25, 2025

Graphical Abstract

Abstract

Abstract

Public key encryption with keyword search (PEKS) over lattice plays an important role in ensuring the privacy, confidentiality, and flexibility of outsourced data while resisting quantum attacks. However, most existing lattice-based PEKS schemes are limited by the underlying preimage sampling algorithm, which suffers from high storage overhead or low efficiency issues. To address the above problems, an optimized public key encryption with keyword search scheme is first proposed. The scheme utilizes a new approximate trapdoor sampling algorithm to improve the computational efficiency. The algorithm outputs an approximate rather than an exact preimage. Then, a combination of non-spherical Gaussian sampling technique and an ideal extendable-output function is used to reduce key and trapdoor storage. Furthermore, an extended scheme with forward security and backward security is introduced to address the basic scheme’s update and search operation leakage. To avoid newly updated ciphertexts matching previous trapdoors, i.e., forward security, the key is periodically updated through a lattice-based delegation mechanism. To prevent subsequent searches from leaking information about deleted files, i.e., backward security, the addition and deletion of files is achieved by combining the bitmap index and lattice-based homomorphic encryption scheme. Theoretical analysis and experimental results exhibit that, compared with the efficient PEKS scheme, the proposed scheme reduces the public key storage overhead by 4.6% and the trapdoor storage overhead by 50.1%, and improves the efficiency of encryption, trapdoor generation, and search by 11.11%, 2.5%, and 26.15%, respectively.
- privacy protection,
- encrypted data retrieval,
- searchable encryption,
- approximate trapdoor,
- forward security,
- backward security

FullText(HTML)

References (37)

References

[1]	Song D X, Wagner D, Perrig A. Practical techniques for searches on encrypted data[C]//Proc of the 2000 IEEE Symp on Security and Privacy. Piscataway, NJ: IEEE, 2000: 44−55
[2]	Boneh D, Di Crescenzo G, Ostrovsky R, et al. Public key encryption with keyword search[C]// Proc of the 2nd Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2004: 506−522
[3]	Huang Qiong, Li Hongbo. An efficient public-key searchable encryption scheme secure against inside keyword guessing attacks[J]. Information Sciences, 2017, 403: 1−14
[4]	Rhee H S, Park J H, Susilo W, et al. Trapdoor security in a searchable public-key encryption scheme with a designated tester[J]. Journal of Systems and Software, 2010, 83(5): 763−771 doi: 10.1016/j.jss.2009.11.726
[5]	Yu Yong, Ni Jianbing, Yang Haomiao, et al. Efficient public key encryption with revocable keyword search[J]. Security and Communication Networks, 2014, 7(2): 466−472 doi: 10.1002/sec.790
[6]	Anada H, Kanaoka A, Matsuzaki N, et al. Key-updatable public-key encryption with keyword search: Models and generic constructions[C]// Proc of the 23rd Australasian Conf on Information Security and Privacy. Berlin: Springer, 2018: 341−359
[7]	Di Crescenzo G, Saraswat V. Public key encryption with searchable keywords based on Jacobi symbols[C]// Proc of the 8th Int Conf on Cryptology in India. Berlin: Springer, 2007: 282−296
[8]	Zhou Xiaotong, He Debiao, Ning Jianting, et al. Single-server public-key authenticated encryption with keyword search and its application in IIoT[J]. IEEE Transactions on Network Science and Engineering, 2024, 11(1): 404−415 doi: 10.1109/TNSE.2023.3300716
[9]	Gu Chunxiang, Zheng Yonghui, Kang Fei, et al. Keyword search over encrypted data in cloud computing from lattices in the standard model[C]// Proc of the 2nd Int Conf on Cloud Computing and Big Data. Berlin: Springer, 2015: 335−343
[10]	Kuchta V, Markowitch O. Multi-authority distributed attribute- based encryption with application to searchable encryption on lattices[C] //Proc of the 2nd Int Conf on Cryptology and Malicious Security. Berlin: Springer, 2017: 409−435
[11]	Yang Yang, Zheng Xianghan, Chang V, et al. Semantic keyword searchable proxy re-encryption for postquanm secure cloud storage[J]. Concurrency and Computation: Practice and Experience, 2017, 29(19): e4211 doi: 10.1002/cpe.4211
[12]	Zhang Xiaojun, Xu Chunxiang, Wang Huaxiong, et al. FS-PEKS: Lattice-based forward secure public-key encryption with keyword search for cloud-assisted industrial Internet of things[J]. IEEE Transactions on Dependable and Secure Computing, 2019, 18(3): 1019−1032
[13]	Zhang Yupeng, Katz J, Papamanthou C. All your queries are belong to us: The power of file-Injection attacks on searchable encryption[C]// Proc of the 25th USENIX Conf on Security Symp. Berkeley, CA: USENIX Association, 2016: 707−720
[14]	Bost R, Minaud B, Ohrimenko O. Forward and backward private searchable encryption from constrained cryptographic primitives[C]//Proc of the 2017 ACM SIGSAC Conf on Computer and Communications Security. New York: ACM, 2017: 1465−1482
[15]	Abdalla M, Bellare M, Catalano D, et al. Searchable encryption revisited: Consistency properties, relation to anonymous IBE, and extensions[C]// Proc of the 25th Annual International Cryptology Conf. Berlin: Springer, 2005: 205−222
[16]	Yu Yang, Jia Huiwen, Wang Xiaoyun. Compact lattice gadget and its applications to hash-and-sign signatures[C]// Proc of the 43rd Annual Int Cryptology Conf. Berlin: Springer, 2023: 390−420
[17]	Jia Huiwen, Hu Yupu, Tang Chunming, et al. Towards compact identity-based encryption on ideal lattices[C]// Proc of the Cryptographer's Track at the RSA Conf. Berlin: Springer, 2024: 354−378
[18]	Jia Huiwen, Hu Yupu, Tang Chunming. Lattice-based hash- and-sign signatures using approximate trapdoor, revisited[J]. IET Information Security, 2022, 16(1): 41−50 doi: 10.1049/ise2.12039
[19]	Fan J, Vercauteren F. Somewhat practical fully homomorphic encryption[J]. Cryptology ePrint Archive, 2012.144, 2012
[20]	Chan C, Ioannidis Y. Bitmap index design and evaluation[C]// Proc of the 1998 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 1998: 355−366
[21]	Behnia R, Ozmen M O, Yavuz A A. Lattice-based public key searchable encryption from experimental perspectives[J]. IEEE Transactions on Dependable and Secure Computing, 2018, 17(6): 1269−1282
[22]	Qi Lijun, Zhuang Jincheng. RLWE-based public key searchable encryption: Securer, faster, and lower end-to-end delay for cloud computing[J]. The Journal of Supercomputing, 2024, 80(2): 2767−2798 doi: 10.1007/s11227-023-05574-9
[23]	Lyubashevsky V, Peikert C, Regev O. On ideal lattices and learning with errors over rings[C/OL]// Proc of the 29th Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2010[2025-01-02]. https://dl.acm.org/doi/10.1145/2535925
[24]	Stehlé D, Steinfeld R, Tanaka K, et al. Efficient public key encryption based on ideal lattices[C]// Proc of the 15th Int Conf on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2009: 617−635
[25]	Agrawal S, Boneh D, Boyen X. Efficient lattice (H) IBE in the standard model[C]// Proc of the 29th Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2010: 553−572
[26]	Micciancio D, Peikert C. Trapdoors for lattices: Simpler, tighter, faster, smaller[C]// Proc of the 31st Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2012: 700−718
[27]	Genise N, Micciancio D. Faster Gaussian sampling for trapdoor lattices with arbitrary modulus[C]//Proc of the 37th Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2018: 174−203
[28]	Wang Peng, Chen Biwen, Xiang Tao, et al. Lattice-based public key searchable encryption with fine-grained access control for edge computing[J]. Future Generation Computer Systems, 2022, 127: 373−383 doi: 10.1016/j.future.2021.09.012
[29]	Zuo Cong, Sun Shifeng, Liu J K, et al. Forward and backward private DSSE for range queries[J]. IEEE Transactions on Dependable and Secure Computing, 2020, 19(1): 328−338
[30]	Agrawal S, Boneh D, Boyen X. Lattice basis delegation in fixed dimension and shorter-ciphertext hierarchical IBE[C]//Proc of the 37th Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2010: 98−115
[31]	Zeng Ming, Qian Haifeng, Chen Jie, et al. Forward secure public key encryption with keyword search for outsourced cloud storage[J]. IEEE Transactions on Cloud Computing, 2019, 10(1): 426−438
[32]	Emura K. Generic construction of forward secure public key authenticated encryption with keyword search[C]// Proc of the 22nd Int Conf on Applied Cryptography and Network Security. Berlin: Springer, 2024: 237−256
[33]	Xu Shiyuan, Cao Yibo, Chen Xue, et al. Post-quantum public-key authenticated searchable encryption with forward security: General construction, and applications[C]// Proc of the 19th Int Conf on Information Security and Cryptology. Berlin: Springer, 2023: 274−298
[34]	汤永利,李静然,闫玺玺,等. 支持联合搜索的动态前向安全可搜索加密方案[J]. 计算机研究与发展,2022,59(8):1853−1866 doi: 10.7544/issn1000-1239.20210260 Tang Yongli, Li Jingran, Yan Xixi, et al. A forward secure dynamic searchable encryption scheme supporting conjunctive search[J]. Journal of Computer Research and Development, 2022, 59(8): 1853−1866 (in Chinese) doi: 10.7544/issn1000-1239.20210260
[35]	Gan Qingqing, Zuo Cong, Wang Jianfeng, et al. Dynamic searchable symmetric encryption with forward and backward privacy: A survey[C]// Proc of the 13th Int Conf on Network and System Security. Berlin: Springer, 2019: 37−52
[36]	张蓝蓝,曹卫东,王怀超. 一种支持联合搜索的多用户动态对称可搜索加密方案[J]. 计算机研究与发展,2022,59(10):2309−2322 doi: 10.7544/issn1000-1239.20220494 Zhang Lanlan, Cao Weidong, Wang Huaichao. A multi-user dynamic symmetric searchable encryption scheme supporting conjunctive search[J]. Journal of Computer Research and Development, 2022, 59(10): 2309−2322 (in Chinese) doi: 10.7544/issn1000-1239.20220494
[37]	黄一才,郁滨. 一种基于SHVE的连接查询动态对称可搜索加密方案[J]. 计算机研究与发展,2024,61(6):1545−1558 doi: 10.7544/issn1000-1239.202220924 Huang Yicai, Yu Bin. Dynamic searchable symmetric encryption scheme for conjunctive queries based on SHVE[J]. Journal of Computer Research and Development, 2024, 61(6): 1545−1558 (in Chinese) doi: 10.7544/issn1000-1239.202220924