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.
