Edit distance based encryption and its application

Tran Viet Xuan Phuong; Guomin Yang; Willy Susilo; Kaitai Liang

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

Edit distance based encryption and its application

Tran Viet Xuan Phuong^*, Guomin Yang, Willy Susilo, Kaitai Liang

^*Corresponding author for this work

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

2 Citations (Scopus)

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.

Original language	English
Title of host publication	Information Security and Privacy - 21st Australasian Conference, ACISP 2016, Proceedings
Editors	Joseph K. Liu, Ron Steinfeld
Publisher	Springer
Pages	103-119
Number of pages	17
ISBN (Print)	9783319403663
DOIs	https://doi.org/10.1007/978-3-319-40367-0_7
Publication status	Published - 1 Jan 2016
Externally published	Yes
Event	21st Australasian Conference on Information Security and Privacy, ACISP 2016 - Melbourne, Australia Duration: 4 Jul 2016 → 6 Jul 2016

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9723
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	21st Australasian Conference on Information Security and Privacy, ACISP 2016
Country/Territory	Australia
City	Melbourne
Period	4/07/16 → 6/07/16

Keywords

Dynamic programming
Edit distance
Fuzzy encryption
Viète’s formulas

Access to Document

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

Cite this

Phuong, T. V. X., Yang, G., Susilo, W., & Liang, K. (2016). Edit distance based encryption and its application. In J. K. Liu, & R. Steinfeld (Eds.), Information Security and Privacy - 21st Australasian Conference, ACISP 2016, Proceedings (pp. 103-119). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9723). Springer. https://doi.org/10.1007/978-3-319-40367-0_7

Phuong, Tran Viet Xuan ; Yang, Guomin ; Susilo, Willy et al. / Edit distance based encryption and its application. Information Security and Privacy - 21st Australasian Conference, ACISP 2016, Proceedings. editor / Joseph K. Liu ; Ron Steinfeld. Springer, 2016. pp. 103-119 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{77785ae13e8144c9a0caeb91341fb6ca,

title = "Edit distance based encryption and its application",

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 = "Dynamic programming, Edit distance, Fuzzy encryption, Vi{\`e}te{\textquoteright}s formulas",

author = "Phuong, {Tran Viet Xuan} and Guomin Yang and Willy Susilo and Kaitai Liang",

year = "2016",

month = jan,

day = "1",

doi = "10.1007/978-3-319-40367-0_7",

language = "English",

isbn = "9783319403663",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "103--119",

editor = "Liu, {Joseph K.} and Ron Steinfeld",

booktitle = "Information Security and Privacy - 21st Australasian Conference, ACISP 2016, Proceedings",

note = "21st Australasian Conference on Information Security and Privacy, ACISP 2016 ; Conference date: 04-07-2016 Through 06-07-2016",

}

Phuong, TVX, Yang, G, Susilo, W & Liang, K 2016, Edit distance based encryption and its application. in JK Liu & R Steinfeld (eds), Information Security and Privacy - 21st Australasian Conference, ACISP 2016, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9723, Springer, pp. 103-119, 21st Australasian Conference on Information Security and Privacy, ACISP 2016, Melbourne, Australia, 4/07/16. https://doi.org/10.1007/978-3-319-40367-0_7

Edit distance based encryption and its application. / Phuong, Tran Viet Xuan; Yang, Guomin; Susilo, Willy et al.
Information Security and Privacy - 21st Australasian Conference, ACISP 2016, Proceedings. ed. / Joseph K. Liu; Ron Steinfeld. Springer, 2016. p. 103-119 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9723).

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

TY - GEN

T1 - Edit distance based encryption and its application

AU - Phuong, Tran Viet Xuan

AU - Yang, Guomin

AU - Susilo, Willy

AU - Liang, Kaitai

PY - 2016/1/1

Y1 - 2016/1/1

N2 - 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.

AB - 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.

KW - Dynamic programming

KW - Edit distance

KW - Fuzzy encryption

KW - Viète’s formulas

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

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

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

M3 - Conference contribution

AN - SCOPUS:84978786085

SN - 9783319403663

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 103

EP - 119

BT - Information Security and Privacy - 21st Australasian Conference, ACISP 2016, Proceedings

A2 - Liu, Joseph K.

A2 - Steinfeld, Ron

PB - Springer

T2 - 21st Australasian Conference on Information Security and Privacy, ACISP 2016

Y2 - 4 July 2016 through 6 July 2016

ER -

Phuong TVX, Yang G, Susilo W, Liang K. Edit distance based encryption and its application. In Liu JK, Steinfeld R, editors, Information Security and Privacy - 21st Australasian Conference, ACISP 2016, Proceedings. Springer. 2016. p. 103-119. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-40367-0_7

Edit distance based encryption and its application

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this