We introduce ZIDS, a client-server solution for private detection of intrusions that is suitable for private detection of zero-day attacks in input data. The system includes an intrusion detection system (IDS) server that has a set of sensitive signatures for zero-day attacks and IDS clients that possess some sensitive data (e.g. files, logs). Using ZIDS, each IDS client learns whether its input data matche any of the zero-day signatures, but neither party learns about any additional information. In other words, the IDS client learns nothing about the zero-day signatures and the IDS server learns nothing about the input data and the analysis results. To solve this problem, we reduce privacy-preserving intrusion detection to an instance of secure two-party oblivious deterministic finite automata (ODFA) evaluation. Then, motivated by the fact that the DFAs associated with attack signature are often sparse, we propose a new and efficient ODFA protocol that takes advantage of this sparsity. Our new construction is considerably more efficient than the existing solutions and, at the same time, does not leak any sensitive information about the nature of the sparsity in the private DFA. We provide a full implementation of our privacy-preserving system that includes optimizations that lead to better memory usage and evaluate its performance on rule sets from the Snort IDS.