{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T17:04:48Z","timestamp":1753895088547,"version":"3.41.2"},"reference-count":23,"publisher":"International Association for Cryptologic Research","license":[{"start":{"date-parts":[[2024,4,9]],"date-time":"2024-04-09T00:00:00Z","timestamp":1712620800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2024,6,3]]},"abstract":"Pattern matching methods are essential in various applications where users must disclose highly sensitive information. Among these applications are genomic data analysis, financial records inspection, and intrusion detection processes, all of which necessitate robust privacy protection mechanisms. Balancing the imperative of protecting the confidentiality of analyzed data with the need for efficient pattern matching presents a significant challenge.<\/jats:p>\n In this paper, we propose an efficient post-quantum secure construction that enables arbitrary pattern matching over encrypted data while ensuring the confidentiality of the data to be analyzed. In addition, we address scenarios where a malicious data sender, intended to send an encrypted content for pattern detection analysis, has the ability to modify the encrypted content. We adapt the data fragmentation technique to handle such a malicious sender. Our construction makes use of a well-suited Homomorphic Encryption packing method in the context of fragmented streams and combines homomorphic operations in a leveled mode (i.e. without bootstrapping) to obtain a very efficient pattern matching detection process.<\/jats:p>\n In contrast to the most efficient state-of-the-art scheme, our construction achieves a significant reduction in the time required for encryption, decryption, and pattern matching on encrypted data. Specifically, our approach decreases the time by factors of \n \n 1850<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>, \n \n \n 10<\/mml:mn>\n 6<\/mml:mn>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>, and \n \n 245<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>, respectively, for matching a single pattern, and by factors of \n \n 115<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>, \n \n \n 10<\/mml:mn>\n 5<\/mml:mn>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>, and \n \n 12<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>, respectively, for matching \n \n \n 2<\/mml:mn>\n \n 10<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math> patterns. <\/jats:p>","DOI":"10.62056\/a09qxrxqi","type":"journal-article","created":{"date-parts":[[2024,7,8]],"date-time":"2024-07-08T15:52:04Z","timestamp":1720453924000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":1,"title":["Efficient Post-Quantum Pattern Matching on Encrypted Data"],"prefix":"10.62056","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9758-4617","authenticated-orcid":false,"given":"Anis","family":"Bkakria","sequence":"first","affiliation":[{"name":"IRT SystemX","place":["France"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0216-7958","authenticated-orcid":false,"given":"Malika","family":"Izabach\u00e8ne","sequence":"additional","affiliation":[{"name":"Unaffiliated","place":["France"]}]}],"member":"48349","published-online":{"date-parts":[[2024,7,8]]},"reference":[{"article-title":"A fully homomorphic encryption scheme","year":"2009","author":"Craig Gentry","key":"ref1:gentry2009fully+"},{"key":"ref2:gentry2009fully","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1145\/1536414.1536440","article-title":"Fully homomorphic encryption using ideal lattices","volume-title":"Proceedings of the 41st Annual ACM Symposium on Theory of\n Computing, STOC 2009","author":"Craig Gentry","year":"2009"},{"key":"ref3:boneh2011functional","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1007\/978-3-642-19571-6_16","article-title":"Functional encryption: Definitions and challenges","volume-title":"Theory of Cryptography - 8th Theory of Cryptography\n Conference, TCC 2011, Proceedings","volume":"6597","author":"Dan Boneh","year":"2011"},{"key":"ref4:abdalla2008searchable","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1007\/S00145-007-9006-6","article-title":"Searchable encryption revisited: Consistency properties,\n relation to anonymous IBE, and extensions","volume":"21","author":"Michel Abdalla","year":"2008","journal-title":"Journal of cryptology"},{"key":"ref5:chase2015substring","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1515\/POPETS-2015-0014","article-title":"Substring-Searchable Symmetric Encryption.","volume":"2015","author":"Melissa Chase","year":"2015","journal-title":"Proc. Priv. Enhancing Technol."},{"key":"ref6:kamara2018structured","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1007\/978-3-319-96884-1_12","article-title":"Structured encryption and leakage suppression","volume-title":"Advances in Cryptology - CRYPTO 2018 - 38th Annual\n International Cryptology Conference, Proceedings, Part I","volume":"10991","author":"Seny Kamara","year":"2018"},{"key":"ref7:song2000practical","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1109\/SECPRI.2000.848445","article-title":"Practical techniques for searches on encrypted data","volume-title":"Proceeding 2000 IEEE symposium on security and privacy. S&P\n 2000","author":"Dawn Xiaoding Song","year":"2000"},{"key":"ref8:sherry2015blindbox","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1145\/2785956.2787502","article-title":"Blindbox: Deep packet inspection over encrypted traffic","volume-title":"Proceedings of the 2015 ACM Conference on Special Interest\n Group on Data Communication, SIGCOMM 2015, London, United Kingdom","author":"Justine Sherry","year":"2015"},{"key":"ref9:canard2017blindids","doi-asserted-by":"crossref","first-page":"561","DOI":"10.1145\/3052973.3053013","article-title":"BlindIDS: Market-compliant and privacy-friendly intrusion\n detection system over encrypted traffic","volume-title":"Proceedings of the 2017 ACM on Asia Conference on Computer\n and Communications Security, AsiaCCS 2017","author":"S\u00e9bastien Canard","year":"2017"},{"key":"ref10:DFOS2018","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/978-3-030-03326-2_5","article-title":"Pattern matching on encrypted streams","volume-title":"International Conference on the Theory and Application of\n Cryptology and Information Security, ASIACRYPT 2018, Proceedings, (Part I)","volume":"11272","author":"Nicolas Desmoulins","year":"2018"},{"key":"ref11:bkakria2020privacy","first-page":"191","article-title":"Privacy-Preserving Pattern Matching on Encrypted Data","volume-title":"International Conference on the Theory and Application of\n Cryptology and Information Security, ASIACRYPT 2020, (Part II)","volume":"12492","author":"Anis Bkakria","year":"2020"},{"key":"ref12:bouscatie2021public","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1007\/978-3-030-92068-5_12","article-title":"Public Key Encryption with Flexible Pattern Matching","volume-title":"Advances in Cryptology - ASIACRYPT 2021 - 27th\n International Conference on the Theory and Application of Cryptology and\n Information Security, Proceedings, Part IV","volume":"13093","author":"Elie Bouscati\u00e9","year":"2021"},{"key":"ref13:canard2015divisible","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1007\/978-3-662-46447-2_4","article-title":"Divisible e-cash made practical","volume-title":"Public-Key Cryptography - PKC 2015 - 18th IACR\n International Conference on Practice and Theory in Public-Key Cryptography","volume":"9020","author":"S\u00e9bastien Canard","year":"2015"},{"key":"ref14:bouscatie2023pattern","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"774","DOI":"10.1007\/978-3-031-31368-4_27","article-title":"Pattern Matching in Encrypted Stream from Inner Product\n Encryption","volume-title":"Public-Key Cryptography - PKC 2023 - 26th IACR\n International Conference on Practice and Theory of Public-Key Cryptography,\n Atlanta, GA, USA, May 7-10, 2023, Proceedings, Part I","volume":"13940","author":"Elie Bouscati\u00e9","year":"2023"},{"key":"ref15:pereira2011family","doi-asserted-by":"publisher","first-page":"1319","DOI":"10.1016\/J.JSS.2011.03.083","article-title":"A family of implementation-friendly BN elliptic curves","volume":"84","author":"Geovandro CCF Pereira","year":"2011","journal-title":"Journal of Systems and Software"},{"key":"ref16:C:Brakerski12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"868","DOI":"10.1007\/978-3-642-32009-5_50","article-title":"Fully Homomorphic Encryption without Modulus Switching from\n Classical GapSVP","volume-title":"Advances in Cryptology - CRYPTO 2012 - 32nd Annual\n Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2012.\n Proceedings","volume":"7417","author":"Zvika Brakerski","year":"2012"},{"article-title":"Somewhat Practical Fully Homomorphic Encryption","year":"2012","author":"Junfeng Fan","key":"ref17:EPRINT:FanVer12"},{"key":"ref18:yasuda2014practical","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1007\/978-3-642-54568-9_3","article-title":"Practical Packing Method in Somewhat Homomorphic\n Encryption","volume-title":"Data Privacy Management and Autonomous Spontaneous\n Security","author":"Masaya Yasuda","year":"2014"},{"key":"ref19:yasuda2015new","doi-asserted-by":"crossref","first-page":"2194","DOI":"10.1002\/sec.1164","article-title":"New packing method in somewhat homomorphic encryption and\n its applications","volume":"8","author":"Masaya Yasuda","year":"2015","journal-title":"Security and Communication Networks"},{"article-title":"Snort - Network Intrusion Detection & Prevention System","year":"1998","author":"SNORT","key":"ref20:snort"},{"key":"ref21:EPRINT:AlbPlaSco15","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1515\/jmc-2015-0016","article-title":"On the concrete hardness of Learning with Errors","volume":"9","author":"Martin R. Albrecht","year":"2015","journal-title":"Journal of Mathemtical Cryptology"},{"article-title":"Homomorphic Encryption Security Standard","year":"2018","author":"Martin Albrecht","key":"ref22:HomomorphicEncryptionSecurityStandard"},{"year":"2022","key":"ref23:sealcrypto","article-title":"Microsoft SEAL (release 4.0)"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T21:27:00Z","timestamp":1733866020000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/1\/2\/22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,8]]},"references-count":23,"URL":"https:\/\/doi.org\/10.62056\/a09qxrxqi","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"type":"electronic","value":"3006-5496"}],"subject":[],"published":{"date-parts":[[2024,7,8]]},"assertion":[{"value":"2024-04-09","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-06-03","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc1-2-74"}}