  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.
