Probabilistic Public Key Encryption with Equality Test Overview
An exploration of Probabilistic Public Key Encryption with Equality Test (PKE-ET), discussing its concept, applications, security levels, and comparisons with other encryption schemes such as PKE with Keyword Search and Deterministic PKE. The PKE-ET allows for perfect consistency and soundness in encryption testing. It is introduced as a solution for scenarios like outsourced databases and searchable encryption.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Probabilistic Public Key Encryption with Equality Test Duncan S. Wong Department of Computer Science City University of Hong Kong Joint work with Guomin Yang, Chik How Tan and Qiong Huang 1
Outline What is PKE with Equality Test? Is it related to PKE with Keyword Search or Deterministic PKE? Applications Ourconstruction What security level can it achieve? Impossibility of achieving IND-ATK (e.g. IND-CPA or IND-CCA1/2) Extension: a non-pairing variant W-IND-CCA2 2
What is PKE with Equality Test (PKE-ET)? pk1 M1 C1 Enc M1 =? M2 pk2 M2 C2 Enc C1 1 iff M1 = M2 Test C2 3
What is PKE with Equality Test (PKE-ET)? 1. Perfect Consistency For every M in plaintext space PtSp(k), Pr[ Test(C1, C2) = 1 ] = 1 if (pk1, sk1) G(1k), (pk2, sk2) G(1k), C1 E(pk1, M) and C2 E(pk2, M). 2. Soundness For any PPT A, Pr[ Test(C1, C2) = 1 M1 M2 M1 M2 ] (k) where (C1, C2, sk1, sk2) A(1k), M1 D(sk1, C1), M2 D(sk2, C2). 4
Is PKE-ET related to PKE with Keyword Search? PKE with Keyword Search (PKES) w : keyword C = Enc(pk, w) TW = Trapdoor(sk, w) Test(pk, C, TW) = 1 iff C is an encryption of w under pk Equality Test Test(pk, C1, TW) = 1 & Test(pk, C2, TW) = 1 Both C1 and C2 are encryptions of the same w. Limitations 1. A tag TW can only be generated if sk is known. 2. Test: only applicable to ciphertexts generated under the same pk. 5
Is PKE-ET related to Deterministic PKE? Deterministic Public Key Encryption (DPKE) S = Enc(pk, M) M = Dec(sk, C) Equality Test Given C1 = Enc(pk, M1) & C2 = Enc(pk, M2) C1 = C2 M1 = M2. Limitation 1. Only applicable to ciphertexts generated under the same pk. 6
Applications of PKE-ET Outsourced Database, data are stored in encrypted form. 1. Searchable Encryption: anyone is able to search keywords of encrypted messages even if they are generated under different public keys. E.g. building a search engine capable of searching encrypted messages provided by different vendors 2. Partitioning Encrypted Data: DBMS or the public is able to categorize or obtain statistical information on messages without any help from the encrypted message owners. E.g. partitioning encrypted files based on file types such as images from videos 7
Our PKE-ET Construction System Parameters G1, G2: cyclic groups of prime order q g: generator of G1 Bilinear pairing e: G1 x G1 G2 PtSp: G1\{1} KeyGen(1k) sk = x R Zq* pk = y = gx Enc(pk, m) 1. r R Zq* 2. Ciphertext C := (U, V, W) where U = gr, V = mr, W = H(U, V, yr) m r Dec(sk, C) 1. m r W H(U, V, Ux) 2. Verify r Zq* m G1\{1} U = gr V = mr 3. If true, return m, else return Test(C1, C2) Given C1 = (U1, V1, W1) and C2 = (U2, V2, W2), if e(U1, V2) = e(U2, V1), return 1, else return 0. 8
What Security Level can our PKE-ET scheme achieve? (Impossibility of Achieving IND-ATK) In general, PKE-ET cannot achieve IND-ATK (e.g. IND-CPA or IND-CCA1/2). IND-ATK: Reason why PKE-ET cannot achieve IND-ATK: adversary knows the challenge plaintexts x0 and x1; does not even need to resort its plaintext choosing capability. 9
What Security Level can our PKE-ET scheme achieve? After challenge phase, the adversary knows: public key: pk challenge plaintexts: x0 and x1 challenge ciphertext: y Adversary A2 computes y = Enc(pk , x1) returns Test(y, y ) 10
What Security Level can our PKE-ET scheme achieve? It achieves one-way under chosen ciphertext attack (OW-CCA2). OW-ATK: 11
What Security Level can our PKE-ET scheme achieve? OW-CCA2 security in the random oracle model under the CDH assumption Proof Idea: Game 1: the original scheme Enc(pk, m) : U = gr, V = mr, W = H(U, V, yr) m r Game 2: Replace H(U*, V*, yr*) of the challenge ciphertext with a random string Enc(pk, m*) : U* = gr*, V* = mr*, W* = R* m r Game 1 and Game 2 are indistinguishable under the CDH assumption. The adversary only has a negligible probability to win in Game 2 under the CDH assumption. 12
Extension: a non-pairing variant In the PKE-ET, pairing is used in Test only. If we remove Test, the scheme is a conventional PKE. KeyGen(1k) sk = x R Zq* pk = y = gx Enc(pk, m) r R Zq* Compute U = gr, V = mr, W = H(U, V, yr) m r C := (U, V, W) Dec(sk, C) m r W H(U, V, Ux) Verify r R Zq* m G1\{1} U = gr V = mr If true, return m, else return The PKE can be implemented using a non-bilinear group. So we have more curves to choose from during implementation. Observation: in a non-bilinear group, this PKE achieves a higher security level. 13
Extension: a non-pairing variant Bad News: still cannot achieve IND-ATK A1 chooses x0 = gr0, x1 = gr1 where r0 r1 challenge stage: b {0,1}, Enc(pk, xb) = (U = gr, V = xbr, W) A2 returns 0 if V = Ur0; otherwise, returns 1. Good News: can achieve something stronger than OW-CCA2 W-IND-ATK where the adversary cannot select challenge plaintexts but the adversary is given the challenge plaintexts. 14
W-IND-ATK In the random oracle model, the PKE in a non-bilinear group is W-IND-CCA2 secure under the DDH assumption. 15
Future Work Standard model construction Achieving IND-CCA2 for Test-removed version Question: is there any application for the property that the same scheme is PKE-ET on bilinear group while being a PKE on non-bilinear group? 16
Q&A More details can be found in the Proc. of CT-RSA 2010 17