SearchableEncryptionRevisitedConsistencyProperties,.ppt

Searchable Encryption Revisited: Consistency Properties, Relation to Anonymous IBE, and Extensions Michel Abdalla (Ecole normale supérieure, Paris) Joint work with: Mihir Bellare, Dario Catalano, Eike Kiltz,Tadayoshi Kohno, Tanja Lange, John Malone-Lee, Gregory Neven, Pascal Paillier and Haixia Shi Motivation Suppose Bob sends an encrypted email to Alice Alice’s email gateway may want to test if the email contains the word “urgent”, so that it could route the email accordingly Still, Alice does not want the gateway to be able to decrypt her messages Public-key encryption with keyword search: Enable gateway to test whether a given keyword is present in the email without learning anything else about the email PEKS: Public-key encryption with keyword search [BDOP04] Consistency in cryptography Every cryptographic primitive needs to satisfy two conditions: Security Consistency Example: Public-key encryption Security: Privacy (IND-CPA or IND-CCA) Consistency: Decryption should reverse encryption Let (sk,pk) be the output of the key generation If C = Enc(pk,M), then Dec(sk,C) should return M PEKS Security and consistency [BDOP04] Security (IND-CPA) Ciphertext should not reveal any information about the encrypted keyword The trapdoor for a keyword w should only allow the gateway to learn whether a given ciphertext contains w Consistency Test should output 1 if and only if w=w Consistency of BDOP-PEKS In [BDOP04], the authors presented an efficient PEKS scheme (BDOP-PEKS) based on bilinear maps Based on Boneh-Franklin’s Basic IBE scheme [BF01] BDOP-PEKS does NOT meet their consistency notion There are keywords w and w such that Trapdoor(sk,w) = Trapdoor(sk,w’) Hence, Test(Trapdoor(sk,w),PEKS(pk,w))=1 Is there a weaker notion of consistency met by BDOP-PEKS which is still adequate in practice? Consistency of PEKS schemes Computational consistency of BDOP-PEKS Theorem: BDOP-PEKS is computationally consistent in the random oracle model PEKS-STAT: Our statistically-