{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T00:57:36Z","timestamp":1760057856684,"version":"build-2065373602"},"reference-count":31,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2025,2,24]],"date-time":"2025-02-24T00:00:00Z","timestamp":1740355200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Taiwan Semiconductor Manufacturing Company","award":["MOST 111-2221-E-002-134-MY3","NTU- 112L900902"],"award-info":[{"award-number":["MOST 111-2221-E-002-134-MY3","NTU- 112L900902"]}]},{"name":"Minister of Science and Technology, Taiwan","award":["MOST 111-2221-E-002-134-MY3","NTU- 112L900902"],"award-info":[{"award-number":["MOST 111-2221-E-002-134-MY3","NTU- 112L900902"]}]},{"name":"National Taiwan University","award":["MOST 111-2221-E-002-134-MY3","NTU- 112L900902"],"award-info":[{"award-number":["MOST 111-2221-E-002-134-MY3","NTU- 112L900902"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Cryptography"],"abstract":"<jats:p>This paper explores advancements in the Gentry-Sahai-Waters (GSW) fully homomorphic encryption scheme (FHE), addressing challenges related to message data range limitations and ciphertext size constraints. We leverage the well-known parallelizing technology\u2014the Chinese Remainder Theorem (CRT)\u2014to tackle the message decomposition, significantly expanding the allowable input message range to the entire plaintext space. This approach enables unrestricted message selection in the GSW scheme and supports parallel homomorphic operations without intermediate decryption. Additionally, we adapt existing ciphertext compression techniques, such as the PVW-like scheme, to reduce the memory overhead associated with ciphertexts. Our experimental results demonstrate the effectiveness of combining the proposed CRT-based decomposition with the PVW-like compression in increasing the upper bound of message values and improving the scheme\u2019s capacity for consecutive homomorphic operations. However, compression introduces a trade-off, necessitating a reduced message range due to error accumulation in successive HE operations. This research contributes to enhancing the practicality and efficiency of the GSW encryption scheme for complex computational scenarios while managing the balance between expanded message range, computational complexity, and storage requirements.<\/jats:p>","DOI":"10.3390\/cryptography9010014","type":"journal-article","created":{"date-parts":[[2025,2,24]],"date-time":"2025-02-24T10:04:28Z","timestamp":1740391468000},"page":"14","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Optimizing Message Range and Ciphertext Storage in Gentry\u2013Sahai\u2013Waters Encryption Using Chinese Remainder Theorem and PVW-like Compression Scheme"],"prefix":"10.3390","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-1306-6079","authenticated-orcid":false,"given":"Kung-Wei","family":"Hu","sequence":"first","affiliation":[{"name":"Department of Computer Science and Information Engineering, National Taiwan University, Taipei City 10617, Taiwan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1293-1510","authenticated-orcid":false,"given":"Huan-Chih","family":"Wang","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Information Engineering, National Taiwan University, Taipei City 10617, Taiwan"}]},{"given":"Wun-Ting","family":"Lin","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Information Engineering, National Taiwan University, Taipei City 10617, Taiwan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3631-1551","authenticated-orcid":false,"given":"Ja-Ling","family":"Wu","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Information Engineering, National Taiwan University, Taipei City 10617, Taiwan"}]}],"member":"1968","published-online":{"date-parts":[[2025,2,24]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Gentry, C., Sahai, A., and Waters, B. (2013, January 18\u201322). Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based. Proceedings of the Advances in Cryptology\u2014CRYPTO 2013: 33rd Annual Cryptology Conference, Santa Barbara, CA, USA. Proceedings, Part I.","DOI":"10.1007\/978-3-642-40041-4_5"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Gentry, C., and Halevi, S. (2019). Compressible FHE with applications to PIR. Theory of Cryptography, Springer.","DOI":"10.1007\/978-3-030-36033-7_17"},{"key":"ref_3","unstructured":"Hedglin, N., Phillips, K., and Reilley, A. (2023, July 21). Building a Fully Homomorphic Encryption Scheme in Python. Available online: https:\/\/courses.csail.mit.edu\/6.857\/2019\/project\/15-Hedglin-Phillips-Reilley.pdf."},{"key":"ref_4","first-page":"169","article-title":"On data banks and privacy homomorphisms","volume":"4","author":"Rivest","year":"1978","journal-title":"Found. Secur. Comput."},{"key":"ref_5","unstructured":"Gentry, C. (2009). A Fully Homomorphic Encryption Scheme, Stanford University."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3214303","article-title":"A survey on homomorphic encryption schemes: Theory and implementation","volume":"51","author":"Acar","year":"2018","journal-title":"ACM Comput. Surv. (Csur)"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"100235","DOI":"10.1016\/j.cosrev.2020.100235","article-title":"Homomorphic encryption systems statement: Trends and challenges","volume":"36","author":"Alaya","year":"2020","journal-title":"Comput. Sci. Rev."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3394658","article-title":"Homomorphic encryption for machine learning in medicine and bioinformatics","volume":"53","author":"Wood","year":"2020","journal-title":"ACM Comput. Surv. (CSUR)"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1528","DOI":"10.1109\/JSYST.2021.3064053","article-title":"A study of the applicability of ideal lattice-based fully homomorphic encryption scheme to ethereum blockchain","volume":"15","author":"Chen","year":"2021","journal-title":"IEEE Syst. J."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1007\/s00145-019-09319-x","article-title":"TFHE: Fast fully homomorphic encryption over the torus","volume":"33","author":"Chillotti","year":"2020","journal-title":"J. Cryptol."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Kuo, T.H., and Wu, J.L. (2023). A High Throughput BFV-Encryption-Based Secure Comparison Protocol. Mathematics, 11.","DOI":"10.3390\/math11051227"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Moore, C., O\u2019Neill, M., O\u2019Sullivan, E., Dor\u00f6z, Y., and Sunar, B. (2014, January 1\u20135). Practical homomorphic encryption: A survey. Proceedings of the 2014 IEEE International Symposium on Circuits and Systems (ISCAS), Melbourne, VIC, Australia.","DOI":"10.1109\/ISCAS.2014.6865753"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Lei, X., Guo, R., Zhang, F., Wang, L., Xu, R., and Qu, G. (2019, January 10\u201312). Accelerating homomorphic full adder based on fhew using multicore cpu and gpus. Proceedings of the 2019 IEEE 21st International Conference on High Performance Computing and Communications; IEEE 17th International Conference on Smart City; IEEE 5th International Conference on Data Science and Systems (HPCC\/SmartCity\/DSS); IEEE 17th International Conference on Smart City; IEEE 5th International Conference on Data Science and Systems (HPCC\/SmartCity\/DSS), Zhangjiajie, China.","DOI":"10.1109\/HPCC\/SmartCity\/DSS.2019.00351"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"2840","DOI":"10.1007\/s11227-021-03980-5","article-title":"Efficient number theoretic transform implementation on GPU for homomorphic encryption","volume":"78","author":"Elgezen","year":"2022","journal-title":"J. Supercomput."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"1572","DOI":"10.1109\/JPROC.2022.3205665","article-title":"Survey on fully homomorphic encryption, theory, and applications","volume":"110","author":"Marcolla","year":"2022","journal-title":"Proc. IEEE"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Brakerski, Z., and Vaikuntanathan, V. (2011, January 22\u201325). Efficient Fully Homomorphic Encryption from (Standard) LWE. Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, Palm Springs, CA, USA.","DOI":"10.1109\/FOCS.2011.12"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Brakerski, Z., and Vaikuntanathan, V. (2011). Fully homomorphic encryption from ring-LWE and security for key dependent messages. Advances in Cryptology\u2014CRYPTO 2011, Springer.","DOI":"10.1007\/978-3-642-22792-9_29"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2633600","article-title":"(Leveled) fully homomorphic encryption without bootstrapping","volume":"6","author":"Brakerski","year":"2014","journal-title":"ACM Trans. Comput. Theory (TOCT)"},{"key":"ref_19","first-page":"144","article-title":"Somewhat practical fully homomorphic encryption","volume":"2012","author":"Fan","year":"2012","journal-title":"Cryptol. ePrint Arch."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Ducas, L., and Micciancio, D. (2015). FHEW: Bootstrapping homomorphic encryption in less than a second. Advances in Cryptology\u2014EUROCRYPT 2015, Springer.","DOI":"10.1007\/978-3-662-46800-5_24"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1145\/1666420.1666444","article-title":"Computing arbitrary functions of encrypted data","volume":"53","author":"Gentry","year":"2010","journal-title":"Commun. ACM"},{"key":"ref_22","unstructured":"Cheon, J.H., Kim, A., Kim, M., and Song, Y. (2017, January 3\u20137). Homomorphic encryption for arithmetic of approximate numbers. Proceedings of the Advances in Cryptology\u2014ASIACRYPT 2017: 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China. Proceedings, Part I 23."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Naehrig, M., Lauter, K., and Vaikuntanathan, V. (2011, January 21). Can homomorphic encryption be practical?. Proceedings of the 3rd ACM Workshop on Cloud Computing Security Workshop, Chicago, IL, USA.","DOI":"10.1145\/2046660.2046682"},{"key":"ref_24","unstructured":"Mahdavi, R.A., Diaa, A., and Kerschbaum, F. (2023). HE is all you need: Compressing FHE Ciphertexts using Additive HE. arXiv."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Peikert, C., Vaikuntanathan, V., and Waters, B. (2008). A framework for efficient and composable oblivious transfer. Advances in Cryptology\u2013CRYPTO 2008, Springer.","DOI":"10.1007\/978-3-540-85174-5_31"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Brakerski, Z., D\u00f6ttling, N., Garg, S., and Malavolta, G. (2019). Leveraging linear decryption: Rate-1 fully-homomorphic encryption and time-lock puzzles. Theory of Cryptography, Springer.","DOI":"10.1007\/978-3-030-36033-7_16"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Mukherjee, P., and Wichs, D. (2016, January 8\u201312). Two round multiparty computation via multi-key FHE. Proceedings of the Advances in Cryptology\u2014EUROCRYPT 2016: 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria. Proceedings, Part II 35.","DOI":"10.1007\/978-3-662-49896-5_26"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Micciancio, D., and Peikert, C. (2012). Trapdoors for lattices: Simpler, tighter, faster, smaller. Advances in Cryptology\u2014 EUROCRYPT 2012, Springer.","DOI":"10.1007\/978-3-642-29011-4_41"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Halevi, S. (2017). Homomorphic encryption. Tutorials on the Foundations of Cryptography: Dedicated to Oded Goldreich, Springer.","DOI":"10.1007\/978-3-319-57048-8_5"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Regev, O. (2005, January 22\u201324). On lattices, learning with errors, random linear codes, and cryptography. Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA.","DOI":"10.1145\/1060590.1060603"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Yuan, M., Wang, D., Zhang, F., Wang, S., Ji, S., and Ren, Y. (2022). An examination of multi-key fully homomorphic encryption and its applications. Mathematics, 10.","DOI":"10.3390\/math10244678"}],"container-title":["Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2410-387X\/9\/1\/14\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T16:41:36Z","timestamp":1760028096000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2410-387X\/9\/1\/14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,24]]},"references-count":31,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2025,3]]}},"alternative-id":["cryptography9010014"],"URL":"https:\/\/doi.org\/10.3390\/cryptography9010014","relation":{},"ISSN":["2410-387X"],"issn-type":[{"type":"electronic","value":"2410-387X"}],"subject":[],"published":{"date-parts":[[2025,2,24]]}}}