Described is a system for protecting sensitive information that is hardcoded in polynomial-size ordered binary decision diagram (POBDD) form. A software executable represented as a POBDD having sensitive information embedded therein is obfuscated into an obfuscated POBDD. An input query on the obfuscated POBDD is evaluated, and the sensitive information is revealed only if the input query is a correct input. Thus, an adversary is prevented from extracting the sensitive information embedded in the POBDD.