Edit Distance Based Encryption and Its Application
Edit distance, also known as Levenshtein distance, is a very useful tool to measure the similarity between two strings. It has been widely used in many applications such as natural language processing and bioinformatics. In this paper, we introduce a new
- PDF / 439,871 Bytes
- 17 Pages / 439.37 x 666.142 pts Page_size
- 77 Downloads / 256 Views
Centre for Computer and Information Security Research, School of Computing and Information Technology, University of Wollongong, Wollongong, Australia [email protected], {gyang,wsusilo}@uow.edu.au 2 Department of Computer Science, Aalto University, Espoo, Finland [email protected]
Abstract. Edit distance, also known as Levenshtein distance, is a very useful tool to measure the similarity between two strings. It has been widely used in many applications such as natural language processing and bioinformatics. In this paper, we introduce a new type of fuzzy public key encryption called Edit Distance-based Encryption (EDE). In EDE, the encryptor can specify an alphabet string and a threshold when encrypting a message, and a decryptor can obtain a decryption key generated from another alphabet string, and the decryption will be successful if and only if the edit distance between the two strings is within the pre-defined threshold. We provide a formal definition and security model for EDE, and propose an EDE scheme that can securely evaluate the edit distance between two strings embedded in the ciphertext and the secret key. We also show an interesting application of our EDE scheme named Fuzzy Broadcast Encryption which is very useful in a broadcasting network. Keywords: Edit distance · Fuzzy encryption · Dynamic programming · Vi`ete’s Formulas
1
Introduction
Measuring the similarity between two strings is an important task in many applications such as natural language processing, bio-informatics, and data mining. One of the common similarity metrics that has been widely used in the above applications is the Edit Distance (a.k.a. Levenshtein distance), which counts the minimum number of operations (namely, insertion, deletion, and substitution) required to transform one string into the other. In this paper, we investigate a challenging problem of building fuzzy public key encryption schemes based on edit distance. Our work is motivated by an open problem raised by Sahai and Waters in [21], where the notion of Fuzzy Identity-Based Encryption (IBE) was proposed. The Fuzzy IBE scheme introduced in [21] can be regarded as the first AttributeBased Encryption (ABE) scheme with a threshold access policy. To be more c Springer International Publishing Switzerland 2016 J.K. Liu and R. Steinfeld (Eds.): ACISP 2016, Part II, LNCS 9723, pp. 103–119, 2016. DOI: 10.1007/978-3-319-40367-0 7
104
T.V.X. Phuong et al.
precise, it allows to use a private key corresponding to an identity string I to decrypt a ciphertext encrypted with another identity string I if and only if the “set overlap” between I and I (i.e., |I ∩I |) is larger than a pre-defined threshold. One of the open problems raised in [21] is to construct fuzzy encryption schemes based on other similarity metrics. We should note that edit distance is very different from the “set overlap” distance used in Fuzzy IBE. For example, consider the biometric identity application of Fuzzy IBE described in [21], given two strings I = “ATCG” and I = “GACT”, we have |
Data Loading...
