Privacy in Tents: a discussion of private solving strategies

Solver Shenanigans
1

A place to discuss

6 Likes
2

Hi @vveiln

Thanks for sharing your thoughts on private intent solving.

While considering FHE for private solving the article mentions that as a solver can also be a user the solver could produce an intent such as on encrypting it’s data it matches with some other intent already exist in the mempool. And hence it will reveal the user intent.

Isn’t this scenario would be very rare considering the encryption function operates on a very large domain and the outputs produce by it differs largely among each others.

1 Like
3

Good question!

Such system would not be considered secure in theory, but if we can prove that the computational effort required to uncover intents is too high, then it might be safe enough in practice.

UPD: another thing is that the solver might not actually want to guess the exact intent, and learning some information is muuch easier

But I feel like with FHE it is only the tip of the iceberg, and there are many other problems to solve even if we don’t take into account the current state of FHE (slow) and imagine it is fast enough to be used today (without any footnotes involved):

  • what about the decryption keys? If we imagine a system where each user encrypts their intent, they need to use the same key to have the encrypted intents compatible and use threshold cryptography to decrypt the result (the output can only be decrypted when a set of parties holding the decryption key shares with the number of participants above the threshold communicates to do so), which sounds like a workable solution but requires more examination. It might also happen that such a combination of FHE with MPC will not actually win over a pure MPC protocol (it will require less communication, but might end up being too slow anyway). There is a lot of handwaving involved in this, but even without proper estimations and more formal reasoning it is not more handwavy than the argument for FHE
  • how do you validate user input? we were kind of imagining that users are good guys, but what if they are not and they just submit garbage intents to keep solvers busy? One way to validate the input would be to use ZKPs. That is cool that we can solve this problem at all, but also not cool - to make FHE work we have to wrap it in more crypto

So in the end we have the tower of crypto built from FHE for computations, MPC for the keys, ZKP for validation, and overlapping crypto for combining C/D privacy with settlement privacy. Now, I don’t have the exact numbers, but it sounds expensive

But going back to reality, FHE is not ready yet and it is hard to predict what will happen by the time it is ready. Maybe we will make MPC and ZKP cheap enough that all of it combined will provide the security guarantees we want and actually be fast enough to be used. Or maybe we will come up with some new cryptoprimitive that will solve some or all of our problems, but I feel like we definitely don’t want to blindly believe in the FHE magic, we need to think more about the problems that need to be solved to make FHE actually practical

2 Likes
4

@vveiln – on your point about decryption keys – this is an active area of research we are working on at Puzzle

There’s been a lot of recent work in MKHE (multi-key homomorphic encryption) that negates that entire point

With MKHE – you can create a system with intents encrypted to different individual user keys, run some FHE computation on those differently encrypted items, and then allow the data to be decrypted by each individual user’s keys

A Simple Ex: Credit Score Modeling → Updating user’s insurance payments

Let’s say you are an insurance agency that services 100 different people and you give a custom rate per person that depends on three things:

  1. Individual person risk profile
  2. Aggregate portfolio risk profile
  3. Past portfolio performance

Let’s say you are at the end of term for 2023 insurance, and you now need to update everyone’s terms to decide their price for their 2024 insurance. With MKHE here – you could:

  1. Each individual user encrypts their health data from the prior year and sends to you and creates a base price for each user: enc(x)
  2. You run MKHE on all the aggregate user health data to determine a portfolio risk profile based on the aggregate of all user health data: enc(y)
  3. You see whether you made loss or profit last year based on this algorithm, and you adjust by some Z’ accordingly

Now you have a table of enc(x) and you add enc(y) to each user so they get enc(z). With MKHE, user’s can then decrypt that Z and add that factor Z’ to get their updated rate.

This still runs risk of validating user input as the insurance company could add more users to run it up, but this can be mitigated with some provenance and attestations using ZKPs.

Last but not least – FHE is getting fast enough to be tenable from when we’ve played with it, and there’s a few folks working on FPGA. MKHE isn’t there yet by any means – it’s truly the cutting of cutting edge. The other issue is that FHExZK is still getting to the forefront. Sunscreen will be ready to play with by end of Q4 that will combine both so we’ll get to see then. They are working on FPGA speed ups as well.

My intuition is that this may make it tenable :slight_smile:

1 Like
5

Thanks for your comment, I def will check MKHE out!

A couple of thoughts:

There’s been a lot of recent work in MKHE

What is the difference in efficiency compared to “simple” FHE?

then allow the data to be decrypted by each individual user’s keys

