Generating a similar key-share for multiple users

[JDugueperouxPEReN]

Would it be possible to add the possibility for several users to use the same partial key when encrypting an object?

Currently, the scheme allows users to encrypt a piece of data D with a given key K, while generating random partial keys K_user, allowing decryption only if a quorum of partial keys are met.
The key K is random but depends on the data D (with two methods for generating random from D), so that all users having the same D will encrypt using the same key K.
However, to the best of my knowledge, partial keys K_user are fully random, and cannot be generated through the same process as K (meaning : having K_user random but deterministically depending on D).
Ideally, I hope one user could generate a key-share for data D, using D' as a seed.

Use-case:
Using a deterministic K_user would allow various forms of bootstrapping.
For instance, it would be possible to imagine a scheme where several quorums are required to decrypt a given information.
More concretely, my use-case can be modeled in a grid with several depth levels, the smaller the cell, the more precise (and identifying) the data.
Let's take a 2-2 grid for instance.

|----+----|
| A1 | B1 |
|----+----|
| C1 | D1 |
|----+----|

To simplify, we could say that X-axis is age, and Y-axis is weight : "A1" is more precise than "1".

I wish to reach some form of k-anonymity (let say 10-anonymity).

Currently, it would be possible to make all users encrypt their data at a given grain, so that data is decrypted only if a quorum k is met. However, if the grid itself is known by the attacker, they could deduce the number of people matching the last undecrypted cell.
For instance, if the quorum is met for all A1, B1 and C1, then i can safely deduce than undecrypted values all fall within D1: k-anonymity is broken.

To prevent that, I would like to use a bootstrapping scheme.
Instead of people in A1 encrypted A1 with a key depending solely on A1, and a fully random key-share, I would like them to make the following.
First, they encrypt A1 using a key depending on 1 only. We fix that the quorum of partial key required is 4 (because there are 4 cells in 1)
They also generate a key-share for this key, but this key-share would depend on A1, and would not be sent directly.
Then, they encrypt this key using a more standard scheme, with a key depending on A1, and a fully random key-share. We say the required quorum of partial keys is 10, for 10-anonymity.
Finally, they send this random key-share.

In short, they send the following:
Encrypted [A1] with [key_depending_on_1] → quorum 4
Encrypted [key-share_depending_on_1, generated using A1 as seed] with [key_depending_on_A1] → quorum 10
key-share_depending_on_A1, generated randomly

What we obtain by doing this is that the server will be able to do the following:

• when they receive at least 10 messages from A1, they will be able to decrypt an other partial key : key_share_depending_on_1. However, as A1 was used as a seed, all key-share are identical, and they don't allow further decryption.
• when they decrypt 4 partial keys (meaning there are 10 people in all A1, B1, C1, D1), they will be able to decrypt all the data together.

Note that this scheme could be possible to extend for recursive structures / precision in a larger sense, and I'm pretty sure this kind of bootstrapping would allow more diverse uses too.

The key issue here is the generation of the key-share depending on a given seed (hopefully compatible with PPOPRF protocol), which doesn't seem to be implemented.

Would it be possible to add this as a possibility? (not as a default obviously)

Eager to discuss any details or issues with my proposition if you want.

[rillian]

@claucece do you have a comment here?