Communications in Cryptology IACR CiC

Efficient Post-Quantum Pattern Matching on Encrypted Data

Authors

Anis Bkakria, Malika Izabachène
Anis Bkakria ORCID
IRT SystemX, France
anis dot bkakria at irt-systemx dot fr
Malika Izabachène ORCID
Unaffiliated, France
malika dot izabachene at gmail dot com

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.

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.

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 $1850$, $10^6$, and $245$, respectively, for matching a single pattern, and by factors of $115$, $10^5$, and $12$, respectively, for matching $2^{10}$ patterns.

References

[ABC+08]
Michel Abdalla, Mihir Bellare, Dario Catalano, Eike Kiltz, Tadayoshi Kohno, Tanja Lange, John Malone-Lee, Gregory Neven, Pascal Paillier, and Haixia Shi. Searchable encryption revisited: Consistency properties, relation to anonymous IBE, and extensions. Journal of cryptology, 21(3):350–391, 2008. DOI: 10.1007/S00145-007-9006-6
[ACC+18]
Martin Albrecht, Melissa Chase, Hao Chen, Jintai Ding, Shafi Goldwasser, Sergey Gorbunov, Shai Halevi, Jeffrey Hoffstein, Kim Laine, Kristin Lauter, Satya Lokam, Daniele Micciancio, Dustin Moody, Travis Morrison, Amit Sahai, and Vinod Vaikuntanathan. Homomorphic Encryption Security Standard. Technical report, HomomorphicEncryption.org. November 2018.
[APS15]
Martin R. Albrecht, Rachel Player, and Sam Scott. On the concrete hardness of Learning with Errors. Journal of Mathemtical Cryptology, 9(3):169–203, 2015. DOI: 10.1515/jmc-2015-0016
[BCC20]
Anis Bkakria, Nora Cuppens, and Frédéric Cuppens. Privacy-Preserving Pattern Matching on Encrypted Data. In International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2020, (Part II), volume 12492, pages 191–220. 2020. Springer. DOI: https://doi.org/10.1007/978-3-030-64834-3_7
[BCS21]
Elie Bouscatié, Guilhem Castagnos, and Olivier Sanders. Public Key Encryption with Flexible Pattern Matching. In Advances in Cryptology - ASIACRYPT 2021 - 27th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings, Part IV, volume 13093 of Lecture Notes in Computer Science, pages 342–370. 2021. Springer. DOI: https://doi.org/10.1007/978-3-030-92068-5_12
[BCS23]
Elie Bouscatié, Guilhem Castagnos, and Olivier Sanders. Pattern Matching in Encrypted Stream from Inner Product Encryption. In Public-Key Cryptography - PKC 2023 - 26th IACR International Conference on Practice and Theory of Public-Key Cryptography, Atlanta, GA, USA, May 7-10, 2023, Proceedings, Part I, volume 13940 of Lecture Notes in Computer Science, pages 774–801. 2023. Springer. DOI: https://doi.org/10.1007/978-3-031-31368-4_27
[Bra12]
Zvika Brakerski. Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP. In Advances in Cryptology - CRYPTO 2012 - 32nd Annual Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2012. Proceedings, volume 7417 of Lecture Notes in Computer Science, pages 868–886. 2012. Springer. DOI: 10.1007/978-3-642-32009-5_50
[BSW11]
Dan Boneh, Amit Sahai, and Brent Waters. Functional encryption: Definitions and challenges. In Theory of Cryptography - 8th Theory of Cryptography Conference, TCC 2011, Proceedings, volume 6597 of Lecture Notes in Computer Science, pages 253–273. 2011. Springer. DOI: https://doi.org/10.1007/978-3-642-19571-6_16
[CDK+17]
Sébastien Canard, Aïda Diop, Nizar Kheir, Marie Paindavoine, and Mohamed Sabt. BlindIDS: Market-compliant and privacy-friendly intrusion detection system over encrypted traffic. In Proceedings of the 2017 ACM on Asia Conference on Computer and Communications Security, AsiaCCS 2017, pages 561–574. 2017. ACM. DOI: https://doi.org/10.1145/3052973.3053013
[CPST15]
Sébastien Canard, David Pointcheval, Olivier Sanders, and Jacques Traoré. Divisible e-cash made practical. In Public-Key Cryptography - PKC 2015 - 18th IACR International Conference on Practice and Theory in Public-Key Cryptography, volume 9020 of Lecture Notes in Computer Science, pages 77–100. 2015. Springer. DOI: https://doi.org/10.1007/978-3-662-46447-2_4
[CS15]
Melissa Chase and Emily Shen. Substring-Searchable Symmetric Encryption.. Proc. Priv. Enhancing Technol., 2015(2):263–281, 2015. DOI: 10.1515/POPETS-2015-0014
[DFOS18]
Nicolas Desmoulins, Pierre-Alain Fouque, Cristina Onete, and Olivier Sanders. Pattern matching on encrypted streams. In International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2018, Proceedings, (Part I), volume 11272 of Lecture Notes in Computer Science, pages 121–148. 2018. Springer. DOI: https://doi.org/10.1007/978-3-030-03326-2_5
[FV12]
Junfeng Fan and Frederik Vercauteren. Somewhat Practical Fully Homomorphic Encryption. https://eprint.iacr.org/2012/144. Cryptology ePrint Archive, Report 2012/144. 2012.
[Gen09a]
Craig Gentry. A fully homomorphic encryption scheme. Stanford university, url: 2009.
[Gen09b]
Craig Gentry. Fully homomorphic encryption using ideal lattices. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, pages 169–178. 2009. ACM. DOI: 10.1145/1536414.1536440
[KMO18]
Seny Kamara, Tarik Moataz, and Olya Ohrimenko. Structured encryption and leakage suppression. In Advances in Cryptology - CRYPTO 2018 - 38th Annual International Cryptology Conference, Proceedings, Part I, volume 10991 of Lecture Notes in Computer Science, pages 339–370. 2018. Springer. DOI: https://doi.org/10.1007/978-3-319-96884-1_12
[PSJNB11]
Geovandro CCF Pereira, Michael Simplício Jr Marcos A and Naehrig, and Paulo SLM Barreto. A family of implementation-friendly BN elliptic curves. Journal of Systems and Software, 84(8):1319–1326, 2011. DOI: 10.1016/J.JSS.2011.03.083
[SEA22]
Microsoft SEAL (release 4.0). Microsoft Research, Redmond, WA.. https://github.com/Microsoft/SEAL. March 2022.
[SLPR15]
Justine Sherry, Chang Lan, Raluca Ada Popa, and Sylvia Ratnasamy. Blindbox: Deep packet inspection over encrypted traffic. In Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication, SIGCOMM 2015, London, United Kingdom, pages 213–226. 2015. ACM. DOI: https://doi.org/10.1145/2785956.2787502
[SWP00]
Dawn Xiaoding Song, David Wagner, and Adrian Perrig. Practical techniques for searches on encrypted data. In Proceeding 2000 IEEE symposium on security and privacy. S&P 2000, pages 44–55, url:. 2000. IEEE. DOI: 10.1109/SECPRI.2000.848445
[YSK+14]
Masaya Yasuda, Takeshi Shimoyama, Jun Kogure, Kazuhiro Yokoyama, and Takeshi Koshiba. Practical Packing Method in Somewhat Homomorphic Encryption. In Joaquin Garcia-Alfaro, Georgios Lioudakis, Nora Cuppens-Boulahia, Simon Foley, and William M. Fitzgerald, editors, Data Privacy Management and Autonomous Spontaneous Security, pages 34–50, Berlin, Heidelberg. 2014. Springer Berlin Heidelberg.
[YSK+15]
Masaya Yasuda, Takeshi Shimoyama, Jun Kogure, Kazuhiro Yokoyama, and Takeshi Koshiba. New packing method in somewhat homomorphic encryption and its applications. Security and Communication Networks, 8(13):2194–2213, 2015.

PDFPDF Open access

History
Submitted: 2024-04-09
Accepted: 2024-06-03
Published: 2024-07-08
How to cite

Anis Bkakria and Malika Izabachène, "Efficient Post-Quantum Pattern Matching on Encrypted Data," IACR Communications in Cryptology, vol. 1, no. 2, Jul 08, 2024, doi: 10.62056/a09qxrxqi.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.