All-but-One Dual Projective Hashing and Its Applications

详细信息    查看全文

• 作者：Zongyang Zhang (18) (21)
  Yu Chen (19)
  Sherman S. M. Chow (20)
  Goichiro Hanaoka (18)
  Zhenfu Cao (21)
  Yunlei Zhao (22)
  
• 关键词：Smooth projective hashing ; ABO lossy trapdoor function ; deterministic encryption ; CCA security
• 刊名：Lecture Notes in Computer Science
• 出版年：2014
• 出版时间：2014
• 年：2014
• 卷：8479
• 期：1
• 页码：181-198
• 参考文献：1. Abdalla, M., Chevalier, C., Pointcheval, D.: Smooth Projective Hashing for Conditionally Extractable Commitments. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol.?5677, pp. 671-89. Springer, Heidelberg (2009) CrossRef
  2. Bellare, M., Boldyreva, A., O’Neill, A.: Deterministic and Efficiently Searchable Encryption. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol.?4622, pp. 535-52. Springer, Heidelberg (2007) CrossRef
  3. Bellare, M., Brakerski, Z., Naor, M., Ristenpart, T., Segev, G., Shacham, H., Yilek, S.: Hedged Public-Key Encryption: How to Protect against Bad Randomness. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol.?5912, pp. 232-49. Springer, Heidelberg (2009) CrossRef
  4. Bellare, M., Fischlin, M., O’Neill, A., Ristenpart, T.: Deterministic Encryption: Definitional Equivalences and Constructions without Random Oracles. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol.?5157, pp. 360-78. Springer, Heidelberg (2008) CrossRef
  5. Bellare, M., Hofheinz, D., Yilek, S.: Possibility and Impossibility Results for Encryption and Commitment Secure under Selective Opening. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol.?5479, pp. 1-5. Springer, Heidelberg (2009) CrossRef
  6. Blazy, O., Pointcheval, D., Vergnaud, D.: Round-Optimal Privacy-Preserving Protocols with Smooth Projective Hash Functions. In: Cramer, R. (ed.) TCC 2012. LNCS, vol.?7194, pp. 94-11. Springer, Heidelberg (2012) CrossRef
  7. Boldyreva, A., Fehr, S., O’Neill, A.: On Notions of Security for Deterministic Encryption, and Efficient Constructions without Random Oracles. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol.?5157, pp. 335-59. Springer, Heidelberg (2008) CrossRef
  8. Brakerski, Z., Segev, G.: Better Security for Deterministic Public-Key Encryption: The Auxiliary-Input Setting. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol.?6841, pp. 543-60. Springer, Heidelberg (2011) CrossRef
  9. 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. 13-5. Springer, Heidelberg (1998) CrossRef
  10. 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. 45-4. Springer, Heidelberg (2002) CrossRef
  11. Damg?rd, I., Jurik, M., Nielsen, J.B.: A generalization of Paillier’s public-key system with applications to electronic voting. Int. J. Inf. Sec.?9(6), 371-85 (2010) CrossRef
  12. Dolev, D., Dwork, C., Naor, M.: Nonmalleable Cryptography. SIAM J. Comput.?30(2), 391-37 (2000) CrossRef
  13. Freeman, D.M., Goldreich, O., Kiltz, E., Rosen, A., Segev, G.: More Constructions of Lossy and Correlation-Secure Trapdoor Functions. J. Cryptology?26(1), 39-4 (2013) CrossRef
  14. Fuller, B., O’Neill, A., Reyzin, L.: A Unified Approach to Deterministic Encryption: New Constructions and a Connection to Computational Entropy. In: Cramer, R. (ed.) TCC 2012. LNCS, vol.?7194, pp. 582-99. Springer, Heidelberg (2012) CrossRef
  15. Gennaro, R., Lindell, Y.: A framework for password-based authenticated key exchange. ACM Trans. Inf. Syst. Secur.?9(2), 181-34 (2006) CrossRef
  16. Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Dwork, C. (ed.) STOC, pp. 197-06. ACM (2008)
  17. Halevi, S., Kalai, Y.T.: Smooth Projective Hashing and Two-Message Oblivious Transfer. J. Cryptology?25(1), 158-93 (2012) CrossRef
  18. Joye, M., Libert, B.: Efficient Cryptosystems from 2 ^{/ k} -th Power Residue Symbols. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol.?7881, pp. 76-2. Springer, Heidelberg (2013) CrossRef
  19. Katz, J., Vaikuntanathan, V.: Smooth Projective Hashing and Password-Based Authenticated Key Exchange from Lattices. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol.?5912, pp. 636-52. Springer, Heidelberg (2009) CrossRef
  20. Mironov, I., Pandey, O., Reingold, O., Segev, G.: Incremental Deterministic Public-Key Encryption. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol.?7237, pp. 628-44. Springer, Heidelberg (2012) CrossRef
  21. Naor, M., Segev, G.: Public-Key Cryptosystems Resilient to Key Leakage. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol.?5677, pp. 18-5. Springer, Heidelberg (2009) CrossRef
  22. Peikert, C., Waters, B.: Lossy Trapdoor Functions and Their Applications. SIAM J. Comput.?40(6), 1803-844 (2011) CrossRef
  23. Raghunathan, A., Segev, G., Vadhan, S.P.: Deterministic Public-Key Encryption for Adaptively Chosen Plaintext Distributions. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol.?7881, pp. 93-10. Springer, Heidelberg (2013) CrossRef
  24. Wee, H.: Efficient Chosen-Ciphertext Security via Extractable Hash Proofs. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol.?6223, pp. 314-32. Springer, Heidelberg (2010) CrossRef
  25. Wee, H.: Dual Projective Hashing and Its Applications - Lossy Trapdoor Functions and More. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol.?7237, pp. 246-62. Springer, Heidelberg (2012) CrossRef
  26. Wichs, D.: Barriers in cryptography with weak, correlated and leaky sources. In: Kleinberg, R.D. (ed.) ITCS, pp. 111-26. ACM (2013)
  
