Comments

derp • September 25, 2012 8:33 AM

cryptDB prototype by MIT works pretty well doing homomorphic encryption only problem is it can’t do square roots

Fgdsaduxrmkrzckq • September 25, 2012 9:16 AM

Ironic that American Scientist registration requires an e-mail address (using an e-mail address as Login is inherently unwise for the user) and only an 8 character password —that does not permit symbols.

True, the user may perceive nothing of value in the content they read or comments they post. Unfortunately, just such data is of enough interest to some that it’s for sale or subject to subpoena.

posedge clock • September 25, 2012 9:18 AM

Are there implementations that can permit more than multiplication and addition?

Multiplication and addition are great for DSP, but little else. Real-world algorithms involve decision making, boolean algebra, table lookups, etc.

Nyhm • September 25, 2012 9:58 AM

This could potentially provide properties pertinent to Bitcoin projects. I had written some notes on a Bitcoin-centric distributed service, which needed this type of cryptography to work (but I didn’t know about FHC).

Anyone have any extra research grants lying about?

1PTxHjhrJDHmZqBD3rTEGjTvzmbECNF5Ku

Curious • September 25, 2012 10:52 AM

Resident of the internet signing in:

How can/could anyone know if an applied homomorphic encryption scheme is “fully” homomorphic and not something just just appear to be “fully” homomorhpic (being somethin else instead)?

I am simply guessing and sort of taking for granted that bad things could happen if there was no way to really know if a homomorphic encryption scheme is a “full” one or not.

My apologies if my question appear to be more of a meaningless question. It’s not like I have an idea of how the math behind this is supposed to work.

Henning Makholm • September 25, 2012 11:07 AM

@posedge: From the look of the article, what these systems really provide at the moment is multiplication and addition on single bits, that is, AND and XOR. If you have enough bits, you can build anything you want from those two components.

@Curious: Being fully homomorphic is a fairly simple mathematical property, and it’s a standard part of inventing a homomorpic cryptosystem that one publishes a mathematical proof that the homomorphism works, which anyone is then able to verify at his leisure.

Being secure against attackers is something completely different, which is hard to prove, except in relative terms by proving that anyone who is able to break the scheme would also be able to solve the underlying “presumed-hard” problem (approximate GCD), which is thought to be impossibly hard. But that is more or less the same kind of guarantees you get for public-key cryptosystems too, and symmetric ciphers usually don’t have even that.

Coyne Tibbets • September 25, 2012 11:38 AM

Some really interesting and mind boggling concepts are implied here.

For example, imagine this: I have some data I want processed by a program, and I don’t want the program to know what it is. The program author doesn’t want me to know how the program works.

So I encrypt my data with my public key, and hand it to the program, which is run on my computer…the program processes it without the program ever being decrypted, and hands me back the processed data without ever knowing what the data was. I use my private key to decrypt the correct result.

Aaron W • September 25, 2012 11:47 AM

How far out is this from real-world use? Page 8:

“Homomorphic addition takes milliseconds, multiplication generally less than a second. These timings are a vast improvement over earlier efforts, but it’s sobering to reflect that they are still an order of magnitude slower than the performance of the ENIAC in 1946.”

And that’s not even a fully homomorphic implementation. So it’s going to take a solution that’s orders of magnitude faster (quantum computing?) to make this viable.

Jeff • September 25, 2012 12:39 PM

I don’t see how homomorphic encryption is supposed to solve any practical problem.

For pure computation like arithmetic – I can just use my own computer for that, and the overhead of homomorphic encryption would probably far outweigh any economies of scale that cloud computing might have.

The only kind of “computation” that I need someone else for is querying a database I don’t have – for example, it would be nice if I could hand Google an encrypted search term and get encrypted results back without them knowing what I searched for. But a homomorphic system can’t do database lookups without reading the whole database (if it reads only a subset, it’s leaking information).

Natanael • September 25, 2012 1:06 PM

I would consider Secure Multiparty Computation more useful in many cases like these as it is actually usable today, although it requires you to trust at least half of the participants to collaborate in most cases. If you only have one system to run the computation on, homomorphic encryption would be the only choice.

B. D. Johnson • September 25, 2012 2:18 PM

It’s another front in the encryption arms race. Can you figure out a homomorphic system that would operate fast enough to be practical before we have computers powerful to render the encryption vulnerable.

I’m reminded of that old CS joke about the algorithm that correctly predicts the weather worldwide for the next 24 hours, but it take 3 days to run.

The application that comes to mind for me is smaller computations, instead of data-crunching. Like third-party decentralized authentication. (e.g. OpenID). If you could get OpenID to verify your identity for login purposes to a third party without having to even give them your personal details (only an encrypted version of them) and to log in providing an encrypted version of your key, it’d open some interesting doors.

askme233 • September 25, 2012 3:49 PM

Applying homomorphic encryption to a Real World application in which performance is not needed: Anonymous Banking

