Score:1

Generate asymmetric key pairs based on keywords such that any public key based on set containing the generating subset is valid

tk flag
Fly

Let's assume we have a ton of users, and each user has a list of fruits they like - Those will be keywords. I want my users to be able to encode any data they store (Let's say, the location of their favorite fruit trees), as well as decode it: Therefore, I want to be able to generate a public/private key pair based on their specific keyword list.

This also implies that any user with the same keyword list should be able to access the data that was previously encoded. However, I'd like to take this a step further: I want all users, that have a keyword list which contains the keyword list used to encode data as a subset, to also have access to that encoded data.

In my example, this would mean the following: All people that like the same fruits or more as someone else should be able to decode the fruit tree locations of that person.

In essence, I want my key pairs to somehow encapsulate each other: A public key generated by a certain keyword list should be able to match all private keys generated by any subset of that keyword list.

Unfortunately, I'm no expert in the field of cryptography, so I was wondering: Does anyone know how I can achieve key pair generation with the properties described above?

Thanks!

knaccc avatar
es flag
Must the server have zero visibility on which fruits anyone likes? Or is the server allowed to know the fruits each person likes, but just not the encrypted data for that list? And is anything preventing someone from just adding all possible fruits so they can have access to everything? Is the list of all possible fruits a secret? Can anyone like any fruit, or must they be allowed "access" to like a fruit? And what if the server just creates a user account that likes all possible fruits to see all data?
tk flag
Fly
@knaccc The server knows (and, actually, even stores it unencoded) exactly who likes which fruits. The rest of your questions are definitely relevant for the actual usecases of such a system, but I think shouldn't impact the key generation algorithm itself; but in my case, only someone who likes a specific fruit can let someone else know that this fruit exists, in which case they are then allowed to like it. A user account who likes all fruit is basically a master-account, who then indeed has access to all data.
knaccc avatar
es flag
It sounds like the server will have access to the list of all possible fruits, and so can then easily decrypt and view any information that any user has stored. So what's the point of anyone having a key pair and doing any encryption, if the server can see everything anyway?
tk flag
Fly
@knaccc Well, database leaks would not yield any data due to the encryption.
knaccc avatar
es flag
If the server can see all data, then a server compromise will leak all data. You could encrypt the entire database at rest with ordinary symmetric encryption, and that would be equivalent to what you're proposing. The only way that an elaborate encryption scheme like the one you're proposing would make sense is if it was done such that the server admin could not have visibility over any data, because only the users would have the private keys in order to decrypt the data.
cn flag
Basically, you are describing is called [attribute-based encryption](https://en.wikipedia.org/wiki/Attribute-based_encryption).
Score:1
es flag

A fruit will be created by a user, and will assign it a secret key $x$. The user will inform the server about the existence of this fruit, identifying it only by a label, and keeping $x$ secret.

All users have their own personal EC key pairs, where their personal secret key is not disclosed to the server. When someone is invited to like a fruit, an invitation will encrypt the secret key of that fruit $x$ with the invitee's personal public key in order to communicate it to them.

When a user wants to encrypt information only visible to users that know the secret keys for a set of fruits whose secret keys are $\{x_1 , x_2 , x_3\}$, the user simply encrypts it using symmetric AEAD encryption with the secret key $H(x_1 | x_2 | x_3)$, where $H$ is a cryptographically secure hash construction immune to length extension attacks. Lists of fruit secret keys should always be concatenated in their lexicographical order. The user will label the encrypted data so that others know which subset of keys they will need to decrypt it. The user may wish to sign the data they've encrypted with their personal public key.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.