Efficient authentication of approximate record matching for outsourced databases

Cloud computing enables the outsourcing of big data analytics, where a third-party server is responsible for data management and processing. A major security concern of the outsourcing paradigm is whether the untrusted server returns correct results. In this paper, we consider approximate record matching in the outsourcing model. Given a target record, the service provider should return all records from the outsourced dataset that are similar to the target. Identifying approximately duplicate records in databases plays an important role in information integration and entity resolution. In this paper, we design ALARM, an Authentication soLution of outsourced Approximate Record Matching to verify the correctness of the result. The key idea of ALARM is that besides returning the similar records, the server constructs the verification object (VO) to prove their authenticity, soundness and completeness. ALARM consists of four authentication approaches, namely V S², E-V S², G-V S² and P-V S². These approaches endeavor to reduce the verification cost from different aspects. We theoretically prove the robustness and security of these approaches, and analyze the time and space complexity for each approach. We perform an extensive set of experiment on real-world datasets to demonstrate that ALARM can verify the record matching results with cheap cost.