All accounts remain anonymous and encrypted. The customer can still transact, adding and subtracting funds. Totals hash maintains data integrity and verifies completeness/accuracy. Cash/Asset pools back up the encrypted accounts and tie out at the summary level, but reveal nothing about the transactions.

Banker knows only that it has the money it should at an aggregate level, customer is the only one that can decrypt the account to the transaction level detail or make any transactions.

Transactions cannot be tied to an individual customer.

Thoroughly illegal in the US for that very reason: KYC

derp • September 25, 2012 5:06 PM

you don’t have to absolutely encrypt everything and worry about massive overhead. read up on cryptdb schema annotations you can either encrypt everything or selectively encrypt what information you want to keep private. for instance forum software only needs a handful of encrypted fields like private msgs and hidden forums.

even better user passwords are used as keys in the sql proxy, so if the server is seized the only people compromised are those who are logged in (and have their key in the proxy).

it’s still basically a research prototype but eventually they’re going to release a full beta version

Paeniteo • September 26, 2012 4:21 AM

@Jeff: “I don’t see how homomorphic encryption is supposed to solve any practical problem.”

The last page of the article provided some example use cases.

Peter Breuer • December 14, 2012 1:13 PM

Why do people think that homomorphically encrypted arithmetic takes extra time? I don’t get it! Ordinary arithmetic is just a question of combinatorial logic between bits on a chip, and encrypted arithmetic is just a different combinatorial logic. One is as fast as the other.

So where does the strange idea that it takes longer come from?

More problematic, it seems to me, is that any algebraist can decipher most kinds of homomorphism easily. If division is implemented in the arithmetic, one just has to try x/x, in encryption, for any encrypted x, to get the encryption of 1. Then one gets the encryption of 2 by doing the encrypted arithmetic for 1+1. Etc. So one constructs the code book in 2^32 steps.

Yes, I can defeat that, but you’d have to ask me!

If division were implemented as a software routine instead, then one would likely have good evidence for certain constants (0, 1, 2, ..) being embedded encrypted in the routine. And one could probably recognise the algorithm anyway and figure out which constants were in use where. Please correct me if you know better! All I can think of that might defeat that is implementing Fourier’s algorithm for modular division, but them one might as well do it in hardware.

And if one merely has “<” implememted encrypted, or any other ordering, then one gets 0 as the unique number that is > one less number than it is < than. Etc.

So how would encrypted arithmetic defeat any attacker with less than an ounce of brains? Further defense is required (which I can think of, but I have never seen mentioned).

But all this about “takes longer” is just nonsense. DO people somehow imagine (falsely) that encrypted arithmetic is just done by sticking hardware codecs on the inputs and outputs of an ALU? That WOULD make it take longer, but it’s a daft way to go. And I’m not even sure it would make thing stake longer overall, given that a processor is pipelined .. it merely needs to have thruput of 1 arithmetic operation per cycle, never mind how many cycles the operation actually takes .. 100 would be a bit much, but 10 would be fine. So long as one can do 1/10th of an operation per cycle as a single stage, then a pipeline 10 stages long for the operation would average one operation per cycle.

dan • December 20, 2012 4:45 PM

Hi, do you people know some homomorphic schemes which support homomorphic property even when ciphertexts produced using say different keys are for example multiplied between each other???

Thanks!.

Yaseen Taha • October 3, 2015 5:22 AM

Hello, i have a question about homomorphic encryption, why addition and multiplication only make any scheme fully homomorphic while as i know division is not supported, please can one show me how to obtain or which scheme can support division and floating point operations ?

Clive Robinson • October 3, 2015 12:04 PM

@ Yaseen Taha,

… why addition and multiplication only make any scheme fully homomorphic…

The simple answer is that the only numbering system a CPU understands is integers within a fixed fieldand the only operators it needs to perform the basic maths operations are,

The bit wise / logical operators XOR, AND, OR and word wise / mathmatical operators ADD and LSL, along with branching instructions

To do SUB you use “Two’s complement” where you use XOR and ADD 1 to complement the number ( invert all the bits and add one converts an integer from the positive to negative).

If you examin the truth table of the AND gate you will find it is the same as a one bit multiplier using this along with LSL will enable you to do the equivalent of “School Multiply” to any size you require.

If you use an array of logic gates to do multiplies –such as the Walace tree– you end up with a result that is twice the width of the input words. You can output this or you can output part of it for ordinary multiplication you assume that the radix point is to the right of the least significant bit of the lowermost word. However if you normalise numbers to the range of 0-1 then the radix point falls to the left of the most significant bit of the upermost word. This latter method is used for floating point numbers with the actuall result exponent calculated seperatly (by addition).

Division within a field can be done by multiplication, you can look up various ways to do this one such method can be found in Knuth.

I hope that gives you sufficient info to either answer your question, or to give you a starting point to search for answers.

Leave a comment

Login

Allowed HTML <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre> Markdown Extra syntax via https://michelf.ca/projects/php-markdown/extra/

Sidebar photo of Bruce Schneier by Joe MacInnis.