Abstract Traceable Signatures is an extension of group signatures that allow tracing of all signatures generated by a particular group member without violating the privacy of remaining members. It also allows members to claim the ownership of previously signed messages. Till date, all the existing traceable signatures are based on number-theoretic assumptions which are insecure in the presence of quantum computers. This work presents the first traceable signature scheme in lattices, which is secure even after the existence of quantum computers. Our scheme is proved to be secure in the random oracle model based on the hardness of Short Integer Solution and Learning with Errors.

References

[1] Agrawal S., Boneh D., and Boyen X., “Efficient Lattice (H) IBE in the Standard Model,” in Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques, Monaco and Nice, pp. 553-572, 2010.

[2] Alwen J. and Peikert C., “Generating Shorter Bases for Hard Random Lattices” Theory of Computing Systems, vol. 48, no. 3, pp. 535-553, 2011.

[3] Boyen X., “Lattice Mixing and Vanishing Trapdoors: A Framework for Fully Secure Short Signatures and More,” in Proceedings of in International Workshop on Public Key Cryptography, Paris, pp. 499-517, 2010.

[4] Brickell E., Pointcheval D., Vaudenay S., and Yung M., “Design Validations for Discrete Logarithm Based Signature Schemes,” in Proceedings of the International Workshop on Practice and Theory in Public Key Cryptography, Melbourne, pp. 276-292, 2000.

[5] Chaum D. and Heyst E, “Group Signatures,” in Proceedings of Workshop on the Theory and Application of Cryptographic Techniques, Brighton, pp. 257-265, 1991.

[6] Fiat A. and Shamir A., “How to Prove Yourself: Practical Solutions to Identification and Signature Problems,” in Proceedings of Conference on the Theory and Application of Cryptographic Techniques, Santa Barbara, pp. 186-194, 1986.

[7] Gentry C., Peikert C., and Vaikuntanathan V., “Trapdoors for Hard Lattices and New Cryptographic Constructions,” in Proceedings of the fortieth annual ACM Symposium on Theory of Computing, New York, pp. 197-206, 2008.

[8] Gordon S., Katz J., and Vaikuntanathan V., “A Group Signature Scheme from Lattice Assumptions,” in Proceedings of International Conference on the Theory and Application of Cryptology and Information Security, Singapore, pp. 395-412, 2010.

[9] Kiayias A., Tsiounis Y., and Yung M., “Traceables Signatures,” in Proceedings of International Conference on the Theory and Applications of Cryptographic Techniques, Interlaken, pp. 571-589, 2004.

[10] Laguillaumie F., Langlois A., Libert B., and Stehlé D., “Lattice Based Group Signatures with Logarithmic Signature Size,” in Proceedings of International Conference on the Theory and Application of Cryptology and Information Security, Bengaluru, pp. 41-61, 2013.

[11] Langlois A., Ling S., Nguyen K., and Wang H., “Lattice-based Group Signature Scheme with Verifier-Local Revocation,” in Proceedings of International Workshop on Public Key Cryptography, Buenos Aires, pp. 345-361, 2014.

[12] Libert B., Ling S., Mouhartem F., Nguyen K., and Wang H., “Signature Schemes with Efficient Protocols and Dynamic Group Signatures from Lattice Assumptions,” in Proceedings of International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, pp. 373-403, 2016.

[13] Libert B., Mouhartem F., and Nguyen K., “A Lattice-Based Group Signature Scheme With Message-Dependent Opening,” in Proceedings of International Conference on Applied Cryptography and Network Security, London, pp. 137-155, 2016.

[14] Ling S., Nguyen K., Wang H., and Xu Y., “Lattice-Based Group Signatures: Achieving Full Dynamicity with Ease,” in Proceedings of International Conference on Applied Cryptography and Network Security, Kanazawa, pp. 293-312, 2017.

[15] Regev O., “On Lattices, Learning with Errors, Random Linear Codes, and Cryptography,” Journal of the ACM, vol. 56, no. 6, pp. 1-37, 2009.

[16] Sakthivel A., “Enhancing Cloud Security based on Group Signature,” The International Arab Journal on Information Technology,” vol. 14, no. 6, pp. 923-929, 2017.

[17] Shor P., “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer,” Society for Industrial and Applied Mathematics Journal, vol. 41, no. 2 pp. 1484-1509, 1997. Traceable Signatures using Lattices 975 Thakkalapally Preethi Thakkalapally Preethi is pursuing her PhD in Computer Science and Engineering at National Institute of Technology Warangal, India. She received her M Tech in Computer Science (CS) from University of Hyderabad, India in 2014. Her areas of interest are lattice-based cryptography, digital signatures, provable security and algorithms. Bharat Amberker received his PhD in 1996 from Indian Institute of Science (IISc), Bangalore, India from the Department of Computer Science and Automation. He is presently working as a Professor in Computer Science and Engineering, National Institute of Technology (NIT) Warangal. He is a senior member IEEE, senior member ACM and member of Cryptology Research Society of India. He has guided PhDs in the area of cryptography and security. His research interest includes cryptography, provable security of cryptographic protocols/primitives, algorithms, information security, network security and digital image watermarking.