Suppose some database manager wants to encrypt his database, but at the same tim

Question

Suppose some database manager wants to encrypt his database, but at the same time, she wants to maintain the search functionality. She came up with an idea: she will use a deterministic public key encryption (with the encryption algorithm to be denoted by Enc) to encrypt all the data entries in the database. More concretely, suppose the data entries are m1,...,mn, and the public key is pk, she encrypts each message and generates the encrypted database c1, . . . , cn, where

for each ci = Enc(pk, mi) for i = 1, . . . , n.

Then whoever wants to search for a message m?, the querier simply encrypts it to get c? = Enc(pk, m?) and compare whether c? equals to any of c1, . . . , cn.

Explain why such a pubic encryption scheme can never be IND-CPA secure. Explain the reason following the IND-CPA definition.

Explanation / Answer

Solution:

Public-key encryption schemes allow anyone to take a plaintext and create a corresponding ciphertext that carries little or no information about the encrypted plaintext, in the eyes of everyone else but the owner of the secret key.

Sometimes, IND-CPA security is insufficient. For example, there are use cases where the adversary can send arbitrary ciphertexts to Bob, and learn whether Bob was able to successfully decrypt. There may also be settings where the adversary can learn some information about the plaintext underlying ciphertexts it made up. To conservatively model such attacks, we would like to additionally allow the adversary to query the challenger on aribtrary ciphertexts; in response the challeger decrypts and gives the plaintext back to the adversary.

For IND-CPA security it is sufficient if an adversary can distinguish between encryptions of two messages m0 and m1. That is, an adversary gets to see an encryption c?Enc(pk,mb) for a random bit b together with the public key pk. Now in order to figure out if c is an encryption of m0 all the adversary has to do is to recompute Enc(pk,m0) and check whether or not this value matches the given ciphertext thus breaking IND-CPA security .

Hence a pubic encryption scheme can never be IND-CPA secure.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.