A computer-implemented method comprising: preprocessing, by a secure client or by a trusted third party, a plaintext string; wherein the preprocessing comprises fragmenting the plaintext string into a plurality of overlapping substrings and encrypting the substrings and position information of the substrings into frequency-hiding order-preserving encryption, FHOPE, ciphertexts, wherein the encryption utilizes an order-preserving encryption scheme comprising a FHOPE scheme, wherein the preprocessing results in a secret state remaining or being located at a client, and a search index including a plurality of corresponding ciphertexts to be outsourced, wherein the secret state is lexicographically sorted according to the substrings and includes a map of all unique substrings together with corresponding FHOPE-ranges, a FHOPE-range being a coherent ciphertext range for each substring; and wherein the search index includes the FHOPE ciphertexts, and each FHOPE encrypted substring is equipped with an encrypted position information; outsourcing, from the client or the trusted third party, the search index including the FHOPE ciphertexts to a server for storage; for querying a search query: tokenizing, by the client, the query to be compatible with the search index into substrings; accessing, by the client, the secret state to look up a corresponding FHOPE range for one of the substrings by applying a binary search; receiving from the client and at an engine of the server, the FHOPE range for the substring in the search query; evaluating, on a database, the FHOPE range by referencing, by the engine, the search index stored in the database of the server together with the plurality of ciphertexts, to produce candidate ciphertexts (116a; 116b) meeting the search query, the evaluation resulting in an all encrypted position information that the queried substring occurs in the search query; and communicating, by the engine, to the client at least one candidate ciphertext (116a; 116b), wherein each of the plurality of ciphertexts comprise a fragment of a string encrypted according to the encryption scheme, and a position of the fragment within the string; decrypting, at the client, the all encrypted position information. preprocessing, by a secure client or by a trusted third party, a plaintext string; wherein the preprocessing comprises fragmenting the plaintext string into a plurality of overlapping substrings and encrypting the substrings and position information of the substrings into frequency-hiding order-preserving encryption, FHOPE, ciphertexts, wherein the encryption utilizes an order-preserving encryption scheme comprising a FHOPE scheme, wherein the preprocessing results in a secret state remaining or being located at a client, and a search index including a plurality of corresponding ciphertexts to be outsourced, wherein the secret state is lexicographically sorted according to the substrings and includes a map of all unique substrings together with corresponding FHOPE-ranges, a FHOPE-range being a coherent ciphertext range for each substring; and wherein the search index includes the FHOPE ciphertexts, and each FHOPE encrypted substring is equipped with an encrypted position information; outsourcing, from the client or the trusted third party, the search index including the FHOPE ciphertexts to a server for storage; for querying a search query: tokenizing, by the client, the query to be compatible with the search index into substrings; accessing, by the client, the secret state to look up a corresponding FHOPE range for one of the substrings by applying a binary search; receiving from the client and at an engine of the server, the FHOPE range for the substring in the search query; evaluating, on a database, the FHOPE range by referencing, by the engine, the search index stored in the database of the server together with the plurality of ciphertexts, to produce candidate ciphertexts (116a; 116b) meeting the search query, the evaluation resulting in an all encrypted position information that the queried substring occurs in the search query; and communicating, by the engine, to the client at least one candidate ciphertext (116a; 116b), wherein each of the plurality of ciphertexts comprise a fragment of a string encrypted according to the encryption scheme, and a position of the fragment within the string; tokenizing, by the client, the query to be compatible with the search index into substrings; accessing, by the client, the secret state to look up a corresponding FHOPE range for one of the substrings by applying a binary search; receiving from the client and at an engine of the server, the FHOPE range for the substring in the search query; evaluating, on a database, the FHOPE range by referencing, by the engine, the search index stored in the database of the server together with the plurality of ciphertexts, to produce candidate ciphertexts (116a; 116b) meeting the search query, the evaluation resulting in an all encrypted position information that the queried substring occurs in the search query; and communicating, by the engine, to the client at least one candidate ciphertext (116a; 116b), wherein each of the plurality of ciphertexts comprise a fragment of a string encrypted according to the encryption scheme, and a position of the fragment within the string; decrypting, at the client, the all encrypted position information.