Cryptanalysis of Two Signature Schemes Based on Bilinear Pairings in CISC ’05

  • Haeryong Park
  • Zhengjun Cao
  • Lihua Liu
  • Seongan Lim
  • Ikkwon Yie
  • Kilsoo Chun
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 4318)


The bilinearity of pairings allows efficient signature verification for signature schemes based on discrete logarithm type problem and often provides useful additional functionalities to signature schemes. In recent years, bilinear pairings have been widely used to create signature schemes. But the bilinearity can also be an attack point in uncarefully designed protocols. We cryptanalyze two signature schemes presented at CISC ’05, Cheng et al.’s group signature scheme and Gu et al.’s ID-based verifiably encrypted signature scheme, both based on bilinear pairings. We show that their improper uses of a bilinear pairing lead to untraceable group signatures for Cheng et al.’s group signature scheme and universally forgeable signatures for Gu et al.’s ID-based verifiably encrypted signature scheme.


bilinear pairing group signature ID-based cryptography verifiably encrypted signature 


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Asokan, N., Shoup, V., Waidner, M.: Optimistic fair exchange of digital signatures. IEEE J. Selected Areas in Comm. 18(4), 593–610 (2000)CrossRefGoogle Scholar
  2. 2.
    Ateniese, G.: Efficient verifiable encryption (and fair exchange) of digital signatures. In: Sixth ACM Conference on Computer and Communication Security, pp. 138–146. ACM, New York (1999)CrossRefGoogle Scholar
  3. 3.
    Ateniese, G., Camenisch, J., Joye, M., Tsudik, G.: A practical and provably secure coalition-resistant group signature scheme. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 255–270. Springer, Heidelberg (2000)CrossRefGoogle Scholar
  4. 4.
    Ateniese, G., Tsudik, G.: Some open issues and new directions in group signature schemes. In: Franklin, M.K. (ed.) FC 1999. LNCS, vol. 1648, pp. 196–211. Springer, Heidelberg (1999)CrossRefGoogle Scholar
  5. 5.
    Bellare, M., Micciancio, D., Warinschi, B.: Foundations of group signatures: formal definitions, simplified requirements, and a constructionbased on general assumptions. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 614–629. Springer, Heidelberg (2003)CrossRefGoogle Scholar
  6. 6.
    Boneh, D., Boyen, X., Shacham, H.: Short group signatures. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 41–55. Springer, Heidelberg (2004)Google Scholar
  7. 7.
    Boneh, D., Franklin, M.: Identity-Based Encryption from the Weil Pairing. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 213–229. Springer, Heidelberg (2001)CrossRefGoogle Scholar
  8. 8.
    Boneh, D., Gentry, C., Lynn, B., Shacham, H.: Aggregate and verifiably encrypted signatures from bilinear maps. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 272–293. Springer, Heidelberg (2003)CrossRefGoogle Scholar
  9. 9.
    Boneh, D., Lynn, B., Shacham, H.: Short signatures from the Weil pairing. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 514–532. Springer, Heidelberg (2001)CrossRefGoogle Scholar
  10. 10.
    Chaum, D., van Heyst, E.: Group Signatures. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol. 547, pp. 257–265. Springer, Heidelberg (1991)Google Scholar
  11. 11.
    Cheng, X., Zhu, H., Qiu, Y., Wang, X.: Efficient Group Signatures from Bilinear Pairing. In: Feng, D., Lin, D., Yung, M. (eds.) CISC 2005. LNCS, vol. 3822, pp. 128–139. Springer, Heidelberg (2005)CrossRefGoogle Scholar
  12. 12.
    Gu, C., Zhu, Y.: An ID-based verifiable encrypted signature scheme based on Hess’s scheme. In: Feng, D., Lin, D., Yung, M. (eds.) CISC 2005. LNCS, vol. 3822, pp. 42–52. Springer, Heidelberg (2005)CrossRefGoogle Scholar
  13. 13.
    Hess, F.: Efficient identity based signature schemes based on pairings. In: Nyberg, K., Heys, H.M. (eds.) SAC 2002. LNCS, vol. 2595, pp. 310–324. Springer, Heidelberg (2003)CrossRefGoogle Scholar
  14. 14.
    Park, J.M., Chong, E., Siegel, H., Ray, I.: Constructing fair exchange protocols for E-commerce via distributed computation of RSA signatures. In: 22th Annual ACM Symp. on Principles of Distributed Computing, pp. 172–181 (2003)Google Scholar
  15. 15.
    Shamir, A.: Identity-Based Cryptosystems and Signature Schemes. In: Blakely, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 47–53. Springer, Heidelberg (1985)CrossRefGoogle Scholar
  16. 16.
    Susilo, W., Zhang, F., Mu, Y.: Identity-Based Strong Designated Verifier Signature Schemes. In: Wang, H., Pieprzyk, J., Varadharajan, V. (eds.) ACISP 2004. LNCS, vol. 3108, pp. 313–324. Springer, Heidelberg (2004)CrossRefGoogle Scholar
  17. 17.
    Tseng, Y., Jan, J.: Reply: improved group signature scheme based on discrete logarithm problem. Electronics Letters 35(20), 1324 (1999)CrossRefGoogle Scholar
  18. 18.
    Wang, G.: Security Analysis of Several Group Signature Schemes. In: Johansson, T., Maitra, S. (eds.) INDOCRYPT 2003. LNCS, vol. 2904, pp. 252–265. Springer, Heidelberg (2003)CrossRefGoogle Scholar
  19. 19.
    Zhang, F., Kim, K.: ID-based blind signature and ring signature from pairings. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 533–547. Springer, Heidelberg (2002)CrossRefGoogle Scholar
  20. 20.
    Zhang, F., Kim, K.: Efficient ID-Based Blind Signature and Proxy Signature from Bilinear Pairings. In: Safavi-Naini, R., Seberry, J. (eds.) ACISP 2003. LNCS, vol. 2727, pp. 312–323. Springer, Heidelberg (2003)CrossRefGoogle Scholar
  21. 21.
    Zhang, F., Safavi-Naini, R., Susilo, W.: Efficient Verifiably Encrypted Signature and Partially Blind Signature from Bilinear Pairings. In: Johansson, T., Maitra, S. (eds.) INDOCRYPT 2003. LNCS, vol. 2904, pp. 191–204. Springer, Heidelberg (2003)CrossRefGoogle Scholar
  22. 22.
    Zhang, F., Safavi-Naini, R., Susilo, W.: An efficient signature scheme from bilinear pairings and its applications. In: Bao, F., Deng, R., Zhou, J. (eds.) PKC 2004. LNCS, vol. 2947, pp. 277–290. Springer, Heidelberg (2004)CrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2006

Authors and Affiliations

  • Haeryong Park
    • 1
  • Zhengjun Cao
    • 2
  • Lihua Liu
    • 3
  • Seongan Lim
    • 4
  • Ikkwon Yie
    • 4
  • Kilsoo Chun
    • 1
  1. 1.Korea Information Security Agency (KISA)SeoulKorea
  2. 2.Department of MathematicsShanghai UniversityShanghaiChina
  3. 3.Department of Information and Computation SciencesShanghai Maritime UniversityShanghaiChina
  4. 4.Department of MathematicsInha UniversityIncheonKorea

Personalised recommendations