Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
Is homomorphic encryption even the correct term when we aren't talking about the ring structure? It'll work, I suppose. – Jeff Burdges Dec 21 '11 at 4:56
What are you talking about if you aren't talking about the ring structure? Maybe partially homomorphic encryption? – mikeazo Dec 21 '11 at 13:13
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. – Paŭlo Ebermann Dec 21 '11 at 15:04
There is some progress in blind folded regex matching using Secure Multiparty Computation techniques not sure if that would be useful for you – sashank Jun 26 '15 at 15:55
up vote 3 down vote accepted

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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