This question is about the use of 'ranking' of regular languages in applications such as format preserving encryption.
I understand format preserving encryption but I don't understand how regular expressions can be used to get an integer that is the input of an encryption algorithm.
Referring to this video https://youtu.be/MT5ketZ-jLw?t=24m44s at time stamp 24:44
According to the process described - In order to encrypt a string to a ciphertext of some agreed upon format, you need to rank all the possible strings it can be - then using your FPE function encrypt the integer that represents the input plain text to an integer in the same set - unrank the output integer to a ciphertext.
I don't understand what is being ranked? Are they actually obtaining all possible string representations of the regular expression and ranking those? Or are they ranking something else? Where does the DFA come to play - because I can see a brute force way you can do this without bothering with the DFA - or even regular expressions to define the format.
I have already most of the paper that use ranking in regular languages for encryption such as these ones
- Mihir Bellare, Thomas Ristenpart, Phillip Rogaway, and Till Stegers Selected Areas in Cryptography, pages 295-312. Springer-Verlag, 2009 (online, see sec 5 p 10 "FPE for arbitrary RLs")
- Daniel Luchaup, Kevin P. Dyer, Somesh Jha, Thomas Ristenpart and Thomas Shrimpton To appear in the proceedings of USENIX Security 2014
Anyway I'm just looking for a 'laymans' explanation of how this works as I cannot find any working examples online. This would be useful to understand the overall procedure. All examples I have found regarding regular expressions involve creating the DFA, and most of them end there. What happens next?
The closest I could find was this post which I think is asking the same thing