Paper 2021/1022

Zero-Knowledge Middleboxes

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

Abstract

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 zero-knowledge proofs for TLS 1.3 session keys. We apply the ZKMB paradigm to several case studies, including filtering for encrypted DNS protocols. Experimental results suggest that performance, while not yet practical, is promising. The middlebox’s overhead is only 2–5ms of running time per verified proof. Clients must store hundreds of MBs to participate in the protocol, and added latency ranges from tens of seconds (to set up a connection) to several seconds (for each successive packet requiring proof). Our optimized TLS 1.3 proofs improve the client’s costs 6× over an unoptimized baseline.