close
Skip to main content
Springer Nature Link
Log in

Tagged Chameleon Hash from Lattices and Application to Redactable Blockchain

  • Conference paper
  • First Online:
Save conference paper
View saved research
Public-Key Cryptography – PKC 2024 (PKC 2024)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 14603))

Included in the following conference series:

  • 822 Accesses

  • 13 Citations

Abstract

Chameleon hash (CH) is a trapdoor hash function. Generally it is hard to find collisions, but with the help of a trapdoor, finding collisions becomes easy. CH plays an important role in converting a conventional blockchain to a redactable one. However, most of existing CH schemes are too weak to support redactable blockchains. The currently known CH schemes serving for redactable blockchains have the best security of so-called “full collision resistance (\(\text {f-CR}\))”, but they are built either in the random oracle model or rely on heavy tools like the simulation-sound extractable non-interactive zero-knowledge (SSE-NIZK) proof system. Moreover, up to now there is no CH scheme with post-quantum \(\text {f-CR}\) security in the standard model. Therefore, no CH can support redactable blockchains in a post-quantum way without relying on random oracles.

In this paper, we introduce a variant of CH, namely tagged chameleon hash (tCH). Tagged chameleon hash takes a tag into hash evaluations and collision finding algorithms. We define two security notions for tCH, restricted collision resistance (\(\text {r-CR}\)) and full collision resistance (\(\text {f-CR}\)), and prove the equivalence between \(\text {r-CR}\) and \(\text {f-CR}\) when tCH works in the one-time tag mode. We propose a tCH scheme from lattices without using any NIZK proof, and prove that its restricted collision resistance is reduced to the Short Integer Solution (SIS) assumption in the standard model. We also show how to apply tCH to a blockchain in one-time tag mode so that the blockchain can be compiled to a redactable one. Our tCH scheme provides the first post-quantum solution for redactable blockchains, without resorting to random oracles or NIZK proofs. Besides, we also construct a more efficient tCH scheme with \(\text {r-CR}\) tightly reduced to SIS in the random oracle model, which may be of independent interest.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+
from $39.99 /Month
  • Starting from 10 chapters or articles per month
  • Access and download chapters and articles from more than 300k books and 2,500 journals
  • Cancel anytime
View plans

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 119.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 159.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Free shipping worldwide - view details

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, books and news in related subjects, suggested using machine learning.

Notes

  1. 1.

    According to [13], \(\text {e-CR}\) and \(\text {s-CR}\) are incomparable, which means that neither \(\text {e-CR}\) implies \(\text {s-CR}\) nor \(\text {s-CR}\) implies \(\text {e-CR}\).

  2. 2.

    Here, adaptations are only allowed for blocks considered to be settled in the redact-able blockchain system.

References

  1. Agrawal, S., Boneh, D., Boyen, X.: Efficient lattice (H)IBE in the standard model. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 553–572. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13190-5_28

    Chapter  Google Scholar 

  2. Alwen, J., Peikert, C.: Generating shorter bases for hard random lattices. In: STACS, pp. 75–86 (2009)

    Google Scholar 

  3. Ateniese, G., Magri, B., Venturi, D., Andrade, E.R.: Redactable blockchain - or - rewriting history in bitcoin and friends. In: EuroS &P, pp. 111–126 (2017)

    Google Scholar 

  4. Ateniese, G., de Medeiros, B.: On the key exposure problem in chameleon hashes. In: Blundo, C., Cimato, S. (eds.) SCN 2004. LNCS, vol. 3352, pp. 165–179. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-30598-9_12

    Chapter  Google Scholar 

  5. Banerjee, A., Peikert, C., Rosen, A.: Pseudorandom functions and lattices. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 719–737. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_42

  6. Boneh, D., et al.: Fully key-homomorphic encryption, arithmetic circuit ABE and compact garbled circuits. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 533–556. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-55220-5_30

    Chapter  Google Scholar 

  7. Boyen, X., Li, Q.: Towards tightly secure lattice short signature and ID-based encryption. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016. LNCS, vol. 10032, pp. 404–434. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53890-6_14

    Chapter  Google Scholar 

  8. Brakerski, Z., Vaikuntanathan, V.: Lattice-based FHE as secure as PKE. In: ITCS (2014). https://doi.org/10.1145/2554797.2554799

  9. Camenisch, J., Derler, D., Krenn, S., Pöhls, H.C., Samelin, K., Slamanig, D.: Chameleon-hashes with ephemeral trapdoors – and applications to invisible sanitizable signatures. In: Fehr, S. (ed.) PKC 2017. LNCS, vol. 10175, pp. 152–182. Springer, Heidelberg (2017). https://doi.org/10.1007/978-3-662-54388-7_6

    Chapter  Google Scholar 

  10. Chen, X., Tian, H., Zhang, F., Ding, Y.: Comments and improvements on key-exposure free chameleon hashing based on factoring. In: Lai, X., Yung, M., Lin, D. (eds.) Inscrypt 2010. LNCS, vol. 6584, pp. 415–426. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-21518-6_29

    Chapter  Google Scholar 

  11. Chen, X., Zhang, F., Kim, K.: Chameleon hashing without key exposure. In: Zhang, K., Zheng, Y. (eds.) ISC 2004. LNCS, vol. 3225, pp. 87–98. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-30144-8_8

    Chapter  Google Scholar 

  12. Derler, D., Krenn, S., Samelin, K., Slamanig, D.: Fully collision-resistant chameleon-hashes from simpler and post-quantum assumptions. In: Galdi, C., Kolesnikov, V. (eds.) SCN 2020. LNCS, vol. 12238, pp. 427–447. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-57990-6_21

    Chapter  Google Scholar 

  13. Derler, D., Samelin, K., Slamanig, D.: Bringing order to chaos: the case of collision-resistant chameleon-hashes. In: Kiayias, A., Kohlweiss, M., Wallden, P., Zikas, V. (eds.) PKC 2020. LNCS, vol. 12110, pp. 462–492. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45374-9_16

    Chapter  Google Scholar 

  14. Deuber, D., Magri, B., Thyagarajan, S.A.K.: Redactable blockchain in the permissionless setting. In: IEEE Symposium on Security and Privacy, pp. 124–138 (2019). https://doi.org/10.1109/SP.2019.00039

  15. Dodis, Y., Reyzin, L., Smith, A.: Fuzzy extractors: how to generate strong keys from biometrics and other noisy data. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 523–540. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24676-3_31

    Chapter  Google Scholar 

  16. Dorri, A., Kanhere, S.S., Jurdak, R.: MOF-BC: a memory optimized and flexible blockchain for large scale networks. Future Gener. Comput. Syst. 92, 357–373 (2019). https://doi.org/10.1016/J.FUTURE.2018.10.002

    Article  Google Scholar 

  17. Florian, M., Henningsen, S.A., Beaucamp, S., Scheuermann, B.: Erasing data from blockchain nodes. In: EuroS &P. pp. 367–376 (2019). https://doi.org/10.1109/EUROSPW.2019.00047

  18. Garay, J., Kiayias, A., Leonardos, N.: The bitcoin backbone protocol: analysis and applications. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 281–310. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46803-6_10

    Chapter  Google Scholar 

  19. Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: STOC, pp. 197–206 (2008)

    Google Scholar 

  20. Gentry, C., Sahai, A., Waters, B.: Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 75–92. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40041-4_5

    Chapter  Google Scholar 

  21. Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions (extended abstract). In: FOCS, pp. 464–479. IEEE Computer Society (1984)

    Google Scholar 

  22. Goldwasser, S., Micali, S., Rivest, R.L.: A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput. (2) (1988). https://doi.org/10.1137/0217017

  23. Hohenberger, S., Waters, B.: Short and stateless signatures from the RSA assumption. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 654–670. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03356-8_38

    Chapter  Google Scholar 

  24. Khalili, M., Dakhilalian, M., Susilo, W.: Efficient chameleon hash functions in the enhanced collision resistant model. Inf. Sci. 155–164 (2020)

    Google Scholar 

  25. Krawczyk, H., Rabin, T.: Chameleon signatures. In: Proceedings of the Network and Distributed System Security Symposium. NDSS 2000, San Diego, California, USA (2000). https://www.ndss-symposium.org/ndss2000/chameleon-signatures/

  26. Li, Y., Liu, S.: Tagged chameleon hash from lattice and application to redactable blockchain. ePrint (2023). https://eprint.iacr.org/2023/774

  27. Matzutt, R., Kalde, B., Pennekamp, J., Drichel, A., Henze, M., Wehrle, K.: How to securely prune bitcoin’s blockchain. In: IFIP Networking Conference, pp. 298–306 (2020). https://ieeexplore.ieee.org/document/9142720

  28. Micciancio, D., Peikert, C.: Trapdoors for lattices: simpler, tighter, faster, smaller. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 700–718. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_41

    Chapter  Google Scholar 

  29. Micciancio, D., Peikert, C.: Hardness of SIS and LWE with small parameters. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 21–39. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40041-4_2

    Chapter  Google Scholar 

  30. Micciancio, D., Regev, O.: Worst-case to average-case reductions based on gaussian measures. In: FOCS. IEEE Computer Society (2004). https://doi.org/10.1109/FOCS.2004.72

  31. Pan, J., Wagner, B.: Short identity-based signatures with tight security from lattices. In: Cheon, J.H., Tillich, J.-P. (eds.) PQCrypto 2021 2021. LNCS, vol. 12841, pp. 360–379. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-81293-5_19

    Chapter  Google Scholar 

  32. Pedersen, T.P.: Non-interactive and information-theoretic secure verifiable secret sharing. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 129–140. Springer, Heidelberg (1992). https://doi.org/10.1007/3-540-46766-1_9

    Chapter  Google Scholar 

  33. Peikert, C.: Bonsai trees (or, arboriculture in lattice-based cryptography). IACR Cryptology ePrint Archive (2009). http://eprint.iacr.org/2009/359

  34. Puddu, I., Dmitrienko, A., Capkun, S.: \(\mu \)chain: how to forget without hard forks. IACR Cryptology ePrint Archive, p. 106 (2017). http://eprint.iacr.org/2017/106

  35. Pyoung, C.K., Baek, S.J.: Blockchain of finite-lifetime blocks with applications to edge-based IoT. IEEE Internet Things J. 7(3), 2102–2116 (2020). https://doi.org/10.1109/JIOT.2019.2959599

    Article  Google Scholar 

  36. Thyagarajan, S.A.K., Bhat, A., Magri, B., Tschudi, D., Kate, A.: Reparo: Publicly verifiable layer to repair blockchains. In: Borisov, N., Diaz, C. (eds.) FC 2021. LNCS, vol. 12675, pp. 37–56. Springer, Heidelberg (2021). https://doi.org/10.1007/978-3-662-64331-0_2

    Chapter  Google Scholar 

  37. Tsabary, R.: Fully secure attribute-based encryption for t-CNF from LWE. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11692, pp. 62–85. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26948-7_3

    Chapter  Google Scholar 

  38. Wu, C., Ke, L., Du, Y.: Quantum resistant key-exposure free chameleon hash and applications in redactable blockchain. Inf. Sci. 438–449 (2021)

    Google Scholar 

  39. Zhang, D., Le, J., Lei, X., Xiang, T., Liao, X.: Exploring the redaction mechanisms of mutable blockchains: a comprehensive survey. Int. J. Intell. Syst. 36(9), 5051–5084 (2021). https://doi.org/10.1002/INT.22502

    Article  Google Scholar 

Download references

Acknowledgements

We would like to thank the reviewers for their valuable comments. The authors are partially sponsored by Guangdong Major Project of Basic and Applied Basic Research under Grant No. 2019B030302008, National Natural Science Foundation of China under Grant No. 61925207 and the National Key R &D Program of China under Grant No. 2022YFB2701500.

Author information

Authors and Affiliations

  1. Department of Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai, 200240, China

    Yiming Li & Shengli Liu

  2. State Key Laboratory of Cryptology, P.O. Box 5159, Beijing, 100878, China

    Yiming Li & Shengli Liu

Authors
  1. Yiming Li
    View author publications

    Search author on:PubMed Google Scholar

  2. Shengli Liu
    View author publications

    Search author on:PubMed Google Scholar

Corresponding author

Correspondence to Shengli Liu.

Editor information

Editors and Affiliations

  1. The University of Sydney, Sydney, NSW, Australia

    Qiang Tang

  2. The Australian National University, Acton, ACT, Australia

    Vanessa Teague

Rights and permissions

Reprints and permissions

Copyright information

© 2024 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Li, Y., Liu, S. (2024). Tagged Chameleon Hash from Lattices and Application to Redactable Blockchain. In: Tang, Q., Teague, V. (eds) Public-Key Cryptography – PKC 2024. PKC 2024. Lecture Notes in Computer Science, vol 14603. Springer, Cham. https://doi.org/10.1007/978-3-031-57725-3_10

Download citation

Keywords

Publish with us

Policies and ethics

Societies and partnerships