Paper 2020/020

Practical Encrypted Network Traffic Pattern Matching for Secure Middleboxes

Shangqi Lai, Xingliang Yuan, Shi-Feng Sun, Joseph K. Liu, Ron Steinfeld, Amin Sakzad, and Dongxi Liu


Network Function Virtualisation (NFV) advances the adoption of composable software middleboxes. Accordingly, cloud data centres become major NFV vendors for enterprise traffic processing. Due to the privacy concern of traffic redirection to the cloud, secure middlebox systems (e.g., BlindBox) draw much attention; they can process encrypted packets against encrypted rules directly. However, most of the existing systems supporting pattern matching based network functions require the enterprise gateway to tokenise packet payloads via sliding windows. Such tokenisation induces a considerable communication overhead, which can be over 100$\times$ to the packet size. To overcome this bottleneck, in this paper, we propose the first bandwidth-efficient encrypted pattern matching protocol for secure middleboxes. We resort to a primitive called symmetric hidden vector encryption (SHVE), and propose a variant of it, aka SHVE+, to achieve constant and moderate communication cost. To speed up, we devise encrypted filters to reduce the number of accesses to SHVE+ during matching highly. We formalise the security of our proposed protocol and conduct comprehensive evaluations over real-world rulesets and traffic dumps. The results show that our design can inspect a packet over 20k rules within 100 $\mu$s. Compared to prior work, it brings a saving of 94$\%$ in bandwidth consumption.

Available format(s)
Publication info
Published elsewhere. IEEE Transactions on Dependable and Secure Computing
Privacy-PreservingMiddleboxPattern Matching
Contact author(s)
shangqi lai @ monash edu
2021-04-17: last of 2 revisions
2020-01-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Shangqi Lai and Xingliang Yuan and Shi-Feng Sun and Joseph K.  Liu and Ron Steinfeld and Amin Sakzad and Dongxi Liu},
      title = {Practical Encrypted Network Traffic Pattern Matching for Secure Middleboxes},
      howpublished = {Cryptology ePrint Archive, Paper 2020/020},
      year = {2020},
      doi = {10.1109/TDSC.2021.3065652},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.