Howdy #cryptography friends,
Let's say I have 1000 friends (haha, I know, right?) and I want to send each of them a number. If I put all the numbers into a list and send the list to all my friends, that sort of works, but each friend won't know which number is theirs.
So I'd like some way to tag each number in the list so each friend can quickly tell which number is theirs, but no one else can. ie, something faster than linear time search through the list would be ideal, but I'd settle for something linear if the constants are small. Maybe something like string equality as the match operation, but not a decryption.
And if someone who isn't my friend sees the list with all the tagged numbers, they shouldn't be able to tell who any of my friends are by using the tags somehow.
Me and all my 1000 friends (lol, it's still funny) all have asymmetric keypairs, so we can use those.
Is this a well-studied problem that has a name I don't know about yet? Maybe there are special-purpose tools that are a good fit for this?
Or maybe there's some clever scheme using encryption that solves this? I feel like a deterministic encryption of some well-known message for each friend gets pretty close. Then add a list-level nonce to make it randomized for each list, but not each friend. Then a friend can do the deterministic encryption using the nonce and scan through the list pretty quickly to find their number. But my asymmetric encryption primitive is randomized, so I can't quite make it work that way unless I use a different primitive.
Although, if the message to be encrypted deterministically is well-known, and the goal is not actually to protect the message, that kind of suggests encryption is the wrong tool here. I'm looking for some kind of tag that is only recognizable by the holder of the private key.
Thoughts?
Jeff Martin /
npub1fv…wm20t
2023-07-03 15:22:43
Author Public Key
npub1fvr2n9j4qek28cdpnmxyh4w9l4ws7yr2xxdge7eug99al70p0snspwm20tSeen on
wss://relay.noswhere.comPublished at
2023-07-03 15:22:43Event JSON
{
"id": "bee032f30688209718531e0a90c7bf0f5261862992244f49286ce6c327a9aae3",
"pubkey": "4b06a99655066ca3e1a19ecc4bd5c5fd5d0f106a319a8cfb3c414bdff9e17c27",
"created_at": 1688397763,
"kind": 1,
"tags": [
[
"t",
"cryptography"
],
[
"mostr",
"https://gladtech.social/users/cuchaz/statuses/110650835819882064"
]
],
"content": "Howdy #cryptography friends,\n\nLet's say I have 1000 friends (haha, I know, right?) and I want to send each of them a number. If I put all the numbers into a list and send the list to all my friends, that sort of works, but each friend won't know which number is theirs.\n\nSo I'd like some way to tag each number in the list so each friend can quickly tell which number is theirs, but no one else can. ie, something faster than linear time search through the list would be ideal, but I'd settle for something linear if the constants are small. Maybe something like string equality as the match operation, but not a decryption.\n\nAnd if someone who isn't my friend sees the list with all the tagged numbers, they shouldn't be able to tell who any of my friends are by using the tags somehow.\n\nMe and all my 1000 friends (lol, it's still funny) all have asymmetric keypairs, so we can use those.\n\nIs this a well-studied problem that has a name I don't know about yet? Maybe there are special-purpose tools that are a good fit for this?\n\nOr maybe there's some clever scheme using encryption that solves this? I feel like a deterministic encryption of some well-known message for each friend gets pretty close. Then add a list-level nonce to make it randomized for each list, but not each friend. Then a friend can do the deterministic encryption using the nonce and scan through the list pretty quickly to find their number. But my asymmetric encryption primitive is randomized, so I can't quite make it work that way unless I use a different primitive.\n\nAlthough, if the message to be encrypted deterministically is well-known, and the goal is not actually to protect the message, that kind of suggests encryption is the wrong tool here. I'm looking for some kind of tag that is only recognizable by the holder of the private key.\n\nThoughts?",
"sig": "ae9b8315978e7016f62bcbbe5ebc725ce346057ee2c1c5f3133bcd1a32cf1dc6c564c4b22f808e918c0bef36e056cd5047cfb4689d6a18e0b0ea28c9a7fadf9a"
}