×

A new universal designated verifier transitive signature scheme for big graph data. (English) Zbl 1350.68094

Summary: We propose a new design of universal designated verifier transitive signatures, to authenticate dynamically growing big graph data. The scheme is built on the classical RSA signature and possesses several desirable properties. It supports edge-signature composition as transitive signatures, i.e., with the signatures of two adjacent edges \((i, j)\) and \((j, k)\), one can obtain a valid signature of the edge \((i, k)\). Additionally, a signature holder can convince only one designated verifier about the existence of an edge. Our design can efficiently achieve a tradeoff between data authenticity (when publishing dynamically growing big graph data) and data privacy (when disseminating big graph data).

MSC:

68P25 Data encryption (aspects in computer science)
94A60 Cryptography
94A62 Authentication, digital signatures and secret sharing
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Manyika, J.; Chui, M.; Brown, B.; Bughin, J.; Dobbs, R.; Roxburgh, C.; Byers, A. H., Big data: the next frontier for innovation, competition, and productivity (2011), McKinsey Global Institute, Report
[2] Micali, S.; Rivest, R. L., Transitive signature schemes, (Preneel, B., Topics in Cryptology - CT-RSA 2002, the Cryptographer’s Track at the RSA Conference, Proceedings. Topics in Cryptology - CT-RSA 2002, the Cryptographer’s Track at the RSA Conference, Proceedings, San Jose, CA, USA, February 18-22, 2002. Topics in Cryptology - CT-RSA 2002, the Cryptographer’s Track at the RSA Conference, Proceedings. Topics in Cryptology - CT-RSA 2002, the Cryptographer’s Track at the RSA Conference, Proceedings, San Jose, CA, USA, February 18-22, 2002, Lecture Notes in Computer Science, vol. 2271 (2002), Springer), 236-243 · Zbl 1048.94518
[3] Hou, S.; Huang, X.; Liu, J. K.; Li, J.; Xu, L., Universal designated verifier transitive signatures for graph-based big data, Inf. Sci., 318, 144-156 (2015)
[4] Bellare, M.; Neven, G., Transitive signatures: new schemes and proofs, IEEE Trans. Inf. Theory, 51, 2133-2151 (2005) · Zbl 1282.94076
[5] Steinfeld, R.; Wang, H.; Pieprzyk, J., Efficient extension of standard Schnorr/RSA signatures into Universal Designated-Verifier Signatures, (Bao, F.; Deng, R. H.; Zhou, J., Public Key Cryptography - PKC 2004, 7th International Workshop on Theory and Practice in Public Key Cryptography. Public Key Cryptography - PKC 2004, 7th International Workshop on Theory and Practice in Public Key Cryptography, Singapore, March 1-4, 2004. Public Key Cryptography - PKC 2004, 7th International Workshop on Theory and Practice in Public Key Cryptography. Public Key Cryptography - PKC 2004, 7th International Workshop on Theory and Practice in Public Key Cryptography, Singapore, March 1-4, 2004, Lecture Notes in Computer Science, vol. 2947 (2004), Springer), 86-100 · Zbl 1198.94163
[6] Shahandashti, S. F.; Salmasizadeh, M.; Mohajeri, J., A provably secure short transitive signature scheme from bilinear group pairs, (Blundo, C.; Cimato, S., Security in Communication Networks, 4th International Conference. Security in Communication Networks, 4th International Conference, SCN 2004, Amalfi, Italy, September 8-10, 2004. Security in Communication Networks, 4th International Conference. Security in Communication Networks, 4th International Conference, SCN 2004, Amalfi, Italy, September 8-10, 2004, Lecture Notes in Computer Science, vol. 3352 (2004), Springer), 60-76, Revised Selected Papers · Zbl 1116.94320
[7] Ma, C.; Wu, P.; Gu, G., A new method for the design of stateless transitive signature schemes, (Shen, H. T.; Li, J.; Li, M.; Ni, J.; Wang, W., Advanced Web and Network Technologies, and Applications, APWeb 2006 International Workshops: XRA, IWSN, MEGA, and ICSE, Proceedings. Advanced Web and Network Technologies, and Applications, APWeb 2006 International Workshops: XRA, IWSN, MEGA, and ICSE, Proceedings, Harbin, China, January 16-18, 2006. Advanced Web and Network Technologies, and Applications, APWeb 2006 International Workshops: XRA, IWSN, MEGA, and ICSE, Proceedings. Advanced Web and Network Technologies, and Applications, APWeb 2006 International Workshops: XRA, IWSN, MEGA, and ICSE, Proceedings, Harbin, China, January 16-18, 2006, Lecture Notes in Computer Science, vol. 3842 (2006), Springer), 897-904
[8] Gong, Z.; Huang, Z.; Qiu, W.; Chen, K., Transitive signature scheme from lfsr, J. Inf. Sci. Eng., 26, 131-143 (2010) · Zbl 1238.94033
[9] Bellare, M.; Neven, G., Transitive signatures based on factoring and RSA, (Zheng, Y., Advances in Cryptology - ASIACRYPT 2002, 8th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. Advances in Cryptology - ASIACRYPT 2002, 8th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings, Queenstown, New Zealand, December 1-5, 2002. Advances in Cryptology - ASIACRYPT 2002, 8th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. Advances in Cryptology - ASIACRYPT 2002, 8th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings, Queenstown, New Zealand, December 1-5, 2002, Lecture Notes in Computer Science, vol. 2501 (2002), Springer), 397-414 · Zbl 1065.94561
[10] Wang, L.; Cao, Z.; Zheng, S.; Huang, X.; Yang, Y., Transitive signatures from braid groups, (Srinathan, K.; Rangan, C. P.; Yung, M., Progress in Cryptology - INDOCRYPT 2007, 8th International Conference on Cryptology in India, Proceedings. Progress in Cryptology - INDOCRYPT 2007, 8th International Conference on Cryptology in India, Proceedings, Chennai, India, December 9-13, 2007. Progress in Cryptology - INDOCRYPT 2007, 8th International Conference on Cryptology in India, Proceedings. Progress in Cryptology - INDOCRYPT 2007, 8th International Conference on Cryptology in India, Proceedings, Chennai, India, December 9-13, 2007, Lecture Notes in Computer Science, vol. 4859 (2007), Springer), 183-196 · Zbl 1153.94466
[11] Wang, L.; Cao, Z.; Zeng, P.; Li, X., One-more matching conjugate problem and security of braid-based signatures, (Proceedings of the 2nd ACM Symposium on Information, Computer and Communications Security (2007), ACM), 295-301
[12] Rivest, R. L.; Hohenberger, S. R., The cryptographic impact of groups with infeasible inversion (2003), MIT, Master’s thesis
[13] Yi, X., Directed transitive signature scheme, (Abe, M., Topics in Cryptology - CT-RSA 2007, the Cryptographers’ Track at the RSA Conference 2007, Proceedings. Topics in Cryptology - CT-RSA 2007, the Cryptographers’ Track at the RSA Conference 2007, Proceedings, San Francisco, CA, USA, February 5-9, 2007. Topics in Cryptology - CT-RSA 2007, the Cryptographers’ Track at the RSA Conference 2007, Proceedings. Topics in Cryptology - CT-RSA 2007, the Cryptographers’ Track at the RSA Conference 2007, Proceedings, San Francisco, CA, USA, February 5-9, 2007, Lecture Notes in Computer Science, vol. 4377 (2007), Springer), 129-144 · Zbl 1177.94193
[14] Neven, G., A simple transitive signature scheme for directed trees, Theor. Comput. Sci., 396, 277-282 (2008) · Zbl 1145.68016
[15] Camacho, P.; Hevia, A., Short transitive signatures for directed trees, IACR Cryptol., 2011, 438 (2011), ePrint Archive
[16] Steinfeld, R.; Bull, L.; Wang, H.; Pieprzyk, J., Universal designated-verifier signatures, (Laih, C., Advances in Cryptology - ASIACRYPT 2003, 9th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. Advances in Cryptology - ASIACRYPT 2003, 9th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings, Taipei, Taiwan, November 30-December 4, 2003. Advances in Cryptology - ASIACRYPT 2003, 9th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. Advances in Cryptology - ASIACRYPT 2003, 9th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings, Taipei, Taiwan, November 30-December 4, 2003, Lecture Notes in Computer Science, vol. 2894 (2003), Springer), 523-542 · Zbl 1205.94112
[17] Boneh, D.; Lynn, B.; Shacham, H., Short signatures from the Weil pairing, (Boyd, C., Advances in Cryptology - ASIACRYPT 2001, 7th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. Advances in Cryptology - ASIACRYPT 2001, 7th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings, Gold Coast, Australia, December 9-13, 2001. Advances in Cryptology - ASIACRYPT 2001, 7th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. Advances in Cryptology - ASIACRYPT 2001, 7th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings, Gold Coast, Australia, December 9-13, 2001, Lecture Notes in Computer Science, vol. 2248 (2001), Springer), 514-532 · Zbl 1064.94554
[18] Susilo, W.; Zhang, F.; Mu, Y., Identity-based strong designated verifier signature schemes, (Wang, H.; Pieprzyk, J.; Varadharajan, V., Information Security and Privacy: 9th Australasian Conference, Proceedings. Information Security and Privacy: 9th Australasian Conference, Proceedings, ACISP 2004, Sydney, Australia, July 13-15, 2004. Information Security and Privacy: 9th Australasian Conference, Proceedings. Information Security and Privacy: 9th Australasian Conference, Proceedings, ACISP 2004, Sydney, Australia, July 13-15, 2004, Lecture Notes in Computer Science, vol. 3108 (2004), Springer), 313-324 · Zbl 1098.94630
[19] Zhang, R.; Furukawa, J.; Imai, H., Short signature and universal designated verifier signature without random oracles, (Ioannidis, J.; Keromytis, A. D.; Yung, M., Applied Cryptography and Network Security, Third International Conference, Proceedings. Applied Cryptography and Network Security, Third International Conference, Proceedings, ACNS 2005, New York, NY, USA, June 7-10, 2005. Applied Cryptography and Network Security, Third International Conference, Proceedings. Applied Cryptography and Network Security, Third International Conference, Proceedings, ACNS 2005, New York, NY, USA, June 7-10, 2005, Lecture Notes in Computer Science, vol. 3531 (2005), Science), 483-498 · Zbl 1126.68421
[20] Boneh, D.; Boyen, X., Short signatures without random oracles, (Cachin, C.; Camenisch, J., Advances in Cryptology - EUROCRYPT 2004, International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. Advances in Cryptology - EUROCRYPT 2004, International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings, Interlaken, Switzerland, May 2-6, 2004. Advances in Cryptology - EUROCRYPT 2004, International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. Advances in Cryptology - EUROCRYPT 2004, International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings, Interlaken, Switzerland, May 2-6, 2004, Lecture Notes in Computer Science, vol. 3027 (2004), Springer), 56-73 · Zbl 1122.94354
[21] Laguillaumie, F.; Libert, B.; Quisquater, J., Universal designated verifier signatures without random oracles or non-black box assumptions, (Prisco, R. D.; Yung, M., Security and Cryptography for Networks, 5th International Conference, Proceedings. Security and Cryptography for Networks, 5th International Conference, Proceedings, SCN 2006, Maiori, Italy, September 6-8, 2006. Security and Cryptography for Networks, 5th International Conference, Proceedings. Security and Cryptography for Networks, 5th International Conference, Proceedings, SCN 2006, Maiori, Italy, September 6-8, 2006, Lecture Notes in Computer Science, vol. 4116 (2006), Springer), 63-77 · Zbl 1152.94433
[22] Huang, X.; Susilo, W.; Mu, Y.; Wu, W., Secure universal designated verifier signature without random oracles, Int. J. Inf. Secur., 7, 171-183 (2008)
[23] Shahandashti, S. F.; Safavi-Naini, R., Generic constructions for universal designated-verifier signatures and identitybased signatures from standard signatures, IET Inf. Secur., 3, 152-176 (2009)
[24] Baek, J.; Safavi-Naini, R.; Susilo, W., Universal designated verifier signature proof (or how to efficiently prove knowledge of a signature), (Roy, B. K., Advances in Cryptology - ASIACRYPT 2005, 11th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. Advances in Cryptology - ASIACRYPT 2005, 11th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings, Chennai, India, December 4-8, 2005. Advances in Cryptology - ASIACRYPT 2005, 11th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. Advances in Cryptology - ASIACRYPT 2005, 11th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings, Chennai, India, December 4-8, 2005, Lecture Notes in Computer Science, vol. 3788 (2005), Springer), 644-661 · Zbl 1154.94447
[25] Ng, C. Y.; Susilo, W.; Mu, Y., Universal designated multi verifier signature schemes, (11th International Conference on Parallel and Distributed Systems. 11th International Conference on Parallel and Distributed Systems, ICPADS 2005, Fuduoka, Japan, July 20-22, 2005 (2005), IEEE Computer Society), 305-309
[26] Huang, X.; Susilo, W.; Mu, Y.; Zhang, F., Restricted universal designated verifier signature, (Ma, J.; Jin, H.; Yang, L. T.; Tsai, J. J.P., Ubiquitous Intelligence and Computing, Third International Conference, Proceedings. Ubiquitous Intelligence and Computing, Third International Conference, Proceedings, UIC 2006, Wuhan, China, September 3-6, 2006. Ubiquitous Intelligence and Computing, Third International Conference, Proceedings. Ubiquitous Intelligence and Computing, Third International Conference, Proceedings, UIC 2006, Wuhan, China, September 3-6, 2006, Lecture Notes in Computer Science, vol. 4159 (2006), Springer), 874-882
[27] Laguillaumie, F.; Vergnaud, D., On the soundness of restricted universal designated verifier signatures and dedicated signatures, (Garay, J. A.; Lenstra, A. K.; Mambo, M.; Peralta, R., Information Security, 10th International Conference, Proceedings. Information Security, 10th International Conference, Proceedings, ISC 2007, Valparaíso, Chile, October 9-12, 2007. Information Security, 10th International Conference, Proceedings. Information Security, 10th International Conference, Proceedings, ISC 2007, Valparaíso, Chile, October 9-12, 2007, Lecture Notes in Computer Science, vol. 4779 (2007), Springer), 175-188 · Zbl 1138.94366
[28] Li, J.; Wang, Y., Universal designated verifier ring signature (proof) without random oracles, (Zhou, X.; Sokolsky, O.; Yan, L.; Jung, E.; Shao, Z.; Mu, Y.; Lee, D. C.; Kim, D.; Jeong, Y.; Xu, C., Emerging Directions in Embedded and Ubiquitous Computing EUC 2006 Workshops: NCUS, SecUbiq, USN, TRUST, ESO, and MSA, Proceedings. Emerging Directions in Embedded and Ubiquitous Computing EUC 2006 Workshops: NCUS, SecUbiq, USN, TRUST, ESO, and MSA, Proceedings, Seoul, Korea, August 1-4, 2006. Emerging Directions in Embedded and Ubiquitous Computing EUC 2006 Workshops: NCUS, SecUbiq, USN, TRUST, ESO, and MSA, Proceedings. Emerging Directions in Embedded and Ubiquitous Computing EUC 2006 Workshops: NCUS, SecUbiq, USN, TRUST, ESO, and MSA, Proceedings, Seoul, Korea, August 1-4, 2006, Lecture Notes in Computer Science, vol. 4097 (2006), Springer), 332-341
[29] Shamir, A.; Tauman, Y., Improved online/offline signature schemes, (Kilian, J., Advances in Cryptology - CRYPTO 2001, 21st Annual International Cryptology Conference, Proceedings. Advances in Cryptology - CRYPTO 2001, 21st Annual International Cryptology Conference, Proceedings, Santa Barbara, California, USA, August 19-23, 2001. Advances in Cryptology - CRYPTO 2001, 21st Annual International Cryptology Conference, Proceedings. Advances in Cryptology - CRYPTO 2001, 21st Annual International Cryptology Conference, Proceedings, Santa Barbara, California, USA, August 19-23, 2001, Lecture Notes in Computer Science, vol. 2139 (2001), Springer), 355-367 · Zbl 1003.94533
[30] Bellare, M.; Namprempre, C.; Pointcheval, D.; Semanko, M., The one-more-rsa-inversion problems and the security of Chaum’s blind signature scheme, J. Cryptol., 16, 185-215 (2003) · Zbl 1045.94012
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.