7 ms·
An open-source fully homomorphic encryption library
- jychang 13y agoIt's basically this, http://eurocrypt2010rump.cr.yp.to/9854ad3cab48983f7c2c5a2258e27717.pdf http://eurocrypt2010rump.cr.yp.to/9854ad3cab48983f7c2c5a2258... , I think. I wonder what the performance numbers are.
- tbmbob 13y agoThis is not quite true: the mathematical problems upon which they base their security, though related, have some important differences. Most significantly, the problem upon which this new implementation is based (Ring-Learning with errors) is theoretically much more time and space efficient than the problem upon which your linked implementation is based (approximate GCD).
- symmetricsaurus 13y agoThe README has lots of really cool words and names and things. But it doesn't say what homomorphic encryption is or what it is good for. Could someone enlighten me?
- jychang 13y agoTL;DR: It allows you to edit encrypted stuff without decrypting it. For example, if you had a book of everyone's salaries, you can ask Bob to add $5000 to it. Normally you'd have to give him the key, but with homomorphic encryption you can just perform operations without decrypting it and having Bob know everyone's salaries. This becomes really powerful for stuff that you need to work with lots of data without knowing the contents of - cloud computing, for example.
- opminion 13y agoThink Google without the privacy issues.
- aardvark179 13y agohttp://en.wikipedia.org/wiki/Homomorphic_encryption http://en.wikipedia.org/wiki/Homomorphic_encryption Basically encryption dchemes that allow operations to be done on the ciphertext that give a result that can be decrypted and is correct plaintext.
- davidw 13y ago"Homomorphic encryption is a form of encryption which allows specific types of computations to be carried out on ciphertext and obtain an encrypted result which decrypted matches the result of operations performed on the plaintext. For instance, one person could add two encrypted numbers and then another person could decrypt the result, without either of them being able to find the value of the individual numbers." From: http://en.wikipedia.org/wiki/Homomorphic_encryption http://en.wikipedia.org/wiki/Homomorphic_encryption I don't know much about it either. For a recent project, I'd be interested in searching and sorting of encrypted data; I wonder if this is up to that. The tricky bit with search is that in many cases, you want to be able to search for substrings, not just an exact match.
- sstarr 13y agoIt's like regular encryption except you only need to encrypt 1 in 10,000 bits for it to be effective.
- eru 13y agoWhy troll?
- sstarr 13y agoSince when is making inoffensive jokes considered trolling? I was amused by the similarity between the words 'homomorphic' and 'homeopathic' so I thought other people might be too. The number of downvotes my attempt at humour received would suggest that I was wrong.
- eru 13y agoOh, HN has a rather strict line on idle jokes. It's not so much that we mind them, but there's a slippery slope into a low signal to noise ratio. Please pardon my comment about the trolling. Sometimes it's also hard to determine intentions via text-only communication.
- Terretta 13y agoThe most approachable layman's summary of homomorphic encryption I've seen (with illustrations): http://www.americanscientist.org/libraries/documents/201286159329266-2012-09CompSciHayes.pdf http://www.americanscientist.org/libraries/documents/2012861... [PDF] Try this before Wikipedia.
- Flimm 13y agoGreat article, thanks.
- betterunix 13y agoA worthwhile example is the problem of encrypted spam. In theory, spammers could use public keys to evade spam filters, and systems like PGP and S/MIME do not give you any ability to prevent that. On the other hand, an FHE system would allow Google to perform spam filtering on your encrypted email, and so that you receive both the email itself and an encrypted "spam or not spam" bit from Google. You can imagine this sort of thing be applied in other situations -- advertising, options modeling on EC2, etc. Unfortunately, FHE is nowhere near practical enough to do that sort of thing. Maybe in a decade or two we will see FHE implementations used outside the research community.
- nraynaud 13y agoI skimmed some docs, and I can't find the list of operation that can be done with that. Is it numerical stuff like addition/multiplication? Is it text editing?
- betterunix 13y agoAny algorithm.
- kvakvs 13y agoGPL? That doesn't encourage too many uses of this code. Especially for commercial purposes.
- pja 13y agoFeel free to write your own version and release it under a more permissive license then.
- krichman 13y agoWhile it seems ridiculous to complain about which FOSS license is being used, it's a legitimate observation since there are certain app stores that disallow GPL'd code entirely. It'd be nice if the author was willing to change the license but it's not something one can reasonably demand.
- new299 13y agoIt would also be nice (actually nicer) if those app stores would allow GPL code.
- lucian1900 13y agoIt's often the other way around, the GPL disallows distributing the software under the very restrictive terms of those app stores.
- new299 13y agoSure, but it would be entirely possible for Appstores to make their terms less restrictive, I don't blame people for using licenses like the GPL which are designed to push people in that direction.
- lucian1900 13y agoI don't think it's very likely app stores will change their terms in the direction of complying with the GPL. I don't blame people using the GPL either (except possibly people that use it for libraries), nor people that publish apps on the various stores, I was just clarifying a point.
- JacobiX 13y agoHolomorphic encryption is a very interesting concept especially in a cloud setting. One could perform some operations on encrypted client data. But I don't know if it's mature enough.
- drostie 13y ago"Fully homomorphic" means "a computation can be done on two encrypted values without decrypting them." It is an extension of partially homomorphic systems, which allow some computation which cannot be extended to arbitrary computations. A good usage case for partially homomorphic systems is public elections. Suppose given E(x) and E(y) you can efficiently compute E(x + y). Now imagine that you arrange a set of bit-fields as: 1000 1100 0111 0111 0100 1110 0010 1001 (random) (check bits) (votes Alice) (votes Bob) In other words, the current vote tally is being represented as a number E(0x8C774E29). You can now create two ballots, E(0xBF010100) and E(0xBF010001). You can add either of those ballots to the vote tally even though you cannot read the vote tally. We can make all of these numbers public knowledge without disclosing your vote -- i.e. a public database can say "Alice's vote was E(0xBF010100)" and "Bob's vote was E(0xDB010001)" and once that encryption is performed, third parties cannot actually verify that Alice didn't vote for Bob or vice versa. So any member of the population can take the public database and confirm that the arithmetic was done properly on the encrypted vote tallies, without figuring out what the actual votes were. Then at the highest level, the tally can be decrypted to find out that Alice won the vote, without disclosing exactly who voted for her. The "check bits" form here a sum of votes as a quick check that someone didn't just add some random ballot in there to screw with the system. Of course, you need more bits as you want to have more candidates and more voters; and there are problems with confirming that a number looks like 0x010100 and not 0x050500. But fundamentally you can get these really cool cryptographic voting systems which preserve the anonymity of your vote at the lowest level, but can be audited at the lowest level (i.e. we can potentially remove votes, say, from people who were not alive at the time of the election), the votes have perfectly auditable mathematics up to the regional level due to the public databases of encrypted votes; and then once the population is large enough to suitably anonymize the vote, you can decrypt and tally votes publicly too. Now that's if you just have some function esum such that esum(E(x), E(y)) = E(x + y). If you have enough to make a full set of logical gates, you could in principle do an entire computation on a set of inputs which you couldn't possibly know, so that the "cloud" could "compute" with your data without ever actually knowing it.
- bradleyjg 13y agoIn theory if you have arbitrary addition and arbitrary multiplication (i.e. a ring structure) you can perform any transform on the cyphertext that you could on the (finite) plaintext. As a practical matter conplext transforms tend to produce enormous cyphertexts that can't be evaluated in any reasonable time. Which is why a lot of the cutting edge work is in renormalizing, even at the cost of restricting operations (thus somewhat rather than fully homomorphic).
- doe88 13y agoFor those trying to compile it, you'll need to install the last version (6.0.0) of NTL (the Ubuntu package from 13.04 does not provide this version).
- tocomment 13y agocould you use something like this to make an anonymous bitcoin protocol?
- tlrobinson 13y agoCheck out Zerocoin, though I don't think it uses homomorphic encryption https://en.bitcoin.it/wiki/Zerocoin https://en.bitcoin.it/wiki/Zerocoin
- StavrosK 13y agoThis is not terribly on-topic, but, if you're interested in cryptography, Dan Boneh (Craig Gentry's advisor) is currently giving a Coursera course on it: https://class.coursera.org/crypto-006/class https://class.coursera.org/crypto-006/class I'd highly recommend it, it's amazingly interesting, and Boneh is very good at explaining things. I used to think that cryptography was hopelessly impenetrable, but it turns out most algorithms (well, mostly symmetric cryptography) are simple to understand. We're currently at asymmetric crypto and the math's starting.
- gbaygon 13y agoBe aware that you will need 1 hour/day for the videos, and a couple of hours/week to read additional material and exercises. I joined the course but couldn't keep the pace. That being said you can still access the material without doing the exams to do the course at your own rhythm.
- StavrosK 13y agoHmm, each week of lessons took me roughly 3 hours a week for the whole course. Doing them at your own pace is also very good, though, as you're pretty much getting the same benefit, but not as much motivation.
- gbaygon 13y agoYes you are right, i should clarify that this is my personal experience, with zero previous knowledge on cryptography, and pausing the video continuously to investigate the topics and do some calculations.
- StavrosK 13y agoI didn't have any prior knowledge either, I guess this is due to each person's method of studying. I generally don't go in very much depth.
- tlrobinson 13y ago
- deleted 13y ago[deleted]
- escaped_hn 13y agoI thought homomorphic encryption wasn't secure or complete due to the fiaso that happened on SE earlier this month?
- walrus 13y agoThe SE thing was someone claiming a company was doing homomorphic encryption when they really weren't. (Here's a link for others: http://crypto.stackexchange.com/questions/3645/how-is-ciphercloud-doing-homomorphic-encryption http://crypto.stackexchange.com/questions/3645/how-is-cipher...)
- Zarathust 13y agoWhile I greatly applaud the effort of implementing such a complex crypto scheme, I'm afraid I will have to wait years before using something like this. Who wants to be the early adopter of a cryptographic library?
- topbanana 13y agoOK, I read this as homeopathic. I need some sleep