Private Temporal Membership Test Queries With Probabilistic Data Structures

With the development of the era of big data,many corporations use information retrieval technology to meet the daily needs of users.On the one hand,data information and advanced technologies provide users with more comprehensive service.On the other hand,a lot of personal sensitive data has thereby been leaked.Service providers may typically infer users' private information including preferences,interests and habits,etc.Privacy protection in today's world is as important as the development of information technology.In this thesis,we investigate the private temporal membership test problem based on probabilistic data structures.Private temporal membership test is one of the privacypreserving techniques that can be used to answer users' temporal membership test queries without leaking users' private information.We first introduce some fundamental probabilistic data structures and important cryptographic primitives,then show how to use these structures to construct the Variant Persistent Bloom Filter(VPB).VPB is suitable for storing temporal data with compact space and thus performs more efficiently to achieve temporal membership test queries and insertion.To achieve private temporal membership test queries with VPB,we design two encryption schemes by utilizing ideas in secure multi-party computation.More precisely,we employ Paillier homomorphic encryption and 1-out-of-n oblivious transfer,respectively.Furthermore,we compare our purposed schemes with the existing methods by simulation results based on VPB,and analyze their efficiency and security.