Firewalls have long been in use to protect local networks from threats of the larger Internet. Although firewalls are effective in preventing attacks initiated from outside, they are vulnerable to insider threats, e.g., malicious insiders may access and alter firewall configurations, and disable firewall services. In this paper, we develop an innovative distributed architecture to obliviously manage and evaluate firewalls to prevent both insider and external attacks oriented to the firewalls. Our proposed structure alleviates these issues by obfuscating the firewall rules or policies themselves, then distributing the function of evaluating these rules across multiple servers. Thus, both accessing and altering the rules are considerably more difficult thereby providing better protection to the local network as well as greater security for the firewall itself. We achieve this by integrating multiple areas of research such as secret sharing schemes and multi-party computation, as well as Bloom filters and Byzantine agreement protocols. Our resulting solution is an efficient and secure means by which a firewall may be distributed, and obfuscated while maintaining the ability for multiple servers to obliviously evaluate its functionality.