University of Surrey

Test tubes in the lab Research in the ATI Dance Research

Edit Distance Based Encryption and Its Application

Phuong, Tran Viet Xuan, Yang, Guomin, Susilo, Willy and Liang, Kaitai (2016) Edit Distance Based Encryption and Its Application ACISP: Australasian Conference on Information Security and Privacy, 2. pp. 103-119.

Full text not available from this repository.


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.

Item Type: Article
Divisions : Faculty of Engineering and Physical Sciences > Computing Science
Authors :
Phuong, Tran Viet Xuan
Yang, Guomin
Susilo, Willy
Date : 30 June 2016
DOI : 10.1007/978-3-319-40367-0 7
Copyright Disclaimer : © Springer International Publishing Switzerland 2016
Uncontrolled Keywords : Edit distance; Fuzzy encryption; Dynamic programming; Vi`ete’s Formulas
Depositing User : Jane Hindle
Date Deposited : 31 Oct 2017 10:01
Last Modified : 16 Jan 2019 19:03

Actions (login required)

View Item View Item


Downloads per month over past year

Information about this web site

© The University of Surrey, Guildford, Surrey, GU2 7XH, United Kingdom.
+44 (0)1483 300800