Take the 2-minute tour ×
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.

Most of the libraries I've seen allow you to add encrypted numbers. Is it possible to subtract and multiply them?

share|improve this question
1  
Have you read the Wikipedia article on homomorphic encryption? That'd be a good starting point. Also, search on this site. I think you'll find some answers.... –  D.W. Aug 12 '13 at 22:57

2 Answers 2

up vote 5 down vote accepted

Have you read Wikipedia: homomorphic encryption and Bruce Schneier: Homomorphic Encryption Breakthrough?

In summary:

Is it possible to subtract numbers using homomorphic encryption? Is it possible to multiply numbers using homomorphic encryption?

Yes, there are many known partially homomorphic cryptosystems, each one can either multiply or add numbers.

To add two encrypted numbers, one could use Benaloh, Damgård–Jurik, or several other known partially homomorphic cryptosystems. (Many of these "addition-only" cryptosystems can also be tweaked to support subtraction. Asking "how do I do that" would be a great separate question).

To multiply two encrypted numbers, one could use Unpadded RSA, ElGamal, or several other known partially homomorphic cryptosystems.

Is it possible to subtract and multiply numbers using homomorphic encryption?

To multiply one encrypted number by a plaintext number (which, alas, is not sufficient for fully general computation) and also add two encrypted numbers, one could use Paillier, Naccache–Stern, or several other known partially homomorphic cryptosystems.

Subtraction can be implemented by encrypted "multiply by a plaintext -1" followed by encrypted addition. (Asking "how do I do that" would be a great separate question).

Is it practical to express any computation whatsoever as a series of multiplies and subtracts?

Yes. In fact, computations on decimal numbers, text strings, 2D images, etc. are almost always done by converting to binary representation, using a series of Boolean computations internally, and then converting back to a human-friendly representation. (Boolean computations can, in turn, be implemented using multiplies and subtracts, although that is slightly less efficient).

Is it possible to encrypt a few numbers, send them to a distant server that uses homomorphic encryption to do a series of "encrypted subtraction" and "encrypted multiplication" operations on those numbers, and then sends the encrypted result back -- a message that can be decrypted to give the same result as a corresponding series of subtractions and multiplications on those numbers?

Cryptographers have been hunting for such a "fully homomorphic encryption scheme" for decades. After a few decades of searching and coming up empty, cryptographers were starting to think perhaps fully homomorphic encryption is impossible.

The first known fully homomorphic encryption scheme was discovered by Craig Gentry and announced in 2009. It is an amazing theoretical breakthrough.

Alas, in that scheme, the "encrypted subtraction" and "encrypted multiplication" operations are so complicated that it's not really practical.

Now that one fully homomorphic encryption scheme has been demonstrated, cryptographers have high hopes that other, more practical systems will be discovered.

The current situation is something like the current situation with manned moon missions. People have been dreaming about traveling to the moon for centuries, but it was long thought to be completely impossible. In a great technological breakthrough, one method of traveling to the moon put 12 men on the moon, demonstrating that it is possible. However, that particular method is so expensive that it is not really practical. Still, futurists have high hopes that other, more practical systems will be discovered.

share|improve this answer

Yes it is.

Given $m_1$ and $m_2$ two numbers, if you take their naive encryption under a El Gamal public key $(p, h = g^r)$ where $p$ is a prime and $g$ a generator, $r$ a random number youl get that:

$c_1 = h^{m_1} \pmod p$; $\;$ $c_2 = h^{m_2} \pmod p$;

and

$c_1 \cdot c_2 = h^{m_1} \cdot h^{m_2} = h^{m_1 + m_2} \pmod p$

so, decrypting you'll get the sum of two numbers $\pmod p$

It has be said that when you use asyimmetric cryptography your messages are numbers. A layer of "translation" (or encoding) has to be added to transform plain english to a sequence of numbers to be used as plain text in an encryption scheme

share|improve this answer
    
this is just one example of how you can add numbers. I think every "malleable" encryption scheme allows to you to make some controlled transformations on plaintext playing only with their ciphertexts. –  ddddavidee Aug 12 '13 at 20:00
    
seems like you've answered the question for addition "so, decrypting you'll get the sum of two numbers" I need a scheme which allows subtraction of numbers –  user375868 Aug 12 '13 at 20:02
    
Addition and subtraction, algebraically speaking, are the same thing. –  pg1989 Aug 12 '13 at 20:06
    
@pg1989 - you mean I could simply use Modular Arithmetic? –  user375868 Aug 12 '13 at 20:14
    
try to write the same thing I wrote but with $-m_2$, or if you prefere, try to compute $c_1/c_2$ ... –  ddddavidee Aug 12 '13 at 20:31

Your Answer

 
discard

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.