[HN Gopher] Google's fully homomorphic encryption compiler - a p...
___________________________________________________________________
Google's fully homomorphic encryption compiler - a primer
Author : mmastrac
Score : 419 points
Date : 2023-02-14 00:40 UTC (22 hours ago)
(HTM) web link (jeremykun.com)
(TXT) w3m dump (jeremykun.com)
| forty wrote:
| Is there proof that this is secure? (ie that no information can
| be found on the plaintext when only having the ciphertext?)
|
| I'm hoping something of the like of "this is secure if AES is
| secure"
| j2kun wrote:
| It's based on the "Learning With Errors" problem and it's
| relative, "Ring Learning With Errors", both of which have
| reductions to lattice crypto problems, the same sort that are
| in the new NIST proposals for post quantum cryptography. See
| this article for some more info about how security is
| evaluated: https://jeremykun.com/2022/12/28/estimating-the-
| security-of-...
|
| That said, the compiler itself doesn't use any crypto. It
| generates code for a backend API, and the backend implements
| the FHE scheme
| blibliblo wrote:
| I could not find on which algorithm this compiler is based at
| first sight.
|
| I know of an other library for homomorphic encryption Lattigo
| (https://github.com/tuneinsight/lattigo) which is based on Ring
| Learning with Errors.
|
| The security of RLWE is "believed" to be strong (meaning there
| has not been a proof of the opposite yet). It is based on the
| Lattice problem which is likely to be resistant even to quantum
| computers.
|
| For a more formal and complete explanation, the paper "A Decade
| of Lattice Cryptography" was very instructive.
| https://eprint.iacr.org/2015/939.pdf
| [deleted]
| Charlie_26 wrote:
| I may have misread the title and thought that was one bigoted
| compiler
| antognini wrote:
| I have a very basic question about fully homomorphic encryption.
| As I understand it, the encryption scheme ensures that an
| adversary who has access to the physical computer cannot
| determine what data the computer program is operating on, even by
| inspecting the physical states of the machine.
|
| My question is whether or not it is possible for the adversary to
| determine what computer program is being run. To use the example
| provided by the post, it is not possible to determine which two
| integers are being added --- but is it possible to know that the
| computer is running a program that is adding two integers?
| ChadNauseam wrote:
| It is possible to determine what algorithm is being run. To
| prevent that as best as possible, you want Indistinguishability
| Obfuscation.
| fatneckbeard wrote:
| sounds like you could have anonymous currency.
|
| heres our FHE bank. we both have accounts. the entire ledger is
| encrypted.
|
| i give you 5 dollars, i have no idea what your starting and
| ending balance, but i am still able to initiate a transaction
| that will deduct 5 from mine, and add 5 to yours, and verify i
| actually have 5 to send, and the entire thing will be done
| without exchange of information about balances with any outside
| party. its just approved/declined by the algorithm. i can see my
| own balance with my own key, you can see your own balance with
| your own key, but we cant see each others balance. ---nor could
| anyone else including the bank---.
|
| weird. and kind of scary. and most definitely illegal in the real
| world since the bank itself could never prove its reserve level
| of deposit met the percentage set by government.
| CraigJPerry wrote:
| >> since the bank itself could never prove its reserve level of
| deposit met the percentage set by government
|
| There's no minimum reserve set by the fed anymore:
| https://www.federalreserve.gov/monetarypolicy/reservereq.htm
| aspyct wrote:
| Other countries exist.
| eru wrote:
| See https://en.wikipedia.org/wiki/Reserve_requirement
|
| Many countries don't have a reserve requirement. The US was
| a bit of a laggard.
|
| Minimum reserve requirements were always a bit silly. You
| want your banks to have a thick capital cushion for its
| debt. Whether they have reserves on hand is an operational
| problem they can solve themselves, and doesn't have
| systemic consequences.
| PeterisP wrote:
| It's not really about the reserve requirements, but about
| basic accounting requirements, which all banks do have. At
| its fundamentals, bank balances are not some storage of "your
| money", they are recording of how much the bank legally owes
| you (or vice versa). And of course the bank has to know
| exactly what liabilities they have according to their
| contracts, so they need to see the balances. They also need
| to be able to add arbitrary quantities of new money to the
| FHE scheme when cash is paid in and remove it when it is paid
| out.
| piaste wrote:
| Or, more succinctly, what makes a bank a bank is that it
| will loan out money deposited by other people.
|
| If the money is just sitting there and can't be moved or
| even counted without the owner's private key, it's not a
| bank, it's a vault.
| CraigJPerry wrote:
| >> what makes a bank a bank is that it will loan out
| money deposited by other people
|
| No, a bank creates money to loan out from nothing. No
| deposits required.
|
| As a sibling comment points out, other jurisdictions
| exist so here's the UK central bank's explainer on the
| topic: https://www.bankofengland.co.uk/explainers/how-is-
| money-crea...
| esperent wrote:
| What purpose would this serve? Just anonymity for the sake of
| anonymity, or something else?
| noduerme wrote:
| I love/hate this. It's one of those ideas that's incredibly
| appealing to people who already have other ways of doing it,
| and incomprehensible to people who would actually benefit from
| it. Most things of that ilk get blown up because once it's
| peddled to the masses, consumers don't verify that it's
| actually run the way it's supposed to be run, and someone
| writes in a backdoor (FTX). Then it just takes a few hyped up
| claims and burst bubbles before it becomes a punchline.
|
| What _would_ be sort of awesome, though, would be a distributed
| bank (or prediction market, or casino) along these lines. If
| every node can donate processing power to run totally encrypted
| transactions, it 's a game changer. You could finally rely on
| client-side processing to deal poker hands and process game
| states without a central server, for example.
| mik1998 wrote:
| GNU Taler does something similar, except without homomorphic
| encryption. It only anonymizes the payer however.
| vintermann wrote:
| Sure. And then, after you've transferred 5 dollars to me, I say
| "What 5 dollars? What are you talking about?" and refuse to
| hand over the thing that you thought you bought.
|
| Add perfect anonymity to the mix and I get to do it over and
| over again, too.
| [deleted]
| 3np wrote:
| You could still design the scheme such that the sender can
| produce a cryptographic proof. Equally applicable for tax
| auditing etc.
| macrolime wrote:
| You could set it up so whoever initiates a transfer could get
| a kind of receipt that proves they initiated a transfer of X
| dollars to whomever.
|
| So if Alice transfers 5 dollars to Bob and Bob says "What 5
| dollars? What are you talking about?", then Alice could say,
| well here's my receipt, that's signed by my private key and
| the private key of the FHE bank, that shows that I sent the
| money to Bob and the FHE bank executed the transfer.
| ricksunscreen wrote:
| You get this for free with FHE. In the event of a dispute,
| you can reveal the randomness and message that produce the
| public ciphertext given the user's public key.
| 3np wrote:
| You don't need FHE for that. It's possible through some zero-
| knowledge schemes, such as zk-SNARKS, which is implemented in
| and popularized by shielded transactions on Zcash.
| easrng wrote:
| You don't need zk-SNARKS for that. It's possible through some
| schemes, such as blind signatures, which have been
| successfully implemented many times but their usage for
| currency has (iirc) proved legally problematic.
| rattlesnakedave wrote:
| For the uninitiated:
|
| https://sceweb.sce.uhcl.edu/yang/teaching/csci5234WebSecuri
| t...
|
| Chaumian mints are gaining some popularity in the bitcoin
| world: https://fedimint.org/
| molsongolden wrote:
| Has anyone used Vaultree[0]? Their product is FHE-as-a-Service
| and they claim "near plaintext speed".
|
| I've seen a few FHE posts roll across the front page recently and
| they all make me think of Vaultree because they sound like
| they've got it sorted.
|
| [0] https://www.vaultree.com/how-it-works/
| whatshisface wrote:
| "Encrypted queries for an encrypted database" could be as
| straightforward as encrypting both the keys and values using a
| known public key and putting the results in MySQL. You have to
| be careful with the claims made around these kinds of things
| because they often appear to be more complex than they are.
| hn_throwaway_99 wrote:
| Huh? How would you search on any encrypted fields?
| KMag wrote:
| No subfield matches, no comparisons other than == and != on
| the whole field, and only works with deterministic
| encryption... so leaks like a sieve under many threat
| models.
| admax88qqq wrote:
| lol no it's not.
|
| Up can't do a range on encrypted data. If you encrypt 5 and
| encrypt 10, how do you expect to compare the encrypted
| results to see which is greater?
|
| If all you do is key value lookup then sure. But SQL is much
| richer than that.
| amadvance wrote:
| Even lookup is not easy to be done securely. You don't want
| that a malicious server/database knows that you are
| accessing always that record.
|
| See this discussion about how to achieve that:
| https://news.ycombinator.com/item?id=31668814
| teraflop wrote:
| It's not nearly that simple. If your encryption scheme is
| deterministic then this leaks a ton of information, because
| anybody with the public key can just encrypt lots of values
| to reconstruct a mapping between plaintexts and ciphertexts.
| On the other hand, if your encryption scheme isn't
| deterministic, then you can't predict what encrypted value
| you should query for.
| 5ersi wrote:
| Add random data to it, so that all (equivalent) data is the
| same length. For example, if you have a four byte field
| that represents some monetary value, add four more bytes of
| random data and encrypt it.
| kientuong114 wrote:
| How would you run queries over that?
| whatshisface wrote:
| Those kinds of problems have never stopped any company from
| offering a service with a lot of nice graphics on the home
| page.
| hn_throwaway_99 wrote:
| I'm really, really curious to how it actually works under the
| covers. Needless to say, I'm sceptical, primarily because "near
| plaintext speed" fundamentally isn't currently possible with
| true fully homomorphic encryption, at least in my
| understanding.
|
| For example, they give an example of running queries against
| data that is never decrypted. I'm very curious as to how they
| do this. I've used blind indexes [1] to solve the "encrypted
| data searchability problem" in the past, but with blind indexes
| you're still left with the fact that you can only do exact
| matches - you can't sort the data or use less than/greater than
| queries.
|
| With true FHE you should be able to sort results, but my
| understanding is that it's several orders of magnitude slower
| than plaintext searching, so I'm very curious as to what
| Vaultree is actually doing.
|
| 1. https://medium.com/@joshuakelly/blind-indexes-
| in-3-minutes-m...
| bawolff wrote:
| > "near plaintext speed" fundamentally isn't currently
| possible with true fully homomorphic encryption, at least in
| my understanding.
|
| If you skip the security requirements, applying rot13 twice
| is a fully homomorphic scheme that achieves plaintext speeds
| ;)
| fragmede wrote:
| It's up to them to define "near", but I'd consider
| https://spiralwiki.com/ (Samir Menon and Prof. David Wu at UT
| Austin) "nearly" usable compared to regular wikipedia.
| yarg wrote:
| FHE @ plain text speed?
|
| Absolute bullshit.
|
| > You choose the encryption standard in use for the database,
| from AES, DES, 3DES, Blowfish, Twofish, Skipjack, and more.
|
| That seems very wrong ((as far as I know) those standards are
| not in any way designed in such a way as to permit operations
| on their cyphertexts).
|
| > Vaultree has achieved major breakthroughs in several
| encryption technologies, allowing organisations to process
| fully encrypted data at near plaintext speed and keep their
| data safe even in case of a leak.
|
| That seems even wronger (security via obscurity at best).
| bawolff wrote:
| > That seems very wrong ((as far as I know) those standards
| are not in any way designed in such a way as to permit
| operations on their cyphertexts).
|
| Those standards are meaningless by themselves without
| specifying a mode (e.g. GCM, CTR, CBC, ECB, etc). A thing
| people sometimes try to do with them (no idea if this is what
| vaulttree is doing) is use some less secure mode that is
| determistic and do equality matching (this is almost always a
| bad idea and usually leaks way more than you would naively
| assume). For example, if you use ECB mode you can search as
| long as you are searching along block boundries.
|
| https://www.microsoft.com/en-us/research/wp-
| content/uploads/... is an interesting paper about this sort
| of thing.
| l33t233372 wrote:
| ECB should never be used under any circumstances. Library
| creators would do well to rename their functions along the
| lines of ECB_NEVER_USE_THIS_IS_NOT_SECURE.
| bawolff wrote:
| In case it wasn't clear from my comment - i agree 100%
| yarg wrote:
| https://upload.wikimedia.org/wikipedia/commons/f/f0/Tux_ecb
| ....
| hectormalot wrote:
| How I read it is that you specify which ways you will use a
| column and then VT will create the various encrypted columns
| to support this. Deterministic shared key for matches only.
| Ordered encryption for ranges and FHE for various
| calculations. The latter probably being quite slow. I don't
| think they are rolling their own crypto, just combining a lot
| of existing algorithms in various ways.
|
| I could see a use cases in either defense in depth and/or
| storing data in the cloud while having your keys somewhere
| else.
| yarg wrote:
| They're claiming to have made breakthroughs in several
| encryption technologies, not that they've figured out a
| clever way to glue some things together.
|
| I could be wrong, but it smells like snake oil to me.
| bahorn wrote:
| From their FAQ and blog posts, I don't believe they apply much
| FHE. Seems what they do is use work from a different subfield
| [1], which seems to be able to achieve the required speeds and
| still be able to work with more complex queries.
|
| Techniques I'm seeing in the Pappas et al. paper mentioned in
| the history section of [1] to do more complex queries seems
| pretty cool, and I imagine the performance has been improved a
| bit in more recent work.
|
| [1]
| https://en.wikipedia.org/wiki/Searchable_symmetric_encryptio...
| lwansbrough wrote:
| Let's put it this way.. if they had actually cracked true FHE,
| they wouldn't be a company anymore having been bought by the US
| government for billions of dollars.
| smoldesu wrote:
| Proprietary FHE is like doing card magic on a loaded deck. I'm
| sure there are technical merits to what they're doing, but
| because they _also_ refuse to show me how the trick is done, I
| can similarly assume there are some ugly cut corners inside
| too.
| bawolff wrote:
| They figured out that most people just look for buzzwords and
| are thus easy to separate from their money when it comes to
| crypto.
|
| Encryption as a service is non-sencical. If the provider has
| the key, and does the encryption and decryption, then who are
| you protecting the data from[1]? What magical malicious person
| are you imagining that would somehow be able to get their hands
| on the encrypted data without also getting the key?
|
| [1] this is very different from FHE where the provider recieves
| the data already encrypted, and at no point has access to the
| decryption key.
|
| Edit: their website claims "Data is never decrypted" but then
| claims they decrypt it before returning it. So its confusing
| what they are actually doing - but i am 99% sure they are
| selling bullshit.
| pmarreck wrote:
| It seems like what they do (maybe?) is encrypt the
| binary/string data but still let you search or join on it by
| encrypting queries to the same data? So in other words the
| operations on the data are not encrypted but the data itself
| is? This might work for whole words but for partial word
| matches I think you'd have to do a byte-for-byte character
| swap which exposes it too much to statistical cryptanalysis?
| And this still leaves computations on numeric data
| vulnerable?
| hn_throwaway_99 wrote:
| What you are describing is basically a blind index (search
| for it, there are lots of good resources online). Blind
| indexes can be quite useful, but they have a number of
| limitations - the partial match issue as you point out, but
| also you cannot do range queries or sorting, and they leak
| some information (e.g. duplicates have the same index
| value). Blind indexes are most definitely _not_ fully
| homomorphic encryption.
| pmarreck wrote:
| Right, but this service isn't advertising FHE.
| hn_throwaway_99 wrote:
| That's false. From the FAQ on their homepage:
|
| > Vaultree's proprietary encryption breakthroughs are in
| various encryption technologies traditionally limited to
| niche use cases. We finally enable users to process
| entirely encrypted data with Fully Homomorphic and
| Searchable Encryption (FHSE) and other technologies in
| the field. Explaining what they are would take all day,
| but here's a one-liner: FHSE enables data processing to
| be run directly on encrypted data in the same way as on
| plain text data.
| bawolff wrote:
| > It seems like what they do (maybe?) is encrypt the
| binary/string data but still let you search or join on it
| by encrypting queries to the same data? So in other words
| the operations on the data are not encrypted but the data
| itself is?
|
| Are you saying something along the lines of - they split
| the data in to tokens, deterministically (no iv) encrypt
| each token, and then do equality comparisons on the
| encrypted tokens?
|
| Maybe, and it would explain why they say you can chose a
| cipher and then list a bunch of standard symmetric ciphers.
| However such schemes usually leak too much in practise
| (even at the granuality of whole words).
|
| More importantly, it really doesn't matter. They have both
| the key and the encrypted data. If someone hacks their
| system, the best encryption in the world won't help if the
| attacker steals both.
| pmarreck wrote:
| Why would they need the key? It says everything's
| encrypted/decrypted on the client. If they did encrypted-
| token indexing server-side, they wouldn't need to
| decrypt. Agreed that this scheme would eventually leak
| too much information.
| bawolff wrote:
| Its unclear, but i think they are using client to mean
| their frontend server. They also say that the user
| recieves plaintext, and they integrate with cloud key
| provider services which would make no sense if they
| aren't using the key.
| pmarreck wrote:
| what is the point of this then? there's no actual secret
| then, LOL, are you sure?
|
| If that's the case it simply moves "the need to trust the
| DB host" to "the need to trust the encrypt/decrypt
| intermediary" (literally a MITM, LOL)
| Dylan16807 wrote:
| What statistics do you have in mind there?
|
| If you're using FHE to encrypt a text search, then you'll
| generate a match/no-match boolean for each character. The
| server won't know which is which. Then you'd probably OR
| large blocks of these together, to give you a match/no-
| match boolean for each segment of text. Then you return all
| the booleans to the client, who decrypts them.
| CGamesPlay wrote:
| Hmm, given that "mov is Turing-complete" [0], is it possible to
| get around the requirement that loops must be fully unrolled?
| Obviously you couldn't tell if your algorithm was finished, but
| if you could ask the key holder if the algorithm had completed or
| needed more work, you could theoretically compute any algorithm.
| What am I missing?
|
| [append] Perhaps, could you create a "fully homomorphically
| encrypted" 6502, where each application of the program
| corresponded with a single clock of the emulated microprocessor?
|
| [0] https://drwho.virtadpt.net/files/mov.pdf
| jchw wrote:
| The "mov is turing complete" thing is mostly about x86 mov
| having a lot of functionality. It can do arithmetic. The mov
| mnemonic basically encapsulates a bunch of functions (and
| opcodes), kind of like how git checkout can do at least ~3
| distinct operations depending on arguments.
|
| That said, to have unbounded loops, they either need:
|
| - A branch at the end.
|
| OR
|
| - The use of pagefaults.
|
| So even then, it's not _quite_ just the mov instruction alone.
| smasher164 wrote:
| Combinatorial circuits aren't turing complete. The novelty of
| mov being turing complete is that they were able to do
| conditional branching with just loads and stores. In the FHE
| case, they can't read and write to parts of memory, so it's a
| no-go.
|
| This is why their compiler essentially only works on pure
| functions whose inputs have a statically known size.
| bunnyswipe_com wrote:
| The future is bright
| phkahler wrote:
| Is there any way to get unencrypted data in or out? I'd like to
| feed it real-world data and get real-world data out, but not know
| the internal state.
| golol wrote:
| When I first learned about homomorphic encryption it gave me the
| idea of "cryptographic AI", as some sort of sci-fi writing
| prompt. Suppose compute is readily available to interstellar
| civilizations but actually designing a (super)intelligent AI is
| difficult. Then it could be economically feasible for
| cryptographic AI to exist. These are descriptions of AIs that run
| under homomorphic encryption, where the private key is only known
| by the AI itself. The description of the AI program and its state
| is spread throughout many locations and generally runs in a
| decentralized way. Planet earth might receive a segment of a
| cryptographic AI and make deal: Earth executes the program with
| some inputs it may choose to compute a solution to a problem. The
| program can be given inputs via a public key. The execution of
| the program can not be modified or manipulated since it is
| running under homomorphic encryption. What the AI gets in return
| is that earth provides it with additional compute that it may use
| for its own purposes. Earth furthermore allows the AI to transmit
| updated fragments of state into the stars. Over the course of
| many years, the pieces of state of the decentralized AI spread
| throughout the galaxy combine to represent the thoughts and
| actions of a singular entity. If earth modified the computations
| then the transmitted state could cryptographically be seen to not
| be valid, and hence would not be used in the decentralized galaxy
| spanning computation of the AI. Furthermore if earth cheats the
| AI in the deal then there may be consequences such as
| relativistic kinetic kill projectiles.
| MoOmer wrote:
| Put a few thousand more words to pad, and I'd read that book!
| golol wrote:
| Yea collecting sci fi ideas is fun but writing a book is
| wayyy too hard sadly ...
| addandsubtract wrote:
| There's an AI for that.
| stjnvcm wrote:
| Check out the Hyperion cantos by Dan Simmons.
| mr_alot wrote:
| That's funny, I started with Hyperion two weeks ago. I like
| it :)
| dumbfoundded wrote:
| I think cryptographic AI will become a reality. The use-case I
| was thinking is more of immortality/digitizing human
| consciousness. If you could be uploaded (like the show Upload),
| what would that actually look like?
|
| Well, plain text representation would just be too dangerous.
| Companies could mine your consciousness, duplicate it at will
| or whatever else they wanted. It's a scary thought. FHE
| provides the solution.
| parksy wrote:
| I also had a similar concept but went in a different direction,
| combining DAOs, AI, and FHE to similar ends. The idea is
| plausible, and given several orders of magnitude more energy
| and compute power, might become feasible sooner than we can
| imagine (given readily available fusion power, exponential
| increases in compute and networking capabilities, etc). Given
| the currently known physics of space travel I feel this will
| occur long before interstellar travel becomes routine so issues
| of fragmentation will be on the order of days or hours rather
| than years or millennia, and because of this I figured that the
| emergence of such a system is more likely to happen here on
| Earth than to arrive here from distant stars.
|
| Pre-general AI, what I think would happen when we get to the
| point of, say, "npm install fhe-ai-dao" (or "hey bing, make me
| a company that trades space mining resources for farm land" or
| some such thing), is a period of competition for compute cycles
| and energy, which like everything will go to the highest
| bidder, so these agents will in this scenario by the sheer
| force of survival of the fittest be refined to be self-
| sustaining for-profit, hyper-capitalist juggernauts. Human
| factors will be minimised and automation will increase, but
| these systems will serve human masters for a while as they
| become more refined and more interconnected.
|
| Assuming at some point general AI is inevitable, whether
| someone creates it, or it emerges from the general complexity
| of the interacting automated systems, various AI "minds" would
| come to "being" already in control of a fully automated
| industrial manufacturing and research network; it can by this
| point make its own choices and start operating to its own ends,
| whatever that ends up being, ultimately rendering humans
| obsolete.
|
| In this scenario, rather than a single point where someone
| creates a rebellious singularity, or an AI turns evil and
| suddenly takes control, or a hypothetical civilisation points
| its gun at us and effectively enslaves us, we will instead
| slowly give control to automated systems more over time in the
| name of efficiency, as we have done since the industrial
| revolution, and at the point where we lose control of these
| systems, we'll have neither the retained knowledge or resources
| to prevent it from doing whatever it wants to.
|
| The only way to stop it is to start now, in "the past", but is
| it too late? You'd have to shut down the internet and all
| emerging blockchain and encryption technology, and that's just
| crazy talk! So is the outcome inevitable?
| mxkopy wrote:
| This premise is very similar to the Dune prequel series. Before
| FTL travel was discovered, AI dominated the galaxy in the
| sharded manner you describe. An interesting plot point dealt
| with what happens if one of these shards doesn't merge for a
| very long time and develops its own personality.
| eru wrote:
| Alas, they are not good books.
| Trias11 wrote:
| The whole need to encrypt likely only exist within rudimental
| newborn civilizations like Earth (on a universe scale) where
| species are fighting their own for survival and growth.
| pyinstallwoes wrote:
| It sounds like a soul
| gigatexal wrote:
| This is all interesting and I'm thinking now with all the talk of
| privacy and data sovereignty etc why this is coming out or Google
| now and not Apple? Anyone know if Apple is thinking along these
| lines? Would be nice if we could get performant computation on
| things without having to decrypt our own data. Then again my
| understanding and real world applications of homomorphic
| encryption is pedestrian at best.
|
| What I do really enjoy is the author's tone and style. The
| article was fun to read and easy to follow and it seems like a
| really cool project.
| londons_explore wrote:
| The news stories you read about Google and Apple re: privacy
| are heavily influenced by corporate PR departments sending
| 'tips' to the media to try to make themselves look good or a
| competitor look bad.
|
| The actual privacy efforts of both companies don't (in my
| experience) closely align with what the news says about them.
| Uftos wrote:
| Why it's a compiler and not a library
| noman-land wrote:
| I left this comment on the blog but I'll repeat it here as well.
|
| Really interesting! Thanks for the writeup. I'd be particularly
| keen to see the example applications broken up into the two
| halves you'd expect in an actual client/server application.
|
| The adder example, while illustrative, receives cleartext inputs
| and returns cleartext outputs. In a real application the adding
| code would presumably sit on a server and there would be client
| code which just encrypts user inputs and decrypts backend
| outputs.
|
| It would be very interesting to see how one might set this all up
| with a keypair. Could the same adding code be used for multiple
| different users and keys, for example?
| yafbum wrote:
| The application domain for this stuff is so negligible... Who's
| going to pay for this huge added cost?
|
| Either the customer whose data is being handled trusts the
| service provider enough to let it handle unencrypted data, in
| which case all the data is vulnerable to interception (and the
| vast majority of data processing falls into this category)
|
| Or the customer doesn't trust the data processor to see the
| unencrypted data, their data but _still wants to delegate
| processing to it_. This is a very thin space to operate in. It
| sounds much easier to simply trust a physically separate and
| controlled computing plant instead of FHE.
| fhd2 wrote:
| I've been working in the privacy space for a few years and
| always had the same opinion. If a customer doesn't trust the
| data processor, the logical conclusion is to not send any
| sensitive data at all, which is technically possible. But it
| means more edge processing, more client side processing, most
| likely not what Google wants. But they have to do _something_,
| even if nobody uses it in the end.
| yafbum wrote:
| The practical way that people deal with this is putting a
| swarm of auditors all up in the processors' business. It used
| to be this way for telecom as well: to know whether comms
| were secure, you needed to walk the length of the cable and
| look for taps. Comms encryption has radically changed this.
| The question is, is there a similar revolution in the making
| for processing as opposed to comms. I strongly doubt the
| benefits will outweigh the drawbacks.
| jossclimb wrote:
| That's not the only trust model at play. Here is a different
| example of where FHE becomes very useful.
|
| Cancer researchers will benefit greatly from patient data sets
| that might include very privacy centric elements such as genome
| sets, past medical history (of both them and relatives to help
| understand heredity aspects of the disease). Most people making
| an informed decision may be uncomfortable with this information
| being made widely available, at best perhaps OK with a select
| few groups, but not available to anyone researching this
| domain.
|
| FHE would solve this, the data can be made available to anyone
| with compute power that wants to help, while still respecting
| the privacy of the patients.
| apple-sauce wrote:
| Are "privacy" issues are more important for people than
| "dying from cancer" issues though?
| unethical_ban wrote:
| Ugh.
|
| All things equal, privacy is usually preferred. This
| technology would allow both. Why is it either or?
| TheGeminon wrote:
| It would be useful to have control data sets as well, from
| those without cancer/illness. This is a problem in a lot of
| medical research where those affected with an ailment are
| much more likely to share data, participate in trials, and
| donate their bodies to science than healthy individuals
| are.
| OJFord wrote:
| Who is 'people'? They're not the same set, not all of
| cancer research is looking at people currently 'dying from
| cancer', nor are there going to be enough from different
| demographies declaring 'I am concerned about dying from
| cancer more than my privacy' and volunteering their data.
| And even if there were, that trait itself is probably
| skewing your data and not necessarily generalisable to
| people not (so particularly) concerned about 'dying from
| cancer'.
| edflsafoiewq wrote:
| How exactly would FHE work here?
| TheGeminon wrote:
| One example would be a project like Folding@Home but with
| much more sensitive/personal information.
|
| Organizations/universities could compute on data provided
| by a custodian organization without having to care about
| data handling.
| edflsafoiewq wrote:
| No, I mean please explain the way you would use FHE to do
| that.
| ilyt wrote:
| Or you can just have a supercomputer and run the code on the
| database, just don't distribute the whole database to the
| people writing the code. Seems far easier and cheaper
| [deleted]
| amelius wrote:
| > The application domain for this stuff is so negligible...
|
| They said the same about Rust ("it's a systems language,
| needlessly complicated for large user applications").
| radicalbyte wrote:
| It also doesn't work for GDPR as legally encrypted personal
| information is still personal information. Just because you
| can't decode it today doesn't mean that you won't be able to
| decode it tomorrow (via key leak, quantum etc etc).
| codethief wrote:
| > First, the subset of C++ supported by the compiler is rather
| small. As mentioned earlier, all data needs to have static sizes.
| This means, e.g., you can't write a program that processes
| arbitrary images. Instead, you have to pick an upper bound on the
| image size, zero-pad the image appropriately before encrypting
| it, and then write the program to operate on that image size. In
| the same vein, the integer types you choose have nontrivial
| implications on performance. To see this, replace the int type in
| the 32-bit adder with a char and inspect the resulting circuit.
|
| > Similarly, loops need static bounds on their iteration count.
| Or, more precisely, xlscc needs to be able to fully unwrap every
| loop--which permits some forms of while loops and recursion that
| provably terminate. This can cause some problem if the input code
| has loops with complex exit criteria (i.e., break's guarded by
| if/else). It also requires you to think hard about how you write
| your loops, though future work will hopefully let the compiler do
| that thinking for you.
|
| I'm wondering if Zig wouldn't be a more appropriate language
| here, given its extensive support for running code at compile
| time (which requires all involved variable values to be known)
| and its integer data types which come in any bit length (u1, u2,
| u3, ...).
| j2kun wrote:
| Admitting the possibility of having multiple frontend languages
| for the compiler is a longer term goal of mine!
| tener wrote:
| > Finally, encrypting each bit of a plaintext message comes with
| major tax on space usage. Each encryption of a single bit
| corresponds to a list of roughly 700 32-bit integers. If you want
| to encrypt a 100x100 pixel greyscale image, each pixel of which
| is an 8-bit integer (0-255), it will cost you 218 MiB to store
| all the pixels in memory. It's roughly a 20,000x overhead. For
| comparison, the music video for Rick Astley's "Never Gonna Give
| You Up" at 360p is about 9 MiB (pretty small for a 3 minute
| video!), but encrypted in FHE would be 188 GiB, which
| (generously) corresponds to 20 feature-length films at 1080p.
|
| Ouch.
| [deleted]
| noman-land wrote:
| [flagged]
| [deleted]
| e12e wrote:
| Curious if there's tooling to de/serialize the encryption
| context?
|
| The examples aren't very useful to demonstrate "real" homomorphic
| encryption in the sense that it takes in plaintext directly;
| encrypt and transforms; then decrypts - I'd love to see a snub
| that takes encrypted input (only) and returns ciphertext of the
| result - that can then be decrypted on a client node provided the
| correct key?
|
| Or is this supposed to be _only_ proof of concept?
|
| Cool stuff, either way.
| slackner wrote:
| There seem to be built-in methods for serializing and
| deserializing crypto context as well as ciphertexts [0], so it
| shouldn't be too difficult to build a "complete" example that
| performs the actual computation in a different application.
| That said, with a duration of 7 seconds for a simple addition,
| it is still far from many practical applications, in my
| opinion.
|
| [0] https://github.com/openfheorg/openfhe-
| development/blob/main/...
| touisteur wrote:
| Would that enable continuations or lightweight checkpoint
| restore? If computation takes hours or weeks you might want
| to do add some restart-ability...
| j2kun wrote:
| We have some serialization and deseralization to protos for
| internal tests. It's straightforward, and probably we'll add it
| to the compiler once we have a strong need and some more stable
| backends
| 7e wrote:
| How many orders of magnitude slower is this?
| Palomides wrote:
| author shows a program that adds two integers and takes 7
| seconds to run, and the way the system processes data results
| in 20000x the RAM usage
| willcipriano wrote:
| So similar to your average electron app.
| nevir wrote:
| Turns out Electron is SUPER SECURE
| tossaway0 wrote:
| We've complained long enough about complexity in code being
| the barrier to speed. Now it's processing power once again.
|
| I'll take it if we can rely on the security.
| barbazoo wrote:
| > I'll take it if we can rely on the security.
|
| What's a use case here? Will this one day make
| communication more secure? If so, how?
| phkahler wrote:
| My bet is on digital currency. Your wallet will be able
| to send and receive from other wallets locally. Not like
| crypto. No distributed ledger. You will make transactions
| locally. You can't just alter your balances though
| because they are encrypted. Not sure how you get data in
| or out without keys though. FHE will be a part of such
| currency though.
| xrd wrote:
| There is something surreal about the last example where you
| take a Rick Astley video that's 9MB and it becomes 188GB
| after FHE. That seems like a new category of rick-rolling by
| some cyberpunk.
| fnordpiglet wrote:
| Adding two numbers takes 7 seconds, so many many many
|
| But - it's a lot better than it has been for FHE. This is
| progress even if it seems absurd.
| TeMPOraL wrote:
| I feel it's already at the edge of being useful in practice.
| Compute and memory are cheap, and we're wasting a lot of it -
| so even with overhead this big, simple calculations wrapped
| in FHE wouldn't be prohibitively expensive - and may just be
| useful enough to create new types of software systems.
| NovemberWhiskey wrote:
| 7 seconds to add two numbers; that's roughly, what, 10
| orders of magnitude slower than without FHE? I'm not sure
| compute is _that_ cheap.
| gregschlom wrote:
| An order of magnitude order of magnitude
| fnordpiglet wrote:
| It's orders of magnitude all the way down
| unshavedyak wrote:
| It would be interesting to see a whole new generation of
| writing apps with hyper optimized code. We suddenly go
| back to the 1950s(?) in relative compute power for apps
| behind FHE.
|
| Not sure what could be done with it at 7s though hah.
| j2kun wrote:
| I probably should have added: the backends used in the post
| are 3-ish years old and missing some of the latest features.
| We're working on integrating newer backends and taking
| advantage of the new techniques! The performance story is
| better than it seems from my article. Plus this doesn't have
| any hardware acceleration, another big topic on my agenda :)
| fnordpiglet wrote:
| Great article btw
| aliqot wrote:
| Hey no need to justify it here, this is really cool! The
| first few runs are always slow and ready for optimization.
| I am very optimistic for what this tech may do for medical
| records and similar industries.
| fnordpiglet wrote:
| Yeah I've always wondered if FHE would benefit from asic
| level acceleration, or at least FPGA
| DesiLurker wrote:
| If you are going to do an asic (w/o data going to memory
| IO) then why not use regular encryption with codec on the
| SoC itself (like DRM content). that works just fine. IMO
| the main value here would be trust between unknown
| parties over untrusted medium.
| ricksunscreen wrote:
| Binary TFHE (the scheme the Google compiler uses) is fairly
| slow and has very large public keys (like 100MB). However the
| advantage is that binary computation is very flexible and
| well understood. Additionally, TFHE supports fast (~10ms)
| bootstrapping, which allows you to perform an arbitrary
| amount of computation.
|
| If you can live with the limitations of other schemes FHE can
| be much faster. On a single core of an M1 Macbook Air,
| multiplying 2 BFV encrypted 4096-bit values takes 4ms and
| adding them takes only 15us. Additionally, key sizes aren't
| horrendous (<500kB). One downside with this scheme are that
| bootstrapping takes minutes so it isn't really practical.
| This limits the amount of computation you can do before you
| exceed your noise budget and the ciphertext decrypts to
| garbage. The other downside is that arithmetic circuits make
| some computations far more difficult (e.g. comparisons).
| flangola7 wrote:
| If all you need to do is handle a symmetric key exchange that
| you then use for everything else, that might be enough.
| sillysaurusx wrote:
| This is tempting to believe, but unfortunately the dream is
| to be able to run applications on someone else's servers
| without them knowing what you're doing. That's when I lost
| interest in FHE. If you want to use it, you have to use it
| everywhere, and it's just too slow.
|
| Hopefully I'm wrong about that.
| squeaky-clean wrote:
| I'm surprised the "capitalizing a 32 character string"
| example is actually one second faster than adding two 32bit
| integers. Still super slow, but I'm curious why. I'd assume
| that if the string_cap.cc example takes 256 wires, wouldn't
| add.cc take 64 wires?
| j2kun wrote:
| Short answer: string cap has more parallelism in the
| circuit. Depth is more important than total number of
| gates, and optimizers can decrease depth pretty well.
| squeaky-clean wrote:
| Thanks (and Dylan18607). So to continue assuming, the
| number of wires specified is just the input/output, and
| the add.cc has more intermediate "wires"?
| j2kun wrote:
| It's more like: to implement add you need a ripple carry
| adder. You can't evaluate bit 6 until you've evaluated
| bits 1-5. So there's a nested dependence that makes the
| circuit deep. String cap, on the other hand, can be
| implemented in parallel by looking at pairs of characters
| independently. So that makes it into a parallel band of
| small circuits, which we can evaluate in different CPU
| cores. Also I think the capitalization operation also
| affects fewer bits of a char (it's just toggling one bit
| in each char, IIRC).
| anthk wrote:
| It's faster to carry six glasses at once than having to
| carry them to some point one by one.
| [deleted]
| Dylan16807 wrote:
| Since it encrypts one bit at a time, does capitalizing even
| have to touch the 224 bits that don't change?
|
| > wouldn't add.cc take 64 wires?
|
| Plus another hundred intermediate wires. And it's doing
| more complicated operations, however much that matters.
| squeaky-clean wrote:
| No idea lol! Though it says it works on all 32 bytes in
| parallel regardless of input size. I imagine ignoring the
| bits that don't change would be some sort of security
| vulnerability? You could probably work out some timing
| attack or entropy reduction otherwise? They state it
| should take the same duration regardless of the length of
| the input string or how much needs to be capitalized (all
| branches are executed even though many are discarded)
| Dylan16807 wrote:
| > I imagine ignoring the bits that don't change would be
| some sort of security vulnerability? You could probably
| work out some timing attack or entropy reduction
| otherwise?
|
| Nah. The bits are hardcoded into the circuit to not
| change. That's part of the program, and the program is
| public information. Only bit 6 of each byte might change,
| and everyone knows it.
| nabla9 wrote:
| > It's roughly a 20,000x overhead.
|
| Would this be a realistic use case?
|
| A wants to send 256 bit message (M) to B.
|
| B sends already encrypted 256-bit AES key (K) to A.
|
| A can use encrypted K to encrypt M and send it to B without
| knowing K.
|
| (essentially public key symmetric key)
| fnordpiglet wrote:
| Someone needs to make a crypto network that runs submitted FHE
| programs as proof of work.
| jossclimb wrote:
| Someone needs to make FHE run at speeds greater than an Abacus
| machine first.
| __MatrixMan__ wrote:
| What's to stop somebody who knows the cleartext (because they
| submitted the job) from cheating?
| fnordpiglet wrote:
| They would presumably pay for the computations on the network
| (by paying gas). The output would be still encrypted with the
| FHE public key and can be signed. Having the clear text is
| the same as having the private key. How would someone cheat?
| I'll admit I'm no crypto nerd but I'm not sure how you would
| cheat.
| friend_and_foe wrote:
| They'd pay themselves for computation on the network? You
| can't see a game theoretical problem with this?
|
| If simply encrencrypting the output is less work than
| running the computation on the ciphertext input, they'll do
| that and publish the encrypted output as proof. This would
| mean alliners would up bid for the computation because they
| know that if their computation becomes the limiting factor
| in block creation they can beat everyone else to it.
|
| There's also the problem of benefitting from mining. Mining
| _has to_ only be useful in that it is used to construct
| blocks, if it is useful for any other purpose whatsoever,
| whoever benefits from that purpose has an opportunity to
| mine at lower marginal cost than other miners.
| cfuendev wrote:
| Am I the only one who read this as "Google's fully homophobic
| encryption compiler"?
| Aachen wrote:
| As the old logicians joke (https://www.barrypopik.com/index.php
| /new_york_city/entry/thr...) goes: I don't know.
___________________________________________________________________
(page generated 2023-02-14 23:02 UTC)