5
$\begingroup$

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.

EDIT:

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

https://cstheory.stackexchange.com/questions/18589/algorithm-for-ranking-members-of-a-regular-language

Improve this question
$\endgroup$
12
  • $\begingroup$ What is the complexity of your brute force approach? $\endgroup$
    – Yuval Filmus
    Commented Mar 31, 2016 at 21:43
  • 1
    $\begingroup$ [the set of properly-formatted strings with the same length as the plaintext] is what's being ranked. ​ They are presumably doing that without "obtaining all possible string representations", ​ since there can very easily be exponentially many such strings. ​ The DFA gives a way to efficiently rank [the set of properly-formatted strings with a given length]. ​ ​ ​ ​ $\endgroup$
    – user12859
    Commented Mar 31, 2016 at 21:46
  • $\begingroup$ Have you tried reading the paper? A talk/presentation is largely an advertisement to get you to read the paper -- but the technical details are in the paper. $\endgroup$
    – D.W. ♦
    Commented Mar 31, 2016 at 21:52
  • $\begingroup$ @RickyDemer That is exactly what I don't understand how the DFA is being used, I tried researching it online but could not find an explanation of how it is done. I don't get it because isn't the DFA (and regular expression) a state machine? You have to traverse it to 'create' a string. So there is no single point along the path that gives a string - its a series of steps. I don't see how you can rank this. $\endgroup$
    – erotavlas
    Commented Mar 31, 2016 at 23:02
  • $\begingroup$ @YuvalFilmus Depends on the string, but I can imagine creating your own methods with a series of conditionals and loops to iterate over all possible combinations of characters. $\endgroup$
    – erotavlas
    Commented Mar 31, 2016 at 23:08

1 Answer 1

Reset to default
5
$\begingroup$

Suppose you want to encode an element of $\binom{[n]}{k}$, that is, a subset of $\{1,\ldots,n\}$ of size $k$. There are $\binom{n}{k}$ such subsets. FPE functions know how to handle encoding and decoding of integers in the range $\{1,\ldots,M\}$, for an $M$ of your choice. To use such an FPE function in your case you will have to translate an element of $\binom{[n]}{k}$ to an integer in $\{1,\ldots,M\}$ for $M = \binom{n}{k}$ (ranking) and back (unranking), efficiently.

How do you efficiently rank and unrank elements of a domain like $\binom{[n]}{k}$? For which domains is it possible? The video describes one scenario where this is possible, and one general algorithm for handling this scenario. If your scenario is different then you might still be able to rank and unrank efficiently, but you will have to use a different approach.

The scenario described by the video (which I haven't watched) is probably that of languages accepted by a DFA with a small number of states. Such a language can be ranked and unranked efficiently, and the algorithms use the DFA which accepts the language. This is how the DFA comes in – it is used by the ranking and unranking algorithms. Hopefully these algorithms are described in the video, but otherwise you can ask another question here.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Actually, if you ask that other question, we will probably refer you to the cstheory link that you already mention. $\endgroup$
    – Yuval Filmus
    Commented Apr 2, 2016 at 9:55
  • $\begingroup$ So are they ranking all the possible strings that match the regular expression? And if so are they using the DFA to rank them in an efficient manner using a special algorithm? If not what are they ranking instead? $\endgroup$
    – erotavlas
    Commented Apr 2, 2016 at 19:01
  • $\begingroup$ Right, they are ranking all possible strings that match the regular expression, using a special algorithm that (I believe) uses the equivalent DFA. $\endgroup$
    – Yuval Filmus
    Commented Apr 2, 2016 at 19:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.