9

It appears that only Partial Homomorphic Encryption(P.H.E.) is practical for modern day (2011) use. However I'm having difficulty locating libraries (FOSS or otherwise) that enable me to leverage this technology.

El Gamal is an example of an algorithm that does PHE, but the wiki page doesn't clearly explain what blind math operations are supported and how to implement them.

Potential Use Cases

A PHE is something that can be used abstract to offload mathematic operations to a 3rd without that party ever knowing what the underlying value is. e.g. x+y=z can be performed and it will have a valid encrypted result, but all 3 values are never known in unencrypted format to the third party. This is beneficial to protecting stock market analysis data, PII, or anything considered proprietary or confidential.

Question

So, what encryption algorithms exist and what libraries exist that allow me to operate on the encrypted data? Samples of operations I'm interested in include

  • Addition and Subtraction
  • Multiplication or Division
  • Comparisons (is encrypted X greater than encrypted Y)
  • A technique that will allow me to compare the binary/encrypted ASCII version of the word "Ap" and do a Contains() or StartsWith() with the encrypted version of "Apple"
Community
  • 1
makerofthings7
  • 50,090
  • 54
  • 250
  • 536

4 Answers4

10

El Gamal encryption allows for multiplication. This occurs within the group on which El Gamal runs; hence you are multiplying numbers modulo a given prime, not "plain" integers. If you can multiply you can divide (inversion in a group of size q is done by raising to the power q-2, so this is a matter of performing some multiplications). El Gamal is implemented in libgcrypt (used in GnuPG) but you would have to do the multiplications yourself (El Gamal is used in the OpenPGP format, but not for its homomorphic properties).

Paillier encryption allows for addition. There again, addition occurs in a finite group (here, numbers modulo n, a big composite integer). I am not aware of implementations of this system in widespread generic crypto library (my non-awareness does not imply inexistence, though) but a simple google search finds a few Java-based implementations (Java offers BigInteger, making implementation of such systems easy).

An important point is that such encryption systems are randomized: for a given plaintext, there are many possible ciphertexts. Thus, you cannot know whether two ciphertexts correspond to the same plaintext or not. A fortiori, they do not allow comparisons (order within a finite group is not well-defined anyway). Note that a comparison method would not be compatible with a secure asymmetric encryption: anybody could encrypt chosen values to guess the encrypted data with a dichotomic search. On a general basis, the key words for that are "data mining". Performing data mining on encrypted data is a widely unexplored field, with substring matching as a kind of Holy Grail. Briefly stated, there is nothing immediately applicable there.

Thomas Pornin
  • 320,799
  • 57
  • 780
  • 949
  • At this link http://www.stanford.edu/class/cs259c/lectures/bgn.pdf it is stated that ElGamal supports additions as well if implemented with elliptic curves.Actually you can have ElGamal homomorphically evaluated on its aditions if you raise the message to a base, but then you don't need the second ciphertext and the scheme seems as Pailier – curious Mar 29 '13 at 09:23
  • 4
    There's a catch: we call "addition" the operation on curve points, but that's just a tradition. ElGamal works over a _group_ and is homomorphic _with regards to the group operation_, regardless of whether you choose to call it "addition" or "multiplication" or "frobnication". What we want is a wait to get additions _on integers_, which ElGamal does not provide, unless you accept to do compute a discrete logarithm at the end (as is done in voting schemes, where the tally is within a rather small range and can thus be searched for exhaustively). – Thomas Pornin Mar 29 '13 at 13:08
9

An example of practical use of PHE (and El Gamal in particular) is Helios Voting. With it you can publicly store encrypted voted ballots in the cloud, and also allow the public to both add them up to confirm the vote counts for each candidate, and to check that their own vote was indeed included in the total, without having a receipt that could prove how they voted to a third party.

It is open source. You can get the source code (based on Python, JavaScript, Django) here:

I don't know how easy it would be to pull pieces of Helios out into a reusable library, but it is one place to look.

nealmcb
  • 20,544
  • 6
  • 69
  • 116
4

@Thomas nailed it. There are schemes that support addition, and schemes that support multiplication (but no practical scheme that supports both). There is no scheme that supports comparison, as that would be incompatible with security.

There are also schemes that support checking whether the encrypted text contains a particular keyword (e.g., this paper), though the threat model and what is accomplished is a bit different. These schemes are oriented at situations where you yourself are the one who uploaded the data, and you remember the crypto keys, and they're focused on read-only (or read-mostly) data sets. They also reveal information that could be used for traffic analysis (e.g., the number of hits on the keyword and their location in the encrypted file).

D.W.
  • 98,420
  • 30
  • 267
  • 572
1

You can have comparisons with an order preserving encryption scheme whose security is strongly debated here and here. Also section II-A of that describes some weaknesses of OPE

curious
  • 224
  • 2
  • 7