Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
Is there any reasonable homomorphic encryption protocol that supports some meaningful fragment of regular languages/expressions and/or edit distance bounds?
I'm suspicious that homomorphic encryption never handles this sort of "insert bounded amount of arbitrary garbage", but maybe a subset of regular expressions with various bounds, or perhaps up to some bonded edit distance.
This question came up in a discussion about CryptDB.
In general, it seems that right now, searching on encrypted data is still quite limited. Besides CryptDB, SADS is another that I have seen. Without knowing more about your security requirements, however, it will be hard to say exactly (e.g., is the regex kept private or is only the data that it is being matched against kept private? Is there a trusted third party? and so on).
Personally, I have never seen a system which allows full regex searching of a dataset where either query or data is kept private. The best I have seen is keyword matching with AND and OR boolean logic (see SADS). Phase II of the DARPA PROCEED program looks to some sort of regex searching capability. Depending on how successful that phase is, we might have something a year from now.
As a side note, from the little I actually understand about fully homomorphic encryption (FHE), it would seem that a fully homomorphic system could perform this type of search. FHE systems are currently not that mature, however, as researchers are still trying to figure out how to make them practical.
