Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Google’s fully homomorphic encryption compiler – a primer

jeremykun.com

Post reply on HN
Print view View original

151–160 of 168 posts

Re: Google’s fully homomorphic encryption compiler – a primer

#151

Post by heartbeats »

noduerme wrote: post #85
fatneckbeard wrote: post #82

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 an…

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 c…

> What would be sort of awesome, though, would be a distributed bank (or prediction market, or casino) along these lines

I think this is already possible for poker, and will never be possible for prediction markets.

Prediction markets require human resolution of "fuzzy" questions. For example, who won the 2020 US presidential election? You can see why the limiting factor isn't the machine.

But for poker, why do you need FHE? To play poker, you have to deal two hole cards and five community cards. First each player gets two secret ("hole") cards, then three community cards are dealt ("flop"), then potentially another ("turn"), then potentially another ("river"). This could be done programmatically as such:

1. Each player generates five secrets: k_HOLE, HOLE, FLOP, TURN, RIVER

2. Each player derives public key K_HOLE from k_HOLE.

3. Each player publishes the hash of each secret in addition to K_HOLE.

4. Each player publishes their value of HOLE, which is checked against the hash from previous step.

5. To get the two hole cards for you, calculate H(HOLE_1 || HOLE_2 || ... || HOLE_N), decrypt the resulting value using k_HOLE (secret to you), then deterministically turn this into cards (for example: hash it, then map the first half into 52 values and the second half into 51 values)

6. Once it's time for the flop, all players publish FLOP. Then calculate H(FLOP_1 || FLOP_2 || ... || FLOP_N).

7. Repeat for turn and river as necessary.

The only difficult part is how to handle colors, but I don't think this is a serious issue, since nobody counts cards in poker anyway. (We can trivially ensure flop, turn and river don't repeat cards, so it's just a question for the hole cards vis-a-vis the community cards)

EDIT: Looks like someone has already tried to do this seven years ago: https://github.com/zweicoder/PokerPhase

Re: Google’s fully homomorphic encryption compiler – a primer

#152

Post by noduerme »

heartbeats wrote: post #151
noduerme wrote: post #85

Earlier quoted context omitted.

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 c…

> What would be sort of awesome, though, would be a distributed bank (or prediction market, or casino) along these lines I think this is already possible for poker, and will never be possible for prediction markets. Prediction markets require human resolution of "fuzzy" questions. For example, who won the 2020 US presidential election? You can see why the limiting factor isn't the machine. But for poker, why do you n…

Given a pair of hole cards and a hash from a server for everything else, you can do this. But a fair poker hand is dealt from a truly randomized deck. Some central server needs to be the arbiter of randomness (not to mention being the actual escrow service for the money in the pot -- which is the other service provided by prediction markets besides deciding how to resolve bets). Those things - randomness, arbitration and escrow - still can't be completely devolved to client-side processing, or at least not without recourse to ludicrous hacks like public ledgers (aka blockchains) which still run the risk of 51% attacks.

Encrypt the whole VM and all i/o on each client though, so that the machine state itself is encrypted at all times, and you can trust their generation of the hole cards (as far as you can trust a PRNG).

Under this new paradigm, though, the power over the systems probably goes to some new certificate authority that doubles as a routing (signaling) service.

Re: Google’s fully homomorphic encryption compiler – a primer

#153

Post by noduerme »

esperent wrote: post #116
fatneckbeard wrote: post #82

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 an…

What purpose would this serve? Just anonymity for the sake of anonymity, or something else?

Seems a fair question. In a private banking context, it would potentially eliminate the need to pay escrow fees to a third party, without resorting to massively inefficient public ledgers. In the context of e.g. stock trading, it might mean that a traditional bank can connect buyers and sellers over a peer to peer connection and guarantee that their trades execute in order without even needing a centralized book. That's maybe a slightly extreme take, and probably a ways off. But I think anonymity is the least important of what becomes available if you can trust client-side processing.

Re: Google’s fully homomorphic encryption compiler – a primer

#154

Post by heartbeats »

noduerme wrote: post #152
heartbeats wrote: post #151

Earlier quoted context omitted.