• 作者单位：Zongyang Zhang (18) (21)
  Yu Chen (19)
  Sherman S. M. Chow (20)
  Goichiro Hanaoka (18)
  Zhenfu Cao (21)
  Yunlei Zhao (22)
  
  18. National Institute of Advanced Industrial Science and Technology (AIST), Japan
  21. Department of Computer Science and Engineering, Shanghai Jiao Tong University, Japan
  19. State Key Laboratory of Information Security (SKLOIS), Institute of Information Engineering, Chinese Academy of Sciences, China
  20. Department of Information Engineering, The Chinese University of Hong Kong, Hong Kong
  22. Software School, Fudan University, China
  
• ISSN：1611-3349

文摘

Recently, Wee (EUROCRYPT-2) introduced the notion of dual projective hashing as an extension of the Cramer-Shoup projective hashing, with a simple construction of lossy trapdoor functions, and a simple construction of deterministic encryption schemes which is chosen-plaintext-attack secure with respect to hard-to-invert auxiliary input. In this work, we further extend it to the all-but-one setting by introducing the notion of all-but-one dual projective hashing. We provide a simple construction of all-but-one lossy trapdoor functions. Our construction encompasses many known constructions of all-but-one lossy trapdoor functions, as presented by Peikert and Waters (STOC-8), and Freeman et al. (JoC-3). Particularly, we present a new construction of all-but-one lossy trapdoor functions based on the DLIN assumption, which can be viewed as an extension of Freeman et al.’s DDH-based construction to the DLIN setting, and therefore solves an open problem left by Freeman et al. We also provide a general construction of chosen-ciphertext-attack (CCA) secure deterministic encryption schemes in the standard model, under an additional assumption about the projective map. This extends the general approach of designing CCA secure deterministic encryption schemes by Boldyreva, Fehr and O’Neill (CRYPTO-8). In addition, we present a new construction of CCA secure deterministic encryption schemes based on the DLIN assumption.