5
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ Is homomorphic encryption even the correct term when we aren't talking about the ring structure? It'll work, I suppose. $\endgroup$
    – Jeff Burdges
    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
    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$
    – Paŭlo Ebermann
    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
    Jun 26, 2015 at 15:55

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

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

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