> What would be sort of awesome, though, would be a distributed bank (or prediction market, or casino) along these lines I think this is already possible for poker, and will never be possible for prediction markets. Prediction markets require human resolution of "fuzzy" questions. For example, who won the 2020 US presidential election? You can see why the limiting factor isn't the machine. But for poker, why do you n…

Given a pair of hole cards and a hash from a server for everything else, you can do this. But a fair poker hand is dealt from a truly randomized deck. Some central server needs to be the arbiter of randomness (not to mention being the actual escrow service for the money in the pot -- which is the other service provided by prediction markets besides deciding how to resolve bets). Those things - randomness, arbitration…

> Some central server needs to be the arbiter of randomness

What, no? My hash-based system is entirely random. The only issue is that draws are done with replacement, so two players may both have e.g. six of spades in their hand. This is aesthetically unappealing, but doesn't alter the actual maths of the game. (There are more complex solutions to this, however)

> not to mention being the actual escrow service for the money in the pot

FHE doesn't solve this, since FHE can't actually interface with your bank. Even if it could, I could just log in on my phone or physically walk into a bank branch to freeze my account before I have to pay out, so you still need a solution for the money layer.

> you can trust their generation of the hole cards

You can do trustless generation of hole cards already, as described in my post.

Re: Google’s fully homomorphic encryption compiler – a primer

#155

Post by MoOmer »

stjnvcm wrote: post #115
MoOmer wrote: post #98

Earlier quoted context omitted.

Put a few thousand more words to pad, and I’d read that book!

Check out the Hyperion cantos by Dan Simmons.

I've got the audio book but never gave it a fair shot, maybe the text is what I need. Will grab it from the library!

Re: Google’s fully homomorphic encryption compiler – a primer

#156

Post by DesiLurker »

fnordpiglet wrote: post #146
DesiLurker wrote: post #140

Earlier quoted context omitted.

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.

The typical perceived use case is FHE in cloud providers providing highly sensitive compute in a multi tenant platform. In something like that full on hardware acceleration is key

just noticed the response..

Not really, even in those cases you need to understand that bits in memory (ie.. everything past (&including) the SoC's IO pins would never see the data unencrypted. any decryption is handled within working cache on soc with secure context (typically on a secure OS vm). I dont see why a bunch of compute code wont work there. in fact you could go a step further and encrypt compute instructions too. then assuming you know what you are doing and dont crash the compute node will have no idea what ops you are actually doing on what data.

btw thats how DRM works (sans the last part).

Re: Google’s fully homomorphic encryption compiler – a primer

#157

Post by squeaky-clean »

Dylan16807 wrote: post #66
squeaky-clean wrote: post #63

Earlier quoted context omitted.

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 t…

> 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.

Whoa, I never knew about the ascii 6th bit trick, I've never really considered capitalization wasn't some random offset. So that does make this circuit simpler than I thought it was, and there's the parallelism aspect. It's not so surprising now that it's faster than the add.

Re: Google’s fully homomorphic encryption compiler – a primer

#158

Post by fatneckbeard »

CraigJPerry wrote: post #114
piaste wrote: post #113

Earlier quoted context omitted.

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.

>> 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...

but once the bank has made the loans, it has to keep track of how many it has made and how many are delinquent. i could be missing something.

Re: Google’s fully homomorphic encryption compiler – a primer

#159

Post by squeaky-clean »

j2kun wrote: post #134
squeaky-clean wrote: post #61

Earlier quoted context omitted.

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"?

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 capital…

That makes perfect sense, thank you! I also didn't know until today that capitalization in ascii is just the 6th bit. I thought it would have been doing 32 subtract operations. (I'll be honest I haven't written my own uppercase function since school haha)

Re: Google’s fully homomorphic encryption compiler – a primer

#160

Post by fatneckbeard »

esperent wrote: post #116
fatneckbeard wrote: post #82

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 an…

What purpose would this serve? Just anonymity for the sake of anonymity, or something else?

its basically a thought experiment.

one of the things i never understood about bitcoin was the idea of the public ledger. one of the main things about most people and businesses in general is that they do not want to draw attention to their actual flows of money. the idea everyone would want their entire purchase and payment history "out there" in public never made sense to me.

but if you could actually make bitcoin anonymous, then what would happen? would it be adopted more? or would the government actually have to crack down?

Post reply on HN