Public Key Encryption with Fuzzy Matching

Publication Name

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


The rise of cloud computing is driving the development in various fields and becoming one of the hot topics in recent years. To solve the problem of comparing ciphertexts between different users in cloud storage, Public Key Encryption with Equality Test (PKEET) was proposed. In PKEET, a tester can determine whether two ciphertexts encrypted with different public keys contain the same message without decrypting the ciphertexts. However, PKEET only supports exact matching, which may not be practical when two messages have misspellings, formatting differences, or differences in the data itself. Therefore, to support fuzzy matching, in this paper we propose the concept of Public Key Encryption with Fuzzy Matching (PKEFM), which allows to determine whether the edit distance between two encrypted messages is less than a threshold value. PKEFM can be well applied to support fuzzy data comparison in encrypted e-mail systems or encrypted gene testing. We then modify the scheme to provide the decryption function, and support (encrypted) wildcards in the matching, in order to further improve the generality of PKEFM at the cost of a small amount of extra computation.

Open Access Status

This publication is not available as open access


13059 LNCS

First Page


Last Page


Funding Number


Funding Sponsor

National Natural Science Foundation of China



Link to publisher version (DOI)