Reliability with Accuracy: Verifying Correctness of Resultant of the Outsourced Frequent Item Set Mining In Data-Mining-As-A-Service Paradigm

Nowadays online applications lack reliability for establishing the integrity of user-generated information. Users may unknowingly own compromised devices, or intentionally publish forged information. In these scenarios, applications need some way to determine the correctness of autonomously generated information. Towards that end, this thesis presents a trust-but- verify approach that enables open online applications to independently verify the information generated by each participant. In order to enable independent verification, our framework allowsour application to verify more information from less trustworthy users andless information from more trustworthy users. Thus, an application can trade-off performance for more integrity, or vice versa. We apply the trust-but- verify approach to three different classes of online applications and show how it can enable 1) high-integrity, privacy-preserving, crowd-sourced sensing 2) non-intrusive cheat detection in online games, and 3) effective spam prevention in online messaging applications.