Efficient authentication of approximate record matching for outsourced databases

Boxiang Dong, Hui Wendy Wang

Research output: Contribution to journalArticleResearchpeer-review

Abstract

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 S2, E-V S2, G-V S2 and P-V S2. 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.

Original languageEnglish
Pages (from-to)119-168
Number of pages50
JournalAdvances in Intelligent Systems and Computing
Volume838
DOIs
StatePublished - 1 Jan 2019

Fingerprint

Outsourcing
Authentication
Servers
Cloud computing
Information management
Costs
Experiments

Keywords

  • Approximate record matching
  • Authentication
  • Game theory
  • Outsourcing
  • Verification object

Cite this

@article{07f9c619cf084076b080f0caceca62fe,
title = "Efficient authentication of approximate record matching for outsourced databases",
abstract = "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 S2, E-V S2, G-V S2 and P-V S2. 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.",
keywords = "Approximate record matching, Authentication, Game theory, Outsourcing, Verification object",
author = "Boxiang Dong and Wang, {Hui Wendy}",
year = "2019",
month = "1",
day = "1",
doi = "10.1007/978-3-319-98056-0_6",
language = "English",
volume = "838",
pages = "119--168",
journal = "Advances in Intelligent Systems and Computing",
issn = "2194-5357",
publisher = "Springer Verlag",

}

Efficient authentication of approximate record matching for outsourced databases. / Dong, Boxiang; Wang, Hui Wendy.

In: Advances in Intelligent Systems and Computing, Vol. 838, 01.01.2019, p. 119-168.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Efficient authentication of approximate record matching for outsourced databases

AU - Dong, Boxiang

AU - Wang, Hui Wendy

PY - 2019/1/1

Y1 - 2019/1/1

N2 - 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 S2, E-V S2, G-V S2 and P-V S2. 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.

AB - 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 S2, E-V S2, G-V S2 and P-V S2. 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.

KW - Approximate record matching

KW - Authentication

KW - Game theory

KW - Outsourcing

KW - Verification object

UR - http://www.scopus.com/inward/record.url?scp=85065745696&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-98056-0_6

DO - 10.1007/978-3-319-98056-0_6

M3 - Article

VL - 838

SP - 119

EP - 168

JO - Advances in Intelligent Systems and Computing

JF - Advances in Intelligent Systems and Computing

SN - 2194-5357

ER -