Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

7-2016

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ète’s Formulas

Discipline

Information Security | OS and Networks

Research Areas

Information Systems and Management

Publication

Proceedings of the 21st Australasian Conference, Melbourne, Australia, 2016 July 4–6

Volume

9723

First Page

103

Last Page

119

ISBN

9783319403663

Identifier

10.1007/978-3-319-40367-0_7

Publisher

Springer Verlag

City or Country

Melbourne, Australia

Additional URL

http://doi.org/10.1007/978-3-319-40367-0_7

Download

Share

COinS