Techniques for an efficient and secure store for credentials enforcement using a firewall are disclosed. In some embodiments, a system, process, and/or computer program product for an efficient and secure store for credentials enforcement using a firewall includes receiving a space-efficient and secure data structure, such as bloom filter, from an agent executed on an authentication server, in which the bloom filter is generated by the agent based on a transformation of a plurality of user credentials extracted from the authentication server and/or intercepted at the authentication server; storing the bloom filter on the network device (e.g., in a cache on the network device); and monitoring network traffic at the network device to perform credentials enforcement using the bloom filter.