Let's say that we want an untrusted person do to a calculation on a 32 bit floating point number and send us back the result, without learning what the specific number was that we care about.

For the sake of argument, let's assume that a partially homomorphic algorithm was not sufficient and that we needed to be able to evaluate any polynomial of any depth.

One way to do this would be to use fully homomorphic encryption which I've heard takes on the order of 2GB to encrypt a single bit, and takes about 10 minutes to AND two encrypted bits together due to bootstrapping / etc.

Another method would be something outlined here: Low Tech Homomorphic Encryption

The idea is to make a file listing all possible 32 bit floating point values starting (in hexadecimal) at 0x00000000 and ending at 0xFFFFFFFF.

We could have the untrusted party perform the operation on every value in the file, get it back, and then, since we know which value we actually cared about, we'd be able to know what the result is, without the untrusted party gaining any information about our value - other than it being 32 bits and presumably that it was representable by a floating point number, since the circuit asked to operate on the data looked like floating point operations.

Going that route, the list of floating point values is 16GB (2^32 different values, each being 4 bytes big).

Doing any floating point operation on this list of values - or doing a floating point operation between two lists of values, which would represent two "encrypted" floats - is going to be pretty quick since you can either go SIMD/Multithreaded, or send it over to a GPU to plow through.

The operations are very simple and massively parallelizable.

Given this, how does this technique of homomorphic obfuscation compare to modern state of the art homomorphic encryption?

It seems to have as much security as the real thing, and seems like it's smaller and faster. Is that true?

  • $\begingroup$ It would be reasonable to re-consider "floating point number". I'd suggest rational numbers with bounded numerator and denominator . $\endgroup$ – Vadym Fedyukovych Oct 21 '16 at 9:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.