Efficient Post-Quantum Pattern Matching on Encrypted Data

Anis Bkakria; Malika Izabachène

doi:10.62056/a09qxrxqi

Efficient Post-Quantum Pattern Matching on Encrypted Data

Authors

Anis Bkakria, Malika Izabachène

Anis Bkakria

IRT SystemX, France
anis dot bkakria at irt-systemx dot fr

Malika Izabachène

Unaffiliated, France
malika dot izabachene at gmail dot com

Keywords: Pattern matching over encrypted strings multiple distance computation data fragmentation

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

Google Scholar ePrint

[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.

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[FV12]

Junfeng Fan and Frederik Vercauteren. Somewhat Practical Fully Homomorphic Encryption. https://eprint.iacr.org/2012/144. Cryptology ePrint Archive, Report 2012/144. 2012.

Google Scholar ePrint

[Gen09a]

Craig Gentry. A fully homomorphic encryption scheme. Stanford university, url: 2009.

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[SEA22]

Microsoft SEAL (release 4.0). Microsoft Research, Redmond, WA.. https://github.com/Microsoft/SEAL. March 2022.

Google Scholar ePrint

[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

Google Scholar ePrint

[SNO98]

SNORT. Snort - Network Intrusion Detection & Prevention System. 1998.

Google Scholar ePrint

[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

Google Scholar ePrint

[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.

Google Scholar ePrint

[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.

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/a09qxrxqi

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.

@article{CiC-1-2-22,
    author = "Bkakria, Anis and Izabachène, Malika",
    journal = "{IACR} {C}ommunications in {C}ryptology",
    publisher = "{I}nternational {A}ssociation for {C}ryptologic {R}esearch",
    title = "Efficient Post-Quantum Pattern Matching on Encrypted Data",
    volume = "1",
    number = "2",
    date = "2024-07-08",
    year = "2024",
    issn = "3006-5496",
    doi = "10.62056/a09qxrxqi"
}

TY - JOUR
AU - Bkakria, Anis
AU - Izabachène, Malika
PY  - 2024
TI  - Efficient Post-Quantum Pattern Matching on Encrypted Data
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 1
IS  - 2
DO  - 10.62056/a09qxrxqi
UR  - https://doi.org/10.62056/a09qxrxqi
AB  - <p>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.</p><p>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.</p><p>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. </p>
ER  -

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.