Skip to main content
placeholder image

Edit distance based encryption and its application

Journal Article


Download full-text (Open Access)

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.

Publication Date


  • 2016

Citation


  • Phuong, T. Viet Xuan., Yang, G., Susilo, W. & Liang, K. (2016). Edit distance based encryption and its application. Lecture Notes in Computer Science, 9723 103-119. Melbourne, Australia Proceedings of The 21st Australasian Conference on Information Security and Privacy (ACISP)

Scopus Eid


  • 2-s2.0-84978786085

Ro Full-text Url


  • http://ro.uow.edu.au/cgi/viewcontent.cgi?article=6841&context=eispapers

Ro Metadata Url


  • http://ro.uow.edu.au/eispapers/5812

Has Global Citation Frequency


Number Of Pages


  • 16

Start Page


  • 103

End Page


  • 119

Volume


  • 9723

Place Of Publication


  • Germany

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.

Publication Date


  • 2016

Citation


  • Phuong, T. Viet Xuan., Yang, G., Susilo, W. & Liang, K. (2016). Edit distance based encryption and its application. Lecture Notes in Computer Science, 9723 103-119. Melbourne, Australia Proceedings of The 21st Australasian Conference on Information Security and Privacy (ACISP)

Scopus Eid


  • 2-s2.0-84978786085

Ro Full-text Url


  • http://ro.uow.edu.au/cgi/viewcontent.cgi?article=6841&context=eispapers

Ro Metadata Url


  • http://ro.uow.edu.au/eispapers/5812

Has Global Citation Frequency


Number Of Pages


  • 16

Start Page


  • 103

End Page


  • 119

Volume


  • 9723

Place Of Publication


  • Germany