Longest Common Sub-sequence Computation and Retrieve for Encrypted Character Strings

Longest Common Sub-sequence is a basic algorithm problem. It serves as a basic component for a variety of applications in information processing and bioinformatics. It is a NP-hard problem and often manipulated using dynamic programming, which is relatively fast but involves large memory space. Fortunately, cloud computing and outsourced computing provides a practical method for overload alleviation. However, for the security and privacy concern, clients hope to encrypt their data before upload them to the cloud, meanwhile maintain the ability for the cloud to process on the data. In this paper, we propose a method to computing Longest Common Sub-sequence using somewhat homomorphic encryption. Beyond that, we show how to use our achievement into searchable encryption to achieve rich expressiveness.