Secure Mining of Association Rules in Horizontally Distributed Databases

1 Introduction

• The goal is to find association rules meeting support and confidence thresholds across the unified database while minimizing disclosure of each site's private data.Generic secure-computation solutions based on Boolean circuits apply only to small inputs and functions realizable by simple circuits.Source: §1 · pp. 1–2
• The proposed private-set union protocol improves on Kantarcioglu and Clifton in privacy, simplicity, and efficiency, and the paper also provides an element-in-subset test.The protocol is not perfectly secure, but its excess information is disclosed only to three coalitions, unlike, which also discloses information to some individual players.Source: §1 · p. 2

1.1 Preliminaries

• The database is represented as a binary transaction-by-item matrix and partitioned horizontally, with each site's local support contributing to global support.An itemset is s-frequent when its global support reaches the threshold sN; local support is measured within each site's partial database.Source: §1.1 · pp. 2–3

1.2 The Fast Distributed Mining algorithm

• FDM generates candidates from frequent (k−1)-itemsets, locally prunes them, unifies surviving local candidates, and computes their global support.Any globally s-frequent itemset must be locally s-frequent at least one site.Source: §1.2 · p. 3

1.3 Overview and organization of the paper

• The proposed secure implementation targets FDM Stage 4, while the paper assumes semi-honest players and more than two participating sites.FDM also exposes information in Stage 6, when players broadcast local support sizes; the paper describes secure implementations of the remaining stages for completeness.Source: §1.3 · p. 4

2.1 The protocol of [12] for the secure computation of all locally frequent itemsets

• UniFI-KC hides each site's locally frequent itemset count by padding its list with fake items, then uses commutative encryption to conceal itemset contents.The players merge encrypted lists, remove duplicates, decrypt the union, and use a lookup table to remove fake items.Source: §2.1 · pp. 4, 6

2.2 A secure multiparty protocol for computing the OR

• The protocol computes a wider range of functions, called threshold functions, and is simpler than UniFI-KC while employing fewer cryptographic primitives.Protocol Threshold-C combines Protocols Threshold and SetInc, with SetInc carrying out the inequality verifications in Steps 6–8.Source: §2.2 · pp. 6, 9
• Threshold-C computes threshold conditions from secret-shared input sums and uses SetInc to test inclusion through keyed-hash signatures checked by an intermediary player.For t=1, the inclusion test implements OR; a signature match indicates inclusion with high probability, while a nonmatch establishes non-inclusion with certainty.Source: §2.2 · pp. 7–8
• Under the semi-honest, M>2-player and preimage-resistant-hash assumptions, Threshold-C is correct and offers perfect or computational privacy in specified coalition cases.Privacy is perfect when P2 is outside the coalition and at least one of P1 and PM is outside it; it is computational when P2 is included but P1 and PM are not. Correctness requires the keyed-hash signatures for included and excluded values to be disjoint, a check the paper says can be performed upfront.Source: §2.2 · p. 9
• Coalitions involving P1, P2, or PM may recover aggregate a, which reveals per-item counts but not which sites hold each itemset.The protocol’s susceptibility is limited to coalitions involving these three players; the aggregate indicates how many sites hold an item, not their identities.Source: §2.2 · p. 10

2.3 An improved protocol for the secure computation of all locally frequent itemsets

• UniFI encodes each player’s locally frequent k-itemsets as binary vectors over the shared Apriori candidate set, then uses Threshold-C to compute their union by OR.The players can order the common candidate set lexicographically before encoding their private subsets.Source: §2.3 · p. 11

2.4 Privacy

• Without collusion, UniFI offers perfect privacy to all players except P2, for whom it offers computational privacy; its collusion leakage leaves partial databases indistinguishable, unlike UniFI-KC.A coalition of two among P1, P2, and PM can learn, for each candidate itemset, how many sites find it frequent, but not which sites; UniFI-KC can reveal relationships among sites.Source: §2.4 · p. 12

2.5 Communication cost

• Protocol UniFI uses 3 communication rounds, improving on UniFI-KC’s 2M rounds; its improvement factor is roughly 93 at M = 4 and about 256 at M = 8.In iteration k, Protocol Threshold-C’s overall communication cost is ((M^2 - 2)(log2 M) + 2|h|)nk bits.Source: §2.5 · p. 13

2.6 Computational cost

• UniFI-KC costs Θ(Mt^3n) bit operations per player, while UniFI costs Θ(Mn log2 M) bit operations per player, plus n hash evaluations for P1 and PM.Here n is the total number of candidate itemsets across iterations.Source: §2.6 · p. 14

Estimating the practical gain in computation time

• In the reported setting, Protocol UniFI's computational overhead was 0.318 seconds for P2 and 1.951 seconds for P1, versus approximately 7,350 seconds per player for UniFI-KC.The estimate used M = 3 and n just over 100,000; the authors describe the improvement as overwhelming.Source: Estimating the practical gain in… · pp. 14–15

• A candidate itemset is globally s-frequent only after its support is securely evaluated, without revealing any site’s local support.The candidates are those locally s-frequent at one or more sites.Source: §3 · p. 15
• For the setting where support sizes are not output, the protocol tests whether Δ(x) mod q < q/2, with q > 2N.Kantarcioglu and Clifton’s alternative setting outputs support sizes, which can be computed using secure summation.Source: §3 · p. 15
• The test uses random additive shares of Δ(x); P1 and PM then verify whether P1’s share belongs to a set known to PM.The shares sum to Δ(x) modulo q, and the membership test expresses the threshold condition.Source: §3 · pp. 15–16
• SetInc is not useful for this verification when its ground set is Z_q, typically large, so Yao’s protocol remains the simplest current option.SetInc is useful in UniFI when the ground set is typically small.Source: §3 · p. 16

• For X, Y ∈ F_s, the rule X ⇒ Y meets confidence c exactly when supp(X ∪ Y)/supp(X) ≥ c.Source: §4 · p. 16
• With q = 2N + 1, players can verify the confidence inequality in parallel for all candidate association rules.Source: §4 · p. 16

• In owner–miner settings, data owners perturb records before release to support trend inference without revealing original records.Source: §5 · p. 16
• In multi-party settings, cryptographic secure computation protects each owner’s records from the others; prior examples include horizontally distributed ID3 and EM clustering.Source: §5 · pp. 16–17
• Association-rule mining had been studied for vertical data in and horizontal data in; work assumes managers assist decryption and no node collusions.Source: §5 · p. 17

• The protocol improves significantly on the current leading protocol in privacy and efficiency.Source: §6 · p. 17
• Its set-inclusion test exploits that the underlying problem is of interest only when there are more than two players.Source: §6 · p. 17
• Further work could develop efficient set-inclusion verification using a semi-honest third party to improve communication and computational costs in stages two and three of.Source: §6 · p. 17
• The study also identifies extending these techniques to generalized association-rule mining as a research problem.Source: §6 · p. 17