So the data to be decrypted is a shielded transaction that has to be decrypted to settle → essentially an interactive protocol that requires users to decrypt the transaction as a part of the protocol. Not saying it is bad (MPC protocols involve even more active communication, and generally the question of tx decryption is something to be specified), but something to keep in mind

Credit Score Modeling → Updating user’s insurance payments

So this can essentially be boiled down to a simple algorithm like (written in fake typed python):

def f([enc_x[i] for i in users]):
    agg = proc(enc_x[i])
    return agg

Health data can be pre-processed and turned into a list of simplified parameters before encryption, then it gets encrypted and the encrypted aggregation part is minimal.

Intents can also be simple data structures, but we can’t do simple aggregation when encrypted because there is inter-intent dependency (we can’t figure out if an intent can be included in a transaction without comparing it to other intents, and considering the uncertainty encoded in intents we can’t simplify them too much either) and phase privacy overlap (we need to produce shielded output)

And let’s not forget about the primary issue - we still need to prove that it is way too hard for the solver to try to decrypt encrypted intents. The solver’s intent doesn’t even have to be precise, coming from a veery generic intent “I want whatever amount of whatever” the solver can slowly make it more specific. They don’t have to see the exact intent in the end, but knowing that someone wants, let’s say, some amount of cocaine for some price might be good enough information to uncover

6

What is the difference in efficiency compared to “simple” FHE?

Not good rn – especially bc scales with # of keys. But promising because rapid improvements over past 2 years! First real scheme purposely proposed for it was in 2021 iirc.

Video here: https://www.youtube.com/watch?v=Wrdr79G32KY&list=PLnbmMskCVh1ei6AkXHDTAefkGZaBmtUQO&index=9

So the data to be decrypted is a shielded transaction that has to be decrypted to settle → essentially an interactive protocol that requires users to decrypt the transaction as a part of the protocol. Not saying it is bad (MPC protocols involve even more active communication, and generally the question of tx decryption is something to be specified), but something to keep in mind

Geezum – great point – wasn’t thinking about next step of ZKP if there was a match. MKHE work has been focused on analysis of data in aggregate thus far. This feels like if you’d want non-interactiveness, you’d need a ZKP execution op on FHE enc data which feels like magic and something I haven’t seen yet lol.

Like if the flow for non-interactivity with user would be:
0. User sends encrypted intent to pool

  1. Analysis of data in aggregate: FHE Private Intersection Match
    → Match found: enc_x[m1] and enc_y[m2]

  2. Execute note exec op:
    enc_x[m1_input_note] & enc_y[m2_input_note] →
    enc_x[m1’_output_note] + enc_x[m1_null]
    & enc_y[m2’_output_note] + enc_y[m2_null]

  3. Execute ZKP op on #2: Proof(exec_trace)
    → Distribute Tx Outputs:
    enc_x[m1’_output_note] + enc_x[m1_null]
    & enc_y[m2’_output_note] + enc_y[m2_null]

  • proof
  1. User x scans for transaction
    → Tx found:
    enc_x[m1’_output_note] + enc_x[m1_null]
    & enc_y[m2’_output_note] + enc_y[m2_null]
  • proof
  1. User x decrypts txn:
    enc_x[m1’_output_note] + enc_x[m1_null]
    & enc_y[m2’_output_note] + enc_y[m2_null]
  • proof
    → m1’_output_note + m1_null
    & enc_y[m2’_output_note] + enc_y[m2_null]
  • proof

It feels like that step #3 doesn’t exist. Sunscreen (& Zama) work on FHE+ZK but to my knowledge, their work wouldn’t encompass a scheme needed like in #3. The proof in #3 would require inputs have valid auths, they are valid state, a valid execution, and valid state transition in order to have the verification you’d want by network to quickly verify and accept the new notes. Perhaps this is something that you can split up such that the proof requires less. May be room to play there.

The work I’ve seen isn’t this intense – but great video here to give you an idea: https://www.youtube.com/watch?v=8bVHYi7avCU&list=PLnbmMskCVh1ei6AkXHDTAefkGZaBmtUQO&index=10

Intents can also be simple data structures, but we can’t do simple aggregation when encrypted because there is inter-intent dependency (we can’t figure out if an intent can be included in a transaction without comparing it to other intents, and considering the uncertainty encoded in intents we can’t simplify them too much either) and phase privacy overlap (we need to produce shielded output)

I’d imagine that this would be up to solver right? Doesn’t this depend on solver strategy? Different solvers may have different aggregation strategies they try?

