Paper 2023/1022

Zombie: Middleboxes that Don’t Snoop

Collin Zhang, New York University, Cornell University
Zachary DeStefano, New York University
Arasu Arun, New York University
Joseph Bonneau, New York University
Paul Grubbs, University of Michigan–Ann Arbor
Michael Walfish, New York University

Zero-knowledge middleboxes (ZKMBs) are a recent paradigm in which clients get privacy while middleboxes enforce policy: clients prove in zero knowledge that the plaintext underlying their encrypted traffic complies with network policies, such as DNS filtering. However, prior work had impractically poor performance and was limited in functionality. This work presents Zombie, the first system built using the ZKMB paradigm. Zombie introduces techniques that push ZKMBs to the verge of practicality: preprocessing (to move the bulk of proof generation to idle times between requests), asynchrony (to remove proving and verifying costs from the critical path), and batching (to amortize some of the verification work). Zombie’s choices, together with these techniques, reduce client and middlebox overhead by $\approx$ 3.5$\times$ lowering the critical path overhead for a DNS filtering application on commodity hardware to less than 300ms or, in the asynchronous configuration, to 0. As an additional contribution that is likely of independent interest, Zombie introduces a portfolio of techniques to efficiently encode regular expressions in probabilistic (and zero knowledge) proofs; these techniques offer significant asymptotic and constant factor improvements in performance over a standard baseline. Zombie builds on this portfolio to support policies based on regular expressions, such as data loss prevention.

Available format(s)
Publication info
zero knowledgenetwork protocolsprivacyprobabilistic proofsapplicationsmiddleboxesTLSNIZKIP
Contact author(s)
rz1477 @ nyu edu
zd2131 @ nyu edu
2023-11-13: last of 2 revisions
2023-07-01: received
See all versions
Short URL
Creative Commons Attribution


      author = {Collin Zhang and Zachary DeStefano and Arasu Arun and Joseph Bonneau and Paul Grubbs and Michael Walfish},
      title = {Zombie: Middleboxes that Don’t Snoop},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1022},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.