Paper 2021/1022

Zero-Knowledge Middleboxes

Paul Grubbs, Arasu Arun, Ye Zhang, Joseph Bonneau, and Michael Walfish


This paper initiates research on zero-knowledge middleboxes (ZKMBs). A ZKMB is a network middlebox that enforces network usage policies on encrypted traffic. Clients send the middlebox zero-knowledge proofs that their traffic is policy-compliant; these proofs reveal nothing about the client’s communication except that it complies with the policy. We show how to make ZKMBs work with unmodified encrypted-communication protocols (specifically TLS 1.3), making ZKMBs invisible to servers. As a contribution of independent interest, we design optimized zero-knowledge proofs for TLS 1.3 session keys. We apply the ZKMB paradigm to several case studies. Experimental results suggest that in certain settings, performance is in striking distance of practicality; an example is a middlebox that filters domain queries (each query requiring a separate proof) when the client has a long-lived TLS connection with a DNS resolver. In such configurations, the middlebox’s overhead is 2–5 ms of running time per proof, and client latency to create a proof is several seconds. On the other hand, clients may have to store hundreds of MBs depending on the underlying zero-knowledge proof machinery, and for some applications, latency is tens of seconds.

Note: Added artifact evaluation badges and artifact appendix

Available format(s)
Publication info
Published elsewhere. MAJOR revision.Usenix Security 2022
zero knowledgenetwork protocolsprivacyprobabilistic proofsapplicationsmiddleboxesTLS
Contact author(s)
paulgrubbs12 @ gmail com
2022-05-06: last of 4 revisions
2021-08-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {Paul Grubbs and Arasu Arun and Ye Zhang and Joseph Bonneau and Michael Walfish},
      title = {Zero-Knowledge Middleboxes},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1022},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.