Tightly-Secure Signatures from Chameleon Hash Functions

详细信息    查看全文

• 作者：Olivier Blazy (14)
  Saqib A. Kakvi (15)
  Eike Kiltz (15)
  Jiaxin Pan (15)
  
  14. XLim ; Universit茅 de Limoges ; Limoges ; France
  15. Horst G枚rtz Institute for IT-Security and Faculty of Mathematics ; Ruhr-University Bochum ; Bochum ; Germany
  
• 关键词：Signature ; Standard model ; Tight reduction ; Chameleon hash
• 刊名：Lecture Notes in Computer Science
• 出版年：2015
• 出版时间：2015
• 年：2015
• 卷：9020
• 期：1
• 页码：256-279
• 全文大小：392 KB
• 参考文献：1. Abe, M, David, B, Kohlweiss, M, Nishimaki, R, Ohkubo, M Tagged one-time signatures: tight security and optimal tag size. In: Kurosawa, K, Hanaoka, G eds. (2013) Public-Key Cryptography 鈥?PKC 2013. Springer, Heidelberg, pp. 312-331
  2. Abe, M, Fuchsbauer, G, Groth, J, Haralambiev, K, Ohkubo, M Structure-preserving signatures and commitments to group elements. In: Rabin, T eds. (2010) Advances in Cryptology 鈥?CRYPTO 2010. Springer, Heidelberg, pp. 209-236
  3. Bader, C., Hofheinz, D., Jager, T., Kiltz, E., Li, Y.: Tightly-secure authenticated key exchange. Cryptology ePrint Archive, Report 2014/797 (2014)
  4. Bellare, M., Ristov, T.: A characterization of chameleon hash functions and new, efficient designs. Journal of Cryptology 27(4), 799鈥?23 (October 2014)
  5. Bellare, M., Rogaway, P.: Random oracles are practical: A paradigm for designing efficient protocols. In: Ashby, V. (ed.) ACM CCS 1993, pp. 62鈥?3. ACM Press, November 1993
  6. Bellare, M, Rogaway, P The exact security of digital signatures - how to sign with RSA and Rabin. In: Maurer, UM eds. (1996) Advances in Cryptology - EUROCRYPT 1996. Springer, Heidelberg, pp. 399-416
  7. Bellare, M, Shoup, S Two-tier signatures, strongly unforgeable signatures, and Fiat-Shamir without random oracles. In: Okamoto, T, Wang, X eds. (2007) Public Key Cryptography 鈥?PKC 2007. Springer, Heidelberg, pp. 201-216
  8. Blazy, O., Kakvi, S., Kiltz, E., Pan. J.: Tightly-secure signatures from chameleon hash functions. Cryptology ePrint Archive, Report 2014/1021 (2014)
  9. Blazy, O, Kiltz, E, Pan, J (Hierarchical) Identity-based encryption from affine message authentication. In: Garay, JA, Gennaro, R eds. (2014) Advances in Cryptology 鈥?CRYPTO 2014. Springer, Heidelberg, pp. 408-425
  10. Boneh, D, Boyen, X Short signatures without random oracles. In: Cachin, C, Camenisch, JL eds. (2004) Advances in Cryptology - EUROCRYPT 2004. Springer, Heidelberg, pp. 56-73
  11. Boneh, D., Boyen, X.: Short signatures without random oracles and the SDH assumption in bilinear groups. Journal of Cryptology 21(2), 149鈥?77 (April 2008)
  12. Boneh, D, Boyen, X, Shacham, H Short group signatures. In: Franklin, M eds. (2004) Advances in Cryptology 鈥?CRYPTO 2004. Springer, Heidelberg, pp. 41-55
  13. Boneh, D, Mironov, I, Shoup, V A secure signature scheme from bilinear maps. In: Joye, M eds. (2003) Topics in Cryptology - CT-RSA 2003. Springer, Heidelberg, pp. 98-110
  14. Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology, revisited (preliminary version). In: 30th ACM STOC, pp. 209鈥?18. ACM Press, May 1998
  15. Cash, D, Hofheinz, D, Kiltz, E, Peikert, C Bonsai trees, or how to delegate a lattice basis. In: Gilbert, H eds. (2010) Advances in Cryptology 鈥?EUROCRYPT 2010. Springer, Heidelberg, pp. 523-552
  16. Catalano, D, Gennaro, R Cramer-damg氓rd signatures revisited: Efficient flat-tree signatures based on factoring. In: Vaudenay, S eds. (2005) Public Key Cryptography - PKC 2005. Springer, Heidelberg, pp. 313-327
  17. Chen, J, Wee, H Fully, (almost) tightly secure IBE and dual system groups. In: Canetti, R, Garay, JA eds. (2013) Advances in Cryptology 鈥?CRYPTO 2013. Springer, Heidelberg, pp. 435-460
  18. Chevallier-Mames, B, Joye, M A practical and tightly secure signature scheme without hash function. In: Abe, M eds. (2006) Topics in Cryptology 鈥?CT-RSA 2007. Springer, Heidelberg, pp. 339-356
  19. Cramer, R, Damg氓rd, IB New generation of secure and practical RSA-based signatures. In: Koblitz, N eds. (1996) Advances in Cryptology - CRYPTO 1996. Springer, Heidelberg, pp. 173-185
  20. Cramer, R., Shoup, V.: Signature schemes based on the strong RSA assumption. In: ACM CCS 1999, pp. 46鈥?1. ACM Press, November 1999
  21. Dodis, Y, Oliveira, R, Pietrzak, K On the generic insecurity of the full domain hash. In: Shoup, V eds. (2005) Advances in Cryptology 鈥?CRYPTO 2005. Springer, Heidelberg, pp. 449-466
  22. Dwork, C, Naor, M An efficient existentially unforgeable signature scheme and its applications. In: Desmedt, YG eds. (1994) Advances in Cryptology - CRYPTO 1994. Springer, Heidelberg, pp. 234-246
  23. Escala, A, Herold, G, Kiltz, E, R脿fols, C, Villar, J An algebraic framework for Diffie-Hellman assumptions. In: Canetti, R, Garay, JA eds. (2013) Advances in Cryptology 鈥?CRYPTO 2013. Springer, Heidelberg, pp. 129-147
  24. Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Ladner, R.E., Dwork, C. (eds.) 40th ACM STOC, pp. 197鈥?06. ACM Press, May 2008
  25. Goh, E.-J., Jarecki, S., Katz, J., Wang, N.: Efficient signature schemes with tight reductions to the Diffie-Hellman problems. Journal of Cryptology 20(4), 493鈥?14 (October 2007)
  26. Goldreich, O Two remarks concerning the Goldwasser-Micali-Rivest signature scheme. In: Odlyzko, AM eds. (1987) Advances in Cryptology - CRYPTO 1986. Springer, Heidelberg, pp. 104-110
  27. Goldwasser, S., Micali, S., Rivest, R.L.: A digital signature scheme secure against adaptive chosen-message attacks. SIAM Journal on Computing 17(2), 281鈥?08 (April 1988)
  28. Groth, J Simulation-sound NIZK proofs for a practical language and constant size group signatures. In: Lai, X, Chen, K eds. (2006) Advances in Cryptology 鈥?ASIACRYPT 2006. Springer, Heidelberg, pp. 444-459
  29. Groth, J, Sahai, A Efficient non-interactive proof systems for bilinear groups. In: Smart, NP eds. (2008) Advances in Cryptology 鈥?EUROCRYPT 2008. Springer, Heidelberg, pp. 415-432
  30. Hofheinz, D, Jager, T Tightly secure signatures and public-key encryption. In: Safavi-Naini, R, Canetti, R eds. (2012) Advances in Cryptology 鈥?CRYPTO 2012. Springer, Heidelberg, pp. 590-607
  31. Hofheinz, D, Jager, T, Kiltz, E Short signatures from weaker assumptions. In: Lee, DH, Wang, X eds. (2011) Advances in Cryptology 鈥?ASIACRYPT 2011. Springer, Heidelberg, pp. 647-666
  32. Hohenberger, S, Waters, B Realizing hash-and-sign signatures under standard assumptions. In: Joux, A eds. (2009) Advances in Cryptology - EUROCRYPT 2009. Springer, Heidelberg, pp. 333-350
  33. Hohenberger, S, Waters, B Short and stateless signatures from the RSA assumption. In: Halevi, S eds. (2009) Advances in Cryptology - CRYPTO 2009. Springer, Heidelberg, pp. 654-670
  34. Katz, J.: Digital Signatures. Springer (2010)
  35. Krawczyk, H., Rabin, T.: Chameleon signatures. In: NDSS 2000. The Internet Society, February 2000
  36. Lindell, Y A simpler construction of CCA2-secure public-key encryption under general assumptions. In: Biham, E eds. (2003) Advances in Cryptology 鈥?EUROCRPYT 2003. Springer, Heidelberg, pp. 241-254
  37. Merkle, RC A certified digital signature. In: Brassard, G eds. (1990) Advances in Cryptology - CRYPTO 1989. Springer, Heidelberg, pp. 218-238
  38. Micciancio, D, Peikert, C Trapdoors for lattices: simpler, tighter, faster, smaller. In: Pointcheval, D, Johansson, T eds. (2012) Advances in Cryptology 鈥?EUROCRYPT 2012. Springer, Heidelberg, pp. 700-718
  39. Micciancio, D., Regev, O.: Worst-case to average-case reductions based on gaussian measures. In: 45th FOCS, pp. 372鈥?81. IEEE Computer Society Press, October 2004
  40. Mohassel, P One-time signatures and chameleon hash functions. In: Biryukov, A, Gong, G, Stinson, DR eds. (2011) Selected Areas in Cryptography. Springer, Heidelberg, pp. 302-319
  41. Naor, M., Yung, M.: Universal one-way hash functions and their cryptographic applications. In: 21st ACM STOC, pp. 33鈥?3. ACM Press, May 1989
  42. Naor, M., Yung, M.: Public-key cryptosystems provably secure against chosen ciphertext attacks. In: 22nd ACM STOC, pp. 427鈥?37. ACM Press, May 1990
  43. Rompel, J.: One-way functions are necessary and sufficient for secure signatures. In: 22nd ACM STOC, pp. 387鈥?94. ACM Press, May 1990
  44. Sch盲ge, S Tight proofs for signature schemes without random oracles. In: Paterson, KG eds. (2011) Advances in Cryptology 鈥?EUROCRYPT 2011. Springer, Heidelberg, pp. 189-206
  45. Waters, B Efficient identity-based encryption without random oracles. In: Cramer, R eds. (2005) Advances in Cryptology 鈥?EUROCRYPT 2005. Springer, Heidelberg, pp. 114-127
  
• 作者单位：Public-Key Cryptography -- PKC 2015
• 丛书名：978-3-662-46446-5
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

We give a new framework for obtaining signatures with a tight security reduction from standard hardness assumptions. Concretely, we show that any Chameleon Hash function can be transformed into a (binary) tree-based signature scheme with tight security. The transformation is in the standard model, i.e., it does not make use of any random oracle. For specific assumptions (such as RSA, Diffie-Hellman and Short Integer Solution (SIS)) we further manage to obtain a more efficient flat-tree construction. Our framework explains and generalizes most of the existing schemes as well as providing a generic means for constructing tight signature schemes based on arbitrary assumptions, which improves the standard Merkle tree transformation. Moreover, we obtain the first tightly secure signature scheme from the SIS assumption and several schemes based on Diffie-Hellman in the standard model. Some of our signature schemes can (using known techniques) be combined with Groth-Sahai proof methodology to yield tightly secure and efficient simulation-sound NIZK proofs of knowledge and CCA-secure encryption in the multi-user/-challenge setting under classical assumptions.