Post-quantum signature with preimage chameleon hashing

• Thiago Astrizi UFSC
• Ricardo Custódio UFSC
• Lucia Moura University of Ottawa

DOI: https://doi.org/10.5753/sbseg.2020.19228

Resumo

In this work, we propose a generalization of the concept of chameleon hash first described in [Krawczyk and Rabin 1998], which we call preimage chameleon hash. While in the conventional chameleon hash, the trapdoor allows a user to compute second preimages, in this generalization, it is possible to compute first preimages. We show how to adapt the post-quantum chameleon hash from [Cash et al. 2010] to a preimage chameleon hash and use this modified construction to build a new signature scheme based on [Mohassel 2011]. A preimage chameleon hash allows the signer to encode in its signature chosen information to be checked during verification. We prove our signature scheme to be strongly unforgeable under a chosen message attack (SUF-CMA).

Referências

Ajtai, M. (1996). Generating hard instances of lattice problems. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 99–108.

Astrizi, T. L. (2020). Repository with preimage chameleon hash test source code. https://github.com/thiagoharry/test_preimage_chameleon_hash.

Ateniese, G., Chou, D. H., de Medeiros, B., and Tsudik, G. (2005). Sanitizable signatures. In Computer Security – ESORICS 2005, LNCS 3679, pages 159–177, Berlin, Heidelberg. Springer.

Ateniese, G. and de Medeiros, B. (2004). Identity-based chameleon hash and applications. In Financial Cryptography, LNCS 3110, pages 164–180, Berlin, Heidelberg. Springer.

Ateniese, G. and de Medeiros, B. (2005). On the key exposure problem in chameleon hashes. In Security in Communication Networks, LNCS 3352, pages 165–179, Berlin, Heidelberg. Springer.

Ateniese, G., Magri, B., Venturi, D., and Andrade, E. (2017). Redactable blockchain– In 2017 IEEE European Symposium on or–rewriting history in bitcoin and friends. Security and Privacy (EuroS&P), pages 111–126. IEEE.

Bellare, M. and Ristov, T. (2008). Hash functions from sigma protocols and improvements to vsh. In Advances in Cryptology ASIACRYPT 2008, LNCS 5350, pages 125–142, Berlin, Heidelberg. Springer.

Bellare, M. and Ristov, T. (2014). A characterization of chameleon hash functions and new, efficient designs. Journal of cryptology, 27(4):799–823.

Blazy, O., Kakvi, S. A., Kiltz, E., and Pan, J. (2015). Tightly-secure signatures from In Public-Key Cryptography – PKC 2015, LNCS 9020, chameleon hash functions. pages 256–279, Berlin, Heidelberg. Springer.

Camenisch, J., Derler, D., Krenn, S., Pöhls, H. C., Samelin, K., and Slamanig, D. (2017). In Public-Key Cryptography – PKC Chameleon-hashes with ephemeral trapdoors. 2017, LNCS 10175, pages 152–182, Berlin, Heidelberg. Springer.

Cash, D., Hofheinz, D., Kiltz, E., and Peikert, C. (2010). Bonsai trees, or how to delegate a lattice basis. In Advances in Cryptology – EUROCRYPT 2010, LNCS 6110, pages 523–552, Berlin, Heidelberg. Springer.

Chien, H.-Y. (2018). Dynamic public key certificates for IoT and WSN scenarios. In 2018 IEEE 42nd Annual Computer Software and Applications Conference (COMPSAC), volume 2, pages 646–651. IEEE.

Derler, D., Samelin, K., and Slamanig, D. (2020). Bringing order to chaos: The case of collision-resistant chameleon-hashes. In Public-Key Cryptography – PKC 2020, LNCS 12110, pages 462–492, Cham. Springer.

Ducas, L. (2014). Accelerating bliss: the geometry of ternary polynomials. IACR Cryptol. ePrint Arch., 2014:874.

Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schwabe, P., Seiler, G., and Stehlé, D. (2018). Crystals-dilithium: A lattice-based digital signature scheme. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2018(1):238–268.

El Bansarkhani, R. and Buchmann, J. (2014). Improvement and efficient implementation of a lattice-based signature scheme. In Selected Areas in Cryptography – SAC 2013, LNCS 8282, pages 48–67, Berlin, Heidelberg. Springer.

Gentry, C., Peikert, C., and Vaikuntanathan, V. (2008). Trapdoors for hard lattices and new cryptographic constructions. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 197–206.

Goldwasser, S., Micali, S., and Rivest, R. L. (1988). A digital signature scheme secure against adaptive chosen-message attacks. SIAM Journal on computing, 17(2):281–308.

Guo, S., Zeng, D., and Xiang, Y. (2013). Chameleon hashing for secure and privacy-preserving vehicular communications. IEEE Transactions on Parallel and Distributed Systems, 25(11):2794–2803.

Krawczyk, H. and Rabin, T. (1998). Chameleon hashing and signatures. http://eprint.iacr.org/1998/010.

Lu, X., Au, M. H., and Zhang, Z. (2019). Raptor: A practical lattice-based (linkable) ring signature. In Applied Cryptography and Network Security, LNCS 11464, pages 110–130, Cham. Springer.

Lyubashevsky, V. and Micciancio, D. (2006). Generalized compact knapsacks are collision resistant. In Automata, Languages and Programming, LNCS 4052, pages 144– 155, Berlin, Heidelberg. Springer.

Micciancio, D. (2002). Generalized compact knapsacks, cyclic lattices, and efficient one way functions from worst-case complexity assumptions. In The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., pages 356–365. IEEE.

Micciancio, D. and Peikert, C. (2012). Trapdoors for lattices: Simpler, tighter, faster, smaller. In Advances in Cryptology – EUROCRYPT 2012, LNCS 7237, pages 700– 718, Berlin, Heidelberg. Springer.

Mohassel, P. (2011). One-time signatures and chameleon hash functions. In Selected Areas in Cryptography, LNCS 6544, pages 302–319, Berlin, Heidelberg. Springer.

Peikert, C. and Rosen, A. (2006). Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices. In Theory of Cryptography, LNCS 3876, pages 145– 166, Berlin, Heidelberg. Springer.

Pornin, T. (2019). New efficient, constant-time implementations of Falcon. IACR Cryptol. ePrint Arch., 2019:893.

Rohloff, K., Cousins, D., and Polyakov, Y. (2020). PALISADE Lattice Cryptography Library (release 1.9.2). https://palisade-crypto.org/.

strongSwan (2020). Bimodal lattice signature scheme (BLISS). https://wiki.strongswan.org/projects/strongswan/wiki/BLISS. Accessed on 29/07/2020.