{'fraction_non_alphanumeric': 0.026758228747336018, 'fraction_numerical': 0.0071434209487725945, 'mean_word_length': 4.749716360335829, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Semi-Trusted Mixer Based Privacy Preserving Distributed Data Mining for Resource Constrained Devices

In this paper a homomorphic privacy preserving association rule mining algorithm is proposed which can be deployed in resource constrained devices (RCD). Privacy preserved exchange of counts of itemsets among distributed mining sites is a vital part in association rule mining process. Existing cryptography based privacy preserving solutions consume lot of computation due to complex mathematical equations involved. Therefore less computation involved privacy solutions are extremely necessary to deploy mining applications in RCD. In this algorithm, a semi-trusted mixer is used to unify the counts of itemsets encrypted by all mining sites without revealing individual values. The proposed algorithm is built on with a well known communication efficient association rule mining algorithm named count distribution (CD). Security proofs along with performance analysis and comparison show the well acceptability and effectiveness of the proposed algorithm. Efficient and straightforward privacy model and satisfactory performance of the protocol promote itself among one of the initiatives in deploying data mining application in RCD.


INTRODUCTION
Data mining sometimes known as data or knowledge discovery is a process of analyzing data from different point of views and to deduce into useful information which can be applied in various applications including advertisement, bioinformatics, database marketing, fraud detection, ecommerce, health care, security, sports, telecommunication, web, weather forecasting, financial forecasting, etc. Association rule mining is one of the data mining techniques which helps discovering underlying correlation among different data items in a certain database. It can deduce some hidden and unpredictable knowledge which may provide high interestingness to the database owners or miners.
Rapid development of information technology, increasing use of advanced devices and development of algorithms have amplified the necessity of privacy preservation in all kind of transactions. It is more important in case of data mining since sharing of information is a primary requirement for the accomplishment of data mining process. As a matter of fact the more the privacy preservation requirement is increased, the less the accuracy the mining process can achieve. Therefore a tradeoff between privacy and accuracy is determined for a particular application.
In this paper we denote Resource Constrained Device (RCD) as any kind of device having limited capability of transmission, computation, storage, battery or any other features. Examples includes but not limited to mobile phones, Personal Digital Assistants (PDAs), sensor devices, smart cards, Radio Frequency Identification (RFID) devices etc. We also interpret lightweight algorithm as a simple algorithm which requires less computation, low communication overhead and less memory and can be deployed in a RCD. Integration of communication devices of various architectures lead to global heterogeneous network which comprises of trusted, semitrusted, untrustworthy, authorized, unauthorized, suspicious, intruders, hackers types of terminals/devices supported by fewer or no dedicated and authorized infrastructure. Sharing data for data mining purposes among such resource constrained ad-hoc environment is a big challenge itself. Preservation of privacy intensifies the problem by another fold. Therefore privacy preserving data mining in RCD envisions facilitating the mining capability to all these tiny devices which may have a major impact in the market of near future.
Data mining capability of RCD would flourish the future era of ubiquitous computing too. Owner of the device would perform mining operation on the fly. Small sensor devices would be able to optimize or extend their operations based on the dynamic circumstance instead of waiting for time consuming decision from the server. Scattered agents of a security department can take instant decision of actions about a crime or a criminal while in duty. To comprehend the necessity of lightweight privacy preserving data mining, let us consider another circumstance: there are many scattered sensor devices located in a geographical location belonging to different authorities which are serving different purposes with some common records about the environment. Now if it is required to mine data among those sensor devices to accomplish a common interest of the authorities in real time, then preserving privacy would be the first issue that must be ensured. Another motivation behind developing our proposed system could be healthcare awareness. Let us assume some community members or some university students want to know about the extent of attack of some infectious diseases such as swine flu, bird flu, AIDS etc. Each individual is very concerned about the privacy since the matter is very sensitive. They are equipped with a mobile phone or similar smart device and want to know the mining result on the fly. In such circumstances, a distributed lightweight privacy preserving data mining technique would provide a perfect solution. In addition to that; relevant people can be warned or prescribed based on all available health information including previously generated knowledge about a particular infectious diseases.
There is not much research work done for lightweight privacy preserving data mining but there is plenty of research on privacy preserving data mining. Essentially two main approaches are adapted for privacy preserving data mining solutions. First one is the randomization which is basically used for centralized data. In this approach data is perturbed using randomization function and submitted for mining. Randomization function is chosen such that the aggregated property of the data can be recognized in the miner side. In [1,2,3] authors have proposed such approaches. One of the major drawbacks of randomization approach is: if the precision of data mining result is increased, the privacy is not fully preserved [4].
Another one is the cryptographic approach in which the data is encrypted before it is being shared. The miner cannot decrypt individual inputs separately rather it needs to decrypt unified encrypted data together. Therefore the miner cannot associate particular information to a particular party. An example of such approach is Secure Multiparty Computation (SMC) proposed by Yao [5]. Another cryptography based privacy preservation technique is proposed by M. Kantarcioglu and C. Clifton [6] which involves enormous amount of mathematical computation and communication between data sites. This is too heavy to be implemented in a RCD. Among other privacy preserving data mining, [7] and [8] are ones which also involve vast mathematical complex equations to be solved. There are some research works on privacy issues for RCD separately too. Authors in [21] propose a technique to hide location information of a particular device for location based applications. A middleware LocServ is designed which lies in between the location-based application and the location tracking technology. A group signature based privacy for vehicles is proposed in [22], which addresses the issue of preserving privacy in exchanging secret information such as vehicle's speed, location etc. Some research approaches address the issue of hiding sensitive information from data repository. In [23] and [24] authors basically propose some techniques to hide sensitive association rules before the data is disclosed to public. A hardware enhanced association rule mining technique is proposed in [25]. Data is needed to be fed into the hardware before the hash based association rule mining process starts. This approach may not be well realistic for RCD because it requires special purpose hardware as well as it does not handle privacy issue. A homomorphic encryption technique; Paillier encryption is used by X. Yi and Y. Zhang [9] to preserve privacy where authors propose a privacy preserving distributed association rule mining using a semi-trusted mixer. This algorithm involves lot of computation due to the use of complex mathematical equations and big prime numbers as keys in the Paillier encryption.
A heterogeneous mobile device based data collection architecture is proposed by P.P. Jayaraman [10]. Sensor devices are scattered in the environment to collect various data whereas regular mobile phones can work as bearers of the data. Detail architecture of the model is available in [10]. Authors did not consider the privacy issue during the transmission of data. If the mobile devices in the environment are intended to be utilized to work as a data bearer then privacy should be one of the major concerns. Therefore it would be difficult to be implementable in real life unless privacy is preserved. A lightweight privacy preserving algorithm similar like in this paper could provide privacy preservation as well as data mining solution for these kinds of models.
Main focus of CD [18] algorithm is to reduce communication overhead with the cost of redundant parallel computation in each data site. In addition to that this algorithm does not transmit the large itemset in the association rule mining process. Rather it communicates the counts of the itemsets only, which let it reduce communication overhead dramatically. These features make it feasible to be deployed in RCD. On the other hand semi-trusted mixer based privacy solution provided by Yi and Zhang in [9] requires lot of computation with managing big encryption key size. In this paper a more efficient semi-trusted mixer and homomorphic encryption based privacy algorithm is proposed which adopts the rule mining technique of CD to make the solution deployable in RCD.
The remainder of the paper is oriented as follows: Section 2 describes some necessary background information. Section 3 describes proposed solution which consists of privacy preserving algorithm and association rule mining algorithm for RCD. Section 4 contains security analysis and section 5 discusses the proofs and performance comparison. Finally the conclusion is presented in section 6.

II. BACKGROUND
Privacy: According to The American Heritage Dictionary privacy means "The quality or condition of being secluded from the presence or view of others". In data mining if the owner of the data requires the miner to preserve privacy, then the miner gets no authority to use the data unless an acceptable and trustworthy privacy preservation technique is ensured. Different points of views define privacy in different ways. For simplicity we consider a definition which is most relevant to this work. According to J.Vaidya [1] privacy preserving data mining technique must ensure two conditions: 'any information disclosed cannot be traced back to an individual' and 'any information disclosed does not constitute an intrusion'. More technical definition of privacy can be found in [11]. This paper also provides technical definition in security analysis in section 4.
Association Rule Mining: Let us consider; in a distributed data mining environment collective database DB is subdivided into DB 1 , DB 2 , … , DB N in wireless data sites S 1 , S 2 , … ,S N respectively. I= {i 1 , i 2 , … , i m } is the set of items where each transaction T⊆I. Typical form of an association rule is X⇒Y, where X⊆I, Y⊆I and X∩Y=φ. The support s of X⇒Y is the probability of a transaction in DB contains both X and Y. On the other hand confidence c of X⇒Y is the probability of a transaction containing X will contain Y too. Usually it is the interest of the data vendor to find all association rules having support and confidence greater than or equal to minimum threshold value. For another instance of an association rule AB⇒C, More detail on association rule mining process is available in [12,20].
Association rule mining process consists of two major parts. First one is to find frequent large itemsets which have support and confidence values more than a threshold number of times. Second part is to construct association rules from those large itemsets. Due to the simplicity and straightforward nature of the second part, most of the association rule mining papers do not address this. Apriori algorithm is one of the leading algorithms, which determines all frequent large itemsets along with their support counts from a database efficiently. This algorithm was proposed by Agrawal in [14] which is discussed here in brief: Let us say L i be the frequent i-itemsets. Apriori algorithm finds L k from L k-1 in two stages: joining and pruning: Joining: Generates a set of k-itemsets C k , known as candidate itemsets by joining L k-1 and other possible items in the database.
Pruning: Any (k−1)-itemsets cannot be a subset of a frequent k -itemset which is not frequent. Therefore it should be removed.
Stream Cipher: It is a symmetric key cipher where plaintext bits are combined with a pseudorandom cipher bit stream typically by an XOR operation. In stream cipher a seed is used as a key to generate continuous stream of bits. This idea can be used in generating random keys by encrypting a constant with the secret key/seed. Therefore multiple randomly generated keys can be shared among multiple entities simply by sharing a seed. In our proposed algorithm we need some randomly generated keys which can be generated by Output Feedback Mode (OFB) of Data Encryption Standard (DES) detail of which is available in [13].
Homomorphic Encryption: Homomorphic encryption is a special form of encryption using which one can perform a specific algebraic operation on the plaintext by performing the same or different operation on the ciphertext. Detail definition could be found in [13]. If x1 and x2 are two plaintext and E and D denotes encryption and decryption function respectively. Let us consider y1 and y2 are two ciphertexts such that: y1=E k (x1) and y2=E k (x2) where, k is the encryption key. This encryption will be considered homomorphic if the following condition is held: y1+y2=E k (x1+x2).

III. PROPOSED SOLUTION
In this paper we propose a privacy preserving secret computation protocol which is based on a homomorphic encryption technique for distributed data sites. In this section first the privacy preserving frequency mining algorithm is discussed and then the modified CD algorithm is discussed which ensures privacy in the association rule mining process.

A. Privacy Preserving Frequency Mining
In our proposed approach, there would be a number of participating semi honest devices or data sites (>2) which are connected to each other using heterogeneous media. There would be a semi-trusted mixer which would receive encrypted count values from sites through its private channel. It is assumed that the semi-trusted mixer would never collude with any of the data site. In practice it could be assumed that it is authorized by the government or semi-government agent. Data sites communicate to the mixer through the private channel and the mixer communicates to all sites through public channel. Necessary keys would be distributed to the sites by corresponding authorities or owner of the sites. It is also assumed that the private channel is protected by a standard secret key cryptosystem, such as DES [15] or AES [16].  Let us consider; there are N resource constrained sites S 1 , S 2 … S N want to share the summation of a specific secret value of their own without disclosing the value itself. The secret values are c 1 , c 2 … c N respectively. c i j denotes the value belongs to site i for j th iteration (in case of association rule mining it would be j th itemset).
Secret parameters: Let us assume ρ is a large prime number such that, ρ ∑ c ୧ ୨ for all j N ୧ୀଵ . Stream cipher seed is µ. These ρ and µ are shared by all the sites using any key agreement algorithm similar to one proposed in [17]. In fact there will not be any effect if ρ is disclosed to the mixer. There are two more parameters r and n which are generated from a stream cipher in which the seed µ is used as key and any constant (may be ρ) as a plaintext. In each repetition the values of r and n will be different due to the characteristics of the stream cipher. Parameter r is chosen such that ‫ݎ‬ ‫א‬ ܼ ‫כ‬ . If it is assumed that the length of r and n are l bits then total number of bits in each chunk in the stream will be: l+N.l = l(1+N). First l bits would be the value of r, second l bits for n i which is a random number allocated for i th site for communication purpose. In every iteration the value of n i would be different (similar to the value of nonce used in various cryptosystems). Thus for j th site n j will be allocated from bit l+j.l to l+(j+1).l. Following figure (Fig.2) describes the allocation of values of r and n from the stream cipher. The length of l should be chosen such that following constrained is held: 2 െ 1 ൌ ߩ. It is already mentioned that, each data sites communicate to the mixer through a private channel and the mixer communicates to all sites through public channel. Communication stages of the algorithm are depicted in the flow diagram of fig.3.

Then S i sends α i using mixer's private channel
Step 2: (Mixing)

2.1
The mixer receives α i in its private channel (for all i=1 to N).

Broadcasts ߝ ′ back to all participating sites.
Step 3: (Decryption) , the sum of the count is shared among all sites without revealing individual count. An example of the algorithm is provided in the following section for more clarification.

B. Example
For simplicity let us consider three sites S 1 , S 2 and S 3 want to share the sum of their count values {5, 7 and 6} without revealing their own values among themselves. Other shared and generated secret parameters are: ρ=91, r=23, n 1 =17, n 2 =11, n 3 =10 and ‫ݎ‬ ିଵ ൌ 4 (mod 91). To minimize complexity, values of r and n i are not calculated from the stream cipher, rather their values are chosen spontaneously. Also let us assume the values of r -1 are the same instead of different for each site. Communication between sites and the mixer is performed using private channel which is not depicted in this example too. Thus T is equal to the intended sum of {5, 7 and 6}.

C. Association Rule Mining
Among many association rule mining algorithms we choose the one which focuses on reduction of communication cost; Parallel Mining of Association Rules [18]. In this paper authors have proposed three algorithms for the accomplishment three different objectives. Count Distribution (CD) is one of them which aims to reduce the communication cost at the cost of parallel redundant computation in each data site. In this subsection we would integrate our proposed privacy preserving communication technique with CD algorithm which would be suitable for RCD in terms of computation and communication.
Since frequent large itemset computation is considered as the major task in association rule mining algorithms, we focus our effort for the accomplishment of the same task as it is the case in many other papers. Following are the notations, major stages and actions performed in each data site in every cycle: (1) Candidate set generation: Each site S i generates a complete candidate set C k from L k-1 which is computed in the previous iteration using Apriori algorithm (discussed in section 2).
(2) Count computation: S i passes over all the transactions in DB i to compute the count for all items in L k-1 .
(3) Transmission of counts: Counts of C k is sent to the mixer using privacy preserving communication techniques discussed in subsection 3.1. Communication between the data sites and the mixer is performed through the private channel. The value of j in the algorithm (subsection 3.1) maps to the itemsets sequence number.

IV. SECURITY ANALYSIS
In this section we demonstrate that our proposed protocol preserves privacy during the transmission of counts of itemsets in association rule mining process. With the basis of privacy requirement and security definition provided in [9,19], following formulation can be addressed.
Let us assume N≥3, since privacy preservation is impossible for less than three parties. VIEW(S i , N) implies view of the party S i where total number of participants is N. Similarly VIEW(M,N) implies the view of the mixer. Therefore by definition VIEW(M,0), VIEW(S i ,0), VIEW(S i ,1) and VIEW(S i ,2) all equal to Φ. If X and Y are two random variables then, X≈ poly Y = (the probability of distinguishing X and Y) ≤ ଵ ଶ ଵ ொሺሻ for all polynomials Q(l) [9]. N parties want to find the sum of their counts of itemset c 1 , c 2 … c N . The privacy will be preserved if following conditions are satisfied [9]. Proof: (a) When N=1, then j=1 and ‫ܣ‬ ଵ,ଵ ൌ ‫,ܯ‪ܹሺ‬ܧܫܸ‪ሺ‬‬ 1ሻ, ܿ ଵ ሻ=(α,c 1 ).

Theorem 2:
The protocol does not reveal support count of one participant to either the mixer or to other participants.
Proof: In step 1.2 of the algorithm, each site S i encrypts the secret value using private keys which are only known to sites. Before the ciphertext is transmitted to the private channel of the mixer, it is farther encrypted using the public key of the mixer in step 1.3. None has the private key of the mixer except the mixer itself; therefore no eavesdropper can get access to the ciphertext. On the other hand the mixer only can decrypt the outer encryption of the double encrypted ciphertext. It cannot decrypt or read the secret value of S i . Mixer only adds all the ciphertexts together and broadcasts the result to all sites in step 2. Now the sum is known to all parties. They all can decrypt it which is a summation of their secret values. Therefore none can reveal or relate any secret value associated to any site. Brute force attack: Again due to the frequent and random change of value of n j in each communication, brute force attack is unrealistic.

V. PERFORMANCE ANALYSIS
Yi-Zhang's [9] privacy preserving association rule mining algorithm uses semi-trusted mixer which is similar to our proposed model. We compare the performance of the proposed protocol with Yi-Zhang protocol. To measure and compare the performance between these two protocols, let us assume following parameters: H= Average number of items in the large k-itemset. L= Size of each entry in the list of large itemsets to store index and count in Bytes.
N= Number of data sites. K= Average size of each item in Byte (number of characters as for example).
φ=Encryption ratio (   Yi-Zhang algorithm [9]: Let us assume same encryption ratio (that is same φ and β') in both level of encryptions. Communication payload in each iteration is: N*(Cipher-text sent by each site) + Data broadcasted by the mixer = N*φ*H*K+N* φ*H*K=2φNHK.
For farther comparison let us assume value of L=2 (two bytes to store two values: index and count) and K=3 (on an average). Therefore communication payload in our proposed algorithm and Yi-Zhang's algorithm are 3NH and 6NH bytes respectively. Therefore the proposed algorithm generates as much as half communication payload of the Yi-Zhang algorithm. In the proposed protocol the key is considered as the seed µ of the stream cipher. The size of µ can be considered as a typical one: 80 bits.
Yi-Zhang protocol: It is mentioned in [9] that for security concern the value of N should be such that ‫݈݃‬ ଶ ே ൎ 1024 . Therefore size of N is 1024 bits.
All the performance comparisons between Yi-Zhang and the proposed protocol are summarized in table 1.

Measure
Our Proposed Protocol

Yi-Zhang Protocol
Communication overhead (each iteration)

3NH 6NH
Number of exponential operations 0 4 Key size 80 1024 Table 1: Performance comparison between Yi-Zhang and the proposed protocol.
Though there is no use of exponent operations in the proposed algorithm, it involves some other cryptographic operations which would be efficient enough due to small key size. Therefore the performance comparison shows that the proposed algorithm is more efficient and straightforward, which make it suitable for RCD.

VI. CONCLUSION
Rapid development and increasing popularity of ubiquitous computing and RCD in the environment demands the deployment of varieties of lightweight applications. A lightweight algorithm which would lead one step ahead to deploy data mining applications in RCD is proposed in this paper. All security protocols involve detail consideration of various security threats. But our proposed model can avoid many security threats such as replay attack, brute force attack etc, due to the nature of the protocol itself. This is so because in this protocol a single communication is not consists of simply between a sender and a receiver rather it involves multiple senders, receivers and the mixer all together. All the secret parameters and keys in our proposed homomorphic encryption technique are very small in size; therefore less computation is involved in the encryption and decryption process. This feature makes the proposed algorithm more suitable for RCD. Performance analysis and proofs of privacy and security also imply the strength and appropriateness of the algorithm. Therefore this effort should be considered as one of the effective initiative towards the deployment of data mining in ubiquitous computing environment.