Oblivious Suffix Sorting: A Multi-Party Computation Scheme for Secure and Efficient Suffix Sorting

Private string search is a technique that enables the search for specific patterns or substrings within a larger text while preserving the privacy of both the search query and the text. This is particularly important in scenarios where sensitive information needs to be processed without revealing the content to computation parties, such as in federated learning applications within bioinformatics. A key component of string search is suffix sorting, which provides essential index data structures such as suffix arrays (SA) and FM-indexes. Despite the existence of efficient suffix sorting methods in the classical model, there have been no efficient methods in secure computation models. In this paper, we propose efficient and secure schemes based on multiparty computation (MPC) that construct suffix arrays and FM-indexes. To our knowledge, this is the first scheme that surpasses naive methods, reducing the communication complexity from O(n²) to O(nlog²n) and the number of online communication rounds from O(n) to O(log²n), where n is the string length. We also give secure schemes for private string search and computing string similarity measures.