And let’s not forget about the primary issue - we still need to prove that it is way too hard for the solver to try to decrypt encrypted intents. The solver’s intent doesn’t even have to be precise, coming from a veery generic intent “I want whatever amount of whatever” the solver can slowly make it more specific. They don’t have to see the exact intent in the end, but knowing that someone wants, let’s say, some amount of cocaine for some price might be good enough information to uncover

In a hypothetical MKHE+ZK world as outlined above, all the intents in the pool are encrypted to various keys – the solver gains no information about who owns the intents or the contents.

For a solver to attack it this way to guess the contents – it seems like they’d have to pull the intent pool, rapidly simulate intent matching against their guesses to uncover a match, they find a match enc_x[m1] and propose enc_y[m2] before any other solver finds a match or completes a match.

They still don’t know who owns it, but they now understand what they’re looking for. Let’s say someone is trying to buy an NFT – now they can bid a bit higher and get it for instance – that’s not idea.

However in this case, the problem feels much more like a sybil attack problem than an encryption problem imo.
→ If it’s too slow or costly a strategy for a solver to spam to try to match encrypted transactions, then that could be an option to take care of that.
→ Or maybe it’s a threshold encrypted intent pool that’s like a commit-reveal scheme to limit intents in pool – ie building up pool from t->t+1 with each user encrypting their intent to the solver network key. Then at t+2, a pool snapshot is taken and the solver network decrypts the pool, then it’s a race to solve that. Penalize/invalidate any transactions with intents not in that pool’s snapshot. Solver’s can run their simulations then and potentially propose intents in the next pool’s snapshot. Assuming diverse solvers, it may be safer to assume that the person’s NFT doesn’t get sniped by a simulating solver because intent pool is locked in.

7

The need for ZKP inside FHE can be reduced if the solving strategy doesn’t require creating new partial transactions, which only happens when the intents match exactly (I want X for price Y and someone offers X for price Y). It might work for NFT exchange, for example, but for fungible tokens this sounds extremely constrained - no adjustment possible.

For example, if you want to specify a price range (I want X for 5-10Y), you need partial transactions: you deposit 10Y, the solver finds a match for, say, 7Y, and sends 3Y back to you, which requires partial transactions, and partial transactions require ZKP.

For a solver to attack it this way to guess the contents – it seems like they’d have to pull the intent pool, rapidly simulate intent matching against their guesses to uncover a match, they find a match enc_x[m1] and propose enc_y[m2] before any other solver finds a match or completes a match.

They can get a user intent from the pool, having their test intent prepared in advance, and just see if the test intent and the user intent match. They don’t need to propose a transaction if the goal is just to learn, but if they do want to execute, it is not something we want to prevent. We want to prevent the situation when the solver just learns the preference of the user, but acting as a user themselves is fine. Solvers are valid users

Also, the competition between solvers would not be any special compared to the “honest” case, if anything it is better for the solver because their intent is ready to be executed and other solvers might need to search for a matching intent

They still don’t know who owns it, but they now understand what they’re looking for.

I think this also depends on the exact application. Users don’t have to reveal their identities, but some applications might ask for that, which is fine, this is up to the application. For such application, the risks seem to be unacceptable

If it’s too slow or costly a strategy for a solver to spam to try to match encrypted transactions, then that could be an option to take care of that.

I don’t think it can be too slow, because this kind of spamming has exactly the same mechanics as the solvers’ main job - it is just matching intents. But instead of matching random users’ intents together, they can try matching some user intent with their test intents, prepared in advance in a smart “binary search” way to efficiently test the user intent

then it’s a race to solve that. Penalize/invalidate any transactions with intents not in that pool’s snapshot.

Racing is good, but it doesn’t help when the solver doesn’t try to win it, they can just test stuff locally without revealing the results of their computations

1 Like
8

Pretty interesting!

With MKHE – you can create a system with intents encrypted to different individual user keys, run some FHE computation on those differently encrypted items, and then allow the data to be decrypted by each individual user’s keys

A basic query.

let’s say I have data d1, d2, and d3 and keys k1, k2, and k3 where MKHEFn is an encryption function which returns cipher text and takes in data and key.

c1 = MKHEFn(d1, k1)
c2 = MKHEFn(d2, k2)
c3 = MKHEFn(d3, k3)

Doing some processing over cipher text using function PROCESSfn.

processedResult = PROCESSfn(c1, c2, c3);

Now which key or combination of keys i can use to decrypt the processedResult ? Like in FHE i can use the initial key which i used for encryption of plain text at the first place to decrypt the processed result.

Thanks in Advance.

2 Likes