1. A method of performing order-preserving encryption of an input plaintext and generating an output ciphertext where the output ciphertext preserves the sort order of the input plaintext, the method comprising: providing a mapping table to store plaintext-to-ciphertext mapping data; receiving the input plaintext; performing, using a processor, order-preserving tokenization of the input plaintext using a random order-preserving function; accessing the mapping table to retrieve plaintext-to-ciphertext mapping data relating to the input plaintext; in response to the input plaintext not being present in the mapping table, performing, using the processor, a search of the random order-preserving function for the input plaintext using the retrieved plaintext-to-ciphertext mapping data and a tail bounded probability distribution sampler to recursively sample the random order-preserving function, the tail bounded probability distribution sampler bounding the possible values for the recursive sampling operations to search the random order-preserving function for the input plaintext at a location with a high probability of locating a ciphertext corresponding to the input plaintext, wherein performing the search comprises performing the search of the random order-preserving function for the input plaintext using the retrieved plaintext-to-ciphertext mapping data and the tail bounded probability distribution sampler to start sampling the random order-preserving function at a point in a ciphertext space of the random order-preserving function indicated by the retrieved plaintext-to-ciphertext mapping data to have a high probability of locating the desired ciphertext; obtaining the ciphertext for the input plaintext as a result of the searching; storing the plaintext-to-ciphertext mapping for the input plaintext in the mapping table; and providing the ciphertext as the output ciphertext.