概率公鑰加密與平等測試Probabilistic Publi

1、 Probabilistic Public Key Encryption with Equality Test 129 without any help from the message owners. These schemes may also be useful in other similar applications such as collection and categorization of condential data through an agent. 5 Weak IND-CCA2 vs Ciphertext Comparability In Sec. 2, we ha

2、ve shown that ciphertext comparability and indistinguishability are irreconcilable. In this section, we are interested in the following question: if we dont need ciphertext comparability, or when being implemented in a nonbilinear group, what kind of security level can our PKE scheme in Sec. 3 achie

3、ve? The rst security model wed like to try is of course IND-CCA. Unfortunately, our scheme is even not IND-CPA secure, as shown below. Theorem 5. The PKE scheme in Sec. 3 with message space G 1 is not IND-CPA secure. Proof. We construct a PPT adversary A as follows. Given public key y , A computes m

4、0 = g r0 and m1 = g r1 for any two distinct r0 and r1 chosen arbitrarily from Z q . A sends (m0 , m1 to the game simulator. After receiving the challenge ciphertext c = (U, V, W , A checks if V = U r0 . If yes, A returns 0; otherwise A returns 1. The probability that A guesses correctly the value of

5、 b is 1. The above attack demonstrates the advantage the adversary can get from selecting the challenge plaintexts. In the next, we dene a dierent set of indistinguishability games where the adversary has no such power. Denition 3 (W-IND-ATK. Let = (G , E , D be a public key encryption scheme and le

6、t A = (A1 , A2 be a polynomial-time adversary. For atk cpa, cca1, cca2 and k N let 1 (pk, sk G (1k , AO 1 (pk , def windatk 1 = Pr (x0 , x1 PtSp(k , b 0, 1, y E (pk, xb , AdvA , 2 2 b AO 2 (pk, x0 , x1 , , y : b = b where x0 = x1 |x0 | = |x1 | and If atk = cpa then O1 ( = and O2 ( = If atk = cca1 th

7、en O1 ( = Dsk ( and O2 ( = If atk = cca2 then O1 ( = Dsk ( and O2 ( = Dsk ( In the case of CCA2, we insist that A2 does not ask its oracle for decrypting windatk is y . We say that is secure in the sense of W-IND-ATK if AdvA , negligible for any A. W-IND-CCA2 Security of Our PKE. Interestingly, we c

8、an show that when being implemented in a non-bilinear group, our PKE scheme given in Sec. 3 can achieve W-IND-CCA2 security under the DDH assumption which is described below. 130 G. Yang et al. Decisional Die-Hellman (DDH Problem. Fix a generator g of G1 . The DDH assumption claims that g, g a, g b

9、, Z and g, g a , g b , g ab are computationally indistinguishable where a, b are randomly selected from Zq and Z is a random element of G1 . Theorem 6. The PKE scheme in Sec. 3 with message space G 1 is W-IND-CCA2 secure in the random oracle model under the DDH assumption. The proof is by contradict

10、ion. Suppose there exists an adversary who can break the encryption scheme, we plant the DDH problem (g, m, U = g r , V = Z into the challenge ciphertext to the adversary, and simulate the decryption oracle in a similar way as in the proof of Theorem 3. Then depending on Z = mr (i.e. Z is in the “ri

11、ght” form or Z G1 (Z is independent of m, the adversary would have dierent probability in winning the game, so we can use the adversary to solve the DDH problem. The detailed proof is deferred to the full version of the paper. Acknowledgement. We would like to thank the anonymous reviewers for their

12、 comments and suggestions. References 1. Abdalla, M., Bellare, M., Catalano, D., Kiltz, E., Kohno, T., Lange, T., Malone-Lee, J., Neven, G., Paillier, P., Shi, H.: Searchable encryption revisited: Consistency properties, relation to anonymous IBE, and extensions. J. Cryptology 21(3, 350391 (2008 2.

13、Abe, M., Gennaro, R., Kurosawa, K., Shoup, V.: Tag-KEM/DEM: A new framework for hybrid encryption and a new analysis of Kurosawa-Desmedt KEM. In: Cramer, R. (ed. EUROCRYPT 2005. LNCS, vol. 3494, pp. 128146. Springer, Heidelberg (2005 3. Bellare, M., Boldyreva, A., ONeill, A.: Deterministic and ecien

14、tly searchable encryption. In: Menezes, A. (ed. CRYPTO 2007. LNCS, vol. 4622, pp. 535552. Springer, Heidelberg (2007 4. Bellare, M., Desai, A., Pointcheval, D., Rogaway, P.: Relations among notions of security for public-key encryption schemes. In: Krawczyk, H. (ed. CRYPTO 1998. LNCS, vol. 1462, pp.

15、 2645. Springer, Heidelberg (1998 5. Bellare, M., Fischlin, M., ONeill, A., Ristenpart, T.: Deterministic encryption: Denitional equivalences and constructions without random oracles. In: Wagner, D. (ed. CRYPTO 2008. LNCS, vol. 5157, pp. 360378. Springer, Heidelberg (2008 6. Boldyreva, A., Fehr, S.,

16、 ONeill, A.: On notions of security for deterministic encryption, and ecient constructions without random oracles. In: Wagner, D. (ed. CRYPTO 2008. LNCS, vol. 5157, pp. 335359. Springer, Heidelberg (2008 7. Boneh, D., Crescenzo, G.D., Ostrovsky, R., Persiano, G.: Public key encryption with keyword s

17、earch. In: Cachin, C., Camenisch, J.L. (eds. EUROCRYPT 2004. LNCS, vol. 3027, pp. 506522. Springer, Heidelberg (2004 8. Camenisch, J., Shoup, V.: Practical veriable encryption and decryption of discrete logarithms. In: Boneh, D. (ed. CRYPTO 2003. LNCS, vol. 2729, pp. 126144. Springer, Heidelberg (20

18、03 Probabilistic Public Key Encryption with Equality Test 131 9. Canetti, R., Halevi, S., Katz, J.: Chosen-ciphertext security from identity-based encryption. In: Cachin, C., Camenisch, J.L. (eds. EUROCRYPT 2004. LNCS, vol. 3027, pp. 207222. Springer, Heidelberg (2004 10. Canetti, R., Halevi, S., Ka

19、tz, J.: A forward-secure public-key encryption scheme. J. Cryptology 20(3, 265294 (2007 11. Cramer, R., Shoup, V.: A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack. In: Krawczyk, H. (ed. CRYPTO 1998. LNCS, vol. 1462, pp. 1325. Springer, Heidelberg (1998 1

20、2. Cramer, R., Shoup, V.: Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption. In: Knudsen, L.R. (ed. EUROCRYPT 2002. LNCS, vol. 2332, pp. 4564. Springer, Heidelberg (2002 13. Dent, A.W.: A brief history of provably-secure public-key encryption. In: Vaude

21、nay, S. (ed. AFRICACRYPT 2008. LNCS, vol. 5023, pp. 357370. Springer, Heidelberg (2008 14. Die, W., Hellman, M.E.: New directions in cryptography. IEEE Transactions on Information Theory 22, 644654 (1978 15. Dolev, D., Dwork, C., Naor, M.: Nonmalleable cryptography. SIAM J. Comput. 30(2, 391437 (200

22、0 16. Goldreich, O.: Foundations of Cryptography: Basic Tools. Cambridge University Press, Cambridge (2001 17. Goldwasser, S., Micali, S.: Probabilistic encryption. J. Comput. Syst. Sci. 28(2, 270299 (1984 18. Hanaoka, G., Kurosawa, K.: Ecient chosen ciphertext secure public key encryption under the

23、 computational die-hellman assumption. In: Pieprzyk, J. (ed. ASIACRYPT 2008. LNCS, vol. 5350, pp. 308325. Springer, Heidelberg (2008 19. Hofheinz, D., Kiltz, E.: Secure hybrid encryption from weakened key encapsulation. In: Menezes, A. (ed. CRYPTO 2007. LNCS, vol. 4622, pp. 553571. Springer, Heidelberg (2007 20. Hofheinz, D., Kiltz, E.: Practical chosen ciphertext secure encryption from factoring. In: Joux, A. (ed.