Sorting Encrypted Strings with a Leaked-Order Index

TL;DR: This is not a cryptographic construction. It is a pragmatic engineering compromise for applications where encrypted storage is required but approximate alphabetical ordering is still useful. I sort encrypted strings using an external index: the sum of weighted Unicode code points for the first N characters with exponential positional weights, followed by quantization. Monotonicity is preserved, but accuracy predictably degrades after the first few characters. Not a cryptographic scheme; some ordering information leaks by design. The problem Some time ago, while implementing a project, I ran into the problem of sorting encrypted data in a database. I’d like to share the solution. I won’t go into detail describing the entire application. I’ll just say that, according to the required architecture, almost all data in the database must be stored exclusively in encrypted form: usernames, file names, tags, comments, dates, and so on (with the exception of identifiers and some system fields). That is, the table structure should be open, but the contents should not be. The encryption is symmetric: the same key is used for both encryption and decryption. This means that without the encryption key, even with a full database dump an attacker should not obtain any original data. And this is where two problems immediately arose: searching by the data without fully decrypting it, and sorting encrypted data. The first problem, with some caveats, is solved fairly simply. To search encrypted data, it is enough to additionally store hashes of the original values you plan to search on. This allows exact-match lookups (for example, users by login or files by tag) without storing the original values in plaintext. Yes, this won’t allow pattern searches, but it’s quite acceptable for the project’s goals. But sorting encrypted data turned out to be significantly more difficult. The solution A quick search showed that the problem is far from new, but there are no standard approaches t