Authenticity Verification for Dynamic Social Data Outsourcing

As with the maturation and diversification of social services, social data outsourcing has become pervasive. In this context, online social networks outsource their real-time social data to a social data provider, who responses to query requests issued from data consumers. However, dishonest or malicious social data providers might tamper with collected social data by adding fake data and deleting/modifying raw data, and further return inauthentic query results to data consumers. In this article, we make the first attempt to study the problem of authenticity verification for dynamic social data. To this end, we first propose a novel authenticity verification framework, and then, propose a self-balancing hash tree scheme to tackle challenges brought on by the vast scale and dynamics of social data. To maximize the search efficiency for the self-balancing hash tree, we introduce a balance factor to define an unbalanced node as its balance factor is not chosen from a predetermined set. Furthermore, we propose three algorithms to balance unbalanced nodes in the self-balancing hash tree. Rigorous theoretical analyses prove that our framework can determinately detect any fake query results returned by data consumers. Experimental results built on a real Twitter dataset show that our scheme is efficient and effective.