Score:1

Crypto

Do there exist cryptographic algorithm where secret key holder can distinguish ciphertext corresponding to without decrypting?

Tsiao Wang

2/18/24, 1:35 PM

I am looking for some cryptographic algorithms suit to the below usage scenario.

$A$ has a set of data, e.g., $\{x_1,x_2,...,x_n\}$. $A$ publish those data in ciphertext (maybe that they are encrypted by different public key, I do not know).

Then participants $\{P_1,P_2,...,P_m\}$ come to pick the data belonging to them from ciphertext list, but without decrypting all the encrypted data. "belonging to them" maybe correspond to their secret key.

In a naive approach, the sender $A$ encrypts data using a different receipt's key (public or symmetric key). Then each receiver uses its key to decrypt ciphertext one by one, such that the receiver can pick the data belonging to it. However, this approach has $N$ decryption operations, which could be faster.

In other words, does there exists an algorithm? Using it, we can distinguish which ciphertext belongs to our key without decrypting every ciphertext one by one.

Does anyone know a cryptographic algorithm that addresses on above problem? Or some related keyword for me to search paper.

1 + 3

knaccc

2/18/24, 2:06 PM

I assume you need to ensure that nobody other than the intended recipient of each piece of data can tell that the encrypted data is destined for them. You can encrypt an identifier with a symmetric key known both to the sender and recipient. Or, you can use the approach Monero uses, which is to encrypt an identifier using the Diffie-Hellman shared secret between an ephemeral public key attached to the data and the recipient's public key.

poncho

2/18/24, 2:23 PM

What are you trying to avoid by the insistence on "without decrypting"? Are you looking for a search that is faster than the full decryption method? Or, is it somehow important that the checker is unable to obtain the plaintext (even though, if he holds the private key, he can if he wants to)?

Tsiao Wang

2/19/24, 1:38 AM

Hi @poncho, there is a list of ciphertext. The receipt's objective is to identify which ciphertext is encrypted for her/him. "without decrypting" means that the key holder or receipt is not required to decrypt each ciphertext one by one.

Score:2

Crypto

Zhun

2/18/24, 2:30 PM

The scenario you described is known as searchable encryption, where a data owner encrypts their data and publishes it in the cloud, and authorized users can search and retrieve specific data items without revealing their identities to the cloud.

There are several cryptographic techniques that can be used for searchable encryption, such as symmetric-key based techniques like Bloom filters or hash-based indexes, and asymmetric-key based techniques like Public Key Encryption with Keyword Search (PEKS) or Identity-Based Encryption (IBE).

In your scenario, it seems like you are looking for an asymmetric-key based technique where data is encrypted with different public keys, and authorized users can retrieve their data items using their private keys. In this case, you may want to explore Identity-Based Encryption (IBE) or Attribute-Based Encryption (ABE) schemes.

IBE and ABE are both types of public-key encryption where users are identified by their attributes or identities rather than traditional public keys. In IBE, the user's identity serves as their public key, while in ABE, users are assigned attributes, and access policies specify which attributes are required to access specific data. Both IBE and ABE allow for fine-grained access control and efficient search capabilities, making them suitable for searchable encryption scenarios like yours.

You may also want to explore the following papers for more information on searchable encryption techniques:

"Public Key Encryption with Keyword Search" by Dan Boneh and Giovanni Di Crescenzo
"A Survey of Searchable Encryption Techniques" by Reza Reyhanitabar, Amirreza Rezvanian, and Majid Naderi
"Attribute-Based Encryption for Fine-Grained Access Control of Encrypted Data" by Amit Sahai and Brent Waters

+ 4

Tsiao Wang

2/19/24, 1:23 AM

Thanks! The searchable encryption or IBE/ABE definitly solves my problem. But, what I want is nobody other than the intended recipient of each piece of data can tell that the encrypted data is destined for them. At best, the receiver are not required to decrypt every ciphertext.

Zhun

2/20/24, 7:50 AM

In that case, you may want to consider using a technique called anonymous encryption. Anonymous encryption is a type of public-key encryption where the identity of the intended recipient is hidden from the sender, and the recipient's anonymity is preserved. The sender encrypts the message using the recipient's public key, but the recipient's identity is kept secret. The recipient can then use their private key to decrypt the message and read its contents. One popular technique for anonymous encryption is known as "group signature".

Zhun

2/20/24, 7:50 AM

In a group signature scheme, a group of users share a common secret key and each user has a unique identity. Any member of the group can produce a signature on behalf of the group without revealing their own identity, and the signature can be verified by anyone with the group's public key. The recipient of a message can use their private key to identify themselves to the group and decrypt the message.

Zhun

2/20/24, 7:50 AM

Another technique for anonymous encryption is called "blind signature". In a blind signature scheme, the sender "blinds" the message by encrypting it with a random value before sending it to the signer. The signer signs the blinded message without seeing the original message, and returns the signed message to the sender. The sender then "unblinds" the signed message to obtain the original message. The signer is unable to link the original message to the recipient, preserving their anonymity.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Do there exist cryptographic algorithm where secret key holder can distinguish ciphertext corresponding to without decrypting?

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.