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.

  • $\begingroup$ Is homomorphic encryption even the correct term when we aren't talking about the ring structure? It'll work, I suppose. $\endgroup$ Commented Dec 21, 2011 at 4:56
  • $\begingroup$ What are you talking about if you aren't talking about the ring structure? Maybe partially homomorphic encryption? $\endgroup$
    – mikeazo
    Commented Dec 21, 2011 at 13:13
  • $\begingroup$ I suppose you can do something like "encrypt each character separately", if you want the encryption to be a homomorphism in relation to "string operations". I'm not sure how secure such a scheme can be. $\endgroup$ Commented Dec 21, 2011 at 15:04
  • $\begingroup$ There is some progress in blind folded regex matching using Secure Multiparty Computation techniques not sure if that would be useful for you $\endgroup$
    – sashank
    Commented Jun 26, 2015 at 15:55

1 Answer 1


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.


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.