In this paper, our goal is to devise an encryption scheme which enables formal privacy guarantees to be proved, and to validate this model over large-scale, real-life transaction databases. The client/owner encrypts its data using an encrypt/decrypt (E/D) module, which can be essentially treated as a “black box” from its perspective. While the details of this module will be explained in Sec. V, it is responsible for transforming the input data into an encrypted database. The server conducts data mining and sends the (encrypted) patterns to the owner. Our encryption scheme has the property that the returned supports are not true supports. The E/D module recovers the true identity of the returned patterns as well their true supports. It is trivial to show that if the data is encrypted using 1-1 substitution ciphers (without using fake transactions), many ciphers and hence the transactions and patterns can be broken by the server with a high probability by launching the frequency-based attack. Thus, the major focus of this paper is to devise encryption schemes such that formal privacy guarantees can be proven against attacks conducted by The server using background knowledge, while keeping the resource requirements under control. Privacy preserving mining of frequent patterns (from which association rules can be easily computed) on an encrypted outsourced transaction database. We assume a conservative model where the adversary knows the domain of items and their exact frequency and can use this knowledge to identify cipher items and cipher itemsets.