Probabilistic Public Key Encryption with Equality Test Overview

 
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
 
2
 
What is 
PKE with Equality Test
?
Is it related to 
PKE with Keyword Search 
or 
Deterministic PKE
?
Applications
Our
 
construction
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
 
Outline
3
What is 
PKE with Equality Test (PKE-ET)
?
Enc
M
1
pk
1
C
1
Enc
M
2
pk
2
C
2
 
M
1
 =? 
M
2
Test
 
C
1
 
C
2
 
1
 iff M
1
 = 
M
2
4
What is 
PKE with Equality Test (PKE-ET)
?
1. Perfect Consistency
2. Soundness
 
For every 
M
 in plaintext space PtSp(
k
),
 
Pr[ 
Test
(
C
1
, 
C
2
) = 1 ] = 1
if (
pk
1
, 
sk
1
) 
 
G
(1
k
), 
(
pk
2
, 
sk
2
) 
 
G
(1
k
), 
C
1
 
 
E
(
pk
1
, 
M
) and 
C
2
 
 
E
(
pk
2
, 
M
).
 
For any PPT 
A
,
 
Pr[ 
Test
(
C
1
, 
C
2
) = 1 
 M
1
 

 
 M
2
 

 
 
M
1
 
 
M
2 
] 
 
(
k
)
where (
C
1
, 
C
2
, 
sk
1
, 
sk
2
) 
 
A
(1
k
), 
M
1
 
 
D
(
sk
1
, 
C
1
), 
M
2
 
 
D
(
sk
2
, 
C
2
).
5
Is 
PKE-ET
 related to 
PKE with Keyword Search
?
PKE with Keyword Search (PKES)
w 
 : keyword
C
 = Enc(
pk
, 
w
)
T
W
 = Trapdoor(
sk
, 
w
)
Test
(
pk
, 
C
, 
T
W
) = 1  
iff 
 
C
 is an encryption of 
w
 under 
pk
Equality Test
Test
(
pk
, 
C
1
, 
T
W
) = 1  &  
Test
(
pk
, 
C
2
, 
T
W
) = 1
Both 
C
1 
and 
C
2 
are encryptions of the same 
w.
 
Limitations
1.
A tag 
T
W
 can only be generated if 
sk
 is known.
2.
Test
: only applicable to ciphertexts generated under the same 
pk
.
6
Is 
PKE-ET
 related to 
Deterministic PKE
?
Deterministic Public Key Encryption (DPKE)
S
 = Enc(
pk
, 
M
)
M
 = Dec(
sk
, 
C
)
Equality Test
Given 
C
1
 = Enc(
pk
, 
M
1
)  & 
C
2
 = Enc(
pk
, 
M
2
)
C
1
 = 
C
2
  
  
M
1
 = 
M
2
.
 
Limitation
1.
Only applicable to ciphertexts generated under the same 
pk
.
 
7
 
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
 
8
 
Our PKE-ET Construction
 
System Parameters
G
1
, 
G
2
: cyclic groups of prime order 
q
g
: generator of 
G
1
Bilinear pairing 
e
: 
G
1
 x 
G
1
 
 
G
2
PtSp: 
G
1
\{1}
 
KeyGen(1
k
)
sk
 = 
x
 
R
 Z
q
*
pk
 = 
y
 = 
g
x
 
Enc(
pk
, 
m
)
1.
r
 
R
 Z
q
*
2.
Ciphertext 
C
 := (
U, V, W
) where 
U
 = 
g
r
,  
V
 = 
m
r
,  
W
 = 
H
(
U, V, y
r
) 
 
m

r
 
Dec(
sk
, 
C
)
1.
m

r
 
 
W
H
(
U, V, U
x
)
2.
Verify  
r
 
 Z
q
* 
 
m
 
 
G
1
\{1} 
 
U
 = 
g
r
 
 
V
 = 
m
r
3.
If true, return 
m
, else return 
 
Test(
C
1
, 
C
2
)
Given 
C
1
 = (
U
1
, 
V
1
, 
W
1
) and 
C
2
 = (
U
2
, 
V
2
, 
W
2
), if 
e
(
U
1
, 
V
2
) = 
e
(
U
2
, 
V
1
), return 1, else return 0.
9
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
x
0
 and 
x
1
; does not even need to resort its plaintext choosing capability.
10
What Security Level can our PKE-ET scheme achieve?
After challenge phase, the adversary knows:
public key: 
pk
challenge plaintexts: 
x
0
 and 
x
1
challenge ciphertext: 
y
 
Adversary 
A
2
computes 
y
’ = Enc(
pk
’, 
x
1
)
returns 
Test
(
y
, 
y
’)
 
11
 
What 
Security Level 
can our PKE-ET scheme achieve?
 
It achieves 
one-way under chosen ciphertext attack (OW-CCA2)
.
 
OW-ATK:
 
12
 
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
 = 
g
r
,  
V 
= 
m
r
,  
W
 = 
H
(
U
, 
V
, 
y
r
) 
 
m

r
 
Game 2: Replace
 H
(
U*
, 
V*
, 
y
r*
) of the challenge ciphertext with a random string
Enc(
pk
, 
m*
) : 
U*
 = 
g
r*
,  
V* 
= 
m
r*
, 
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.
13
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(1
k
)
sk
 = 
x
 
R
 Z
q
*
pk
 = 
y
 = 
g
x
Enc(
pk
, 
m
)
r
 
R
 Z
q
*
Compute 
U
 = 
g
r
,  
V
 = 
m
r
,  
W
 = 
H
(
U, V, y
r
)
m

r
C
 := (
U, V, W
)
Dec(
sk
, 
C
)
m

r
 
 
W
H
(
U, V, U
x
)
Verify  
r
 
R
 Z
q
* 
 
m
 
 
G
1
\{1} 
 
U
 = 
g
r
 
 
V
 = 
m
r
If true, return 
m
, else return 
 
Observation:
 in a non-bilinear group, this PKE achieves a higher security level.
 
The PKE can be implemented using a non-bilinear group. So we have
more curves to choose from during implementation.
14
Extension: a non-pairing variant
Bad News:
 still cannot achieve IND-ATK
A
1 
chooses 
x
0
 = 
g
r
0
, 
x
1
 = 
g
r
1
 where 
r
0
 
 
r
1
challenge stage: 
b
 
 {0,1}, 
Enc(
pk
, 
x
b
) = (
U
 = 
g
r
, 
V
 = 
x
b
r
, 
W
)
A
2 
returns 0 if 
V
 = 
U
r
0
; 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.
 
15
 
W-IND-ATK
 
In the random oracle model, the PKE in a non-bilinear group is W-IND-CCA2
secure under the DDH assumption.
 
16
 
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?
 
17
 
Q&A
 
 
 
 
More details can be found in the Proc. of CT-RSA 2010
Slide Note
Embed
Share

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.


Uploaded on Sep 06, 2024 | 3 Views


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


  1. 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

  2. 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

  3. 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

  4. 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

  5. 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

  6. 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

  7. 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

  8. 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

  9. 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

  10. 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

  11. What Security Level can our PKE-ET scheme achieve? It achieves one-way under chosen ciphertext attack (OW-CCA2). OW-ATK: 11

  12. 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

  13. 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

  14. 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

  15. 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

  16. 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

  17. Q&A More details can be found in the Proc. of CT-RSA 2010 17

More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#