Lower Bounds on Structure-Preserving Signatures for Bilateral Messages | SpringerLink
Skip to main content
Springer Nature Link
Log in

Lower Bounds on Structure-Preserving Signatures for Bilateral Messages

  • Conference paper
  • First Online:
Security and Cryptography for Networks (SCN 2018)

Part of the book series: Lecture Notes in Computer Science ((LNSC,volume 11035))

Included in the following conference series:

Abstract

Lower bounds for structure-preserving signature (SPS) schemes based on non-interactive assumptions have only been established in the case of unilateral messages, i.e. schemes signing tuples of group elements all from the same source group. In this paper, we consider the case of bilateral messages, consisting of elements from both source groups. We show that, for Type-III bilinear groups, SPS’s must consist of at least 6 group elements: many more than the 4 elements needed in the unilateral case, and optimal, as it matches a known upper bound from the literature. We also obtain the first non-trivial lower bounds for SPS’s in Type-II groups: a minimum of 4 group elements, whereas constructions with 3 group elements are known from interactive assumptions.

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+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Abe, M., Ambrona, M., Ohkubo, M., Tibouchi, M.: Lower bounds on structurepreserving signatures for bilateral messages. IACR Cryptology ePrint Archive 2018/640 (2018). https://eprint.iacr.org/2018/640

  2. Abe, M., Chase, M., David, B., Kohlweiss, M., Nishimaki, R., Ohkubo, M.: Constant-size structure-preserving signatures: generic constructions and simple assumptions. J. Cryptol. 29(4), 833–878 (2016)

    Article  MathSciNet  Google Scholar 

  3. Abe, M., Fuchsbauer, G., Groth, J., Haralambiev, K., Ohkubo, M.: Structure-preserving signatures and commitments to group elements. J. Cryptol. 29(2), 363–421 (2016)

    Article  MathSciNet  Google Scholar 

  4. Abe, M., Groth, J., Haralambiev, K., Ohkubo, M.: Optimal structure-preserving signatures in asymmetric bilinear groups. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 649–666. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22792-9_37

    Chapter  MATH  Google Scholar 

  5. Abe, M., Groth, J., Ohkubo, M.: Separating short structure-preserving signatures from non-interactive assumptions. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 628–646. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25385-0_34

    Chapter  Google Scholar 

  6. Abe, M., Groth, J., Ohkubo, M., Tibouchi, M.: Structure-preserving signatures from type II pairings. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8616, pp. 390–407. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44371-2_22. Full version: IACR Cryptology ePrint Archive 2014/312

    Chapter  Google Scholar 

  7. Abe, M., Groth, J., Ohkubo, M., Tibouchi, M.: Structure-preserving signatures from type II pairings. IACR Cryptology ePrint Archive, 2014/312 (2014)

    Google Scholar 

  8. Abe, M., Groth, J., Ohkubo, M., Tibouchi, M.: Unified, minimal and selectively randomizable structure-preserving signatures. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 688–712. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-54242-8_29

    Chapter  Google Scholar 

  9. Boneh, D., Boyen, X., Shacham, H.: Short group signatures. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 41–55. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-28628-8_3

    Chapter  Google Scholar 

  10. Boneh, D., Venkatesan, R.: Breaking RSA may not be equivalent to factoring. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 59–71. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0054117

    Chapter  Google Scholar 

  11. Chatterjee, S., Menezes, A.: Type 2 structure-preserving signature schemes revisited. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9452, pp. 286–310. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48797-6_13

    Chapter  Google Scholar 

  12. Coron, J.-S.: Optimal security proofs for PSS and other signature schemes. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 272–287. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-46035-7_18

    Chapter  Google Scholar 

  13. Escala, A., Herold, G., Kiltz, E., Ràfols, C., Villar, J.: An algebraic framework for Diffie-Hellman assumptions. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8043, pp. 129–147. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40084-1_8

    Chapter  Google Scholar 

  14. Fuchsbauer, G., Kiltz, E., Loss, J.: The algebraic group model and its applications. Cryptology ePrint Archive, Report 2017/620 (2017). https://eprint.iacr.org/2017/620

  15. Fuchsbauer, G., Hanser, C., Slamanig, D.: Practical round-optimal blind signatures in the standard model. IACR Cryptology ePrint Archive 2015/626 (2015). https://eprint.iacr.org/2015/626

  16. Galbraith, S.D., Paterson, K.G., Smart, N.P.: Pairings for cryptographers. Discrete Appl. Math. 156(16), 3113–3121 (2008). Applications of Algebra to Cryptography

    Article  MathSciNet  Google Scholar 

  17. Garg, S., Bhaskar, R., Lokam, S.V.: Improved bounds on security reductions for discrete log based signatures. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 93–107. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85174-5_6

    Chapter  Google Scholar 

  18. Ghadafi, E.: Short structure-preserving signatures. In: Sako, K. (ed.) CT-RSA 2016. LNCS, vol. 9610, pp. 305–321. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-29485-8_18

    Chapter  Google Scholar 

  19. Ghadafi, E.: How low can you go? Short structure-preserving signatures for Diffie-Hellman vectors. In: O’Neill, M. (ed.) IMACC 2017. LNCS, vol. 10655, pp. 185–204. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-71045-7_10

    Chapter  Google Scholar 

  20. Ghadafi, E.: More efficient structure-preserving signatures - or: bypassing the type-III lower bounds. In: Foley, S.N., Gollmann, D., Snekkenes, E. (eds.) ESORICS 2017. LNCS, vol. 10493, pp. 43–61. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-66399-9_3

    Chapter  Google Scholar 

  21. Ghadafi, E., Smart, N.P., Warinschi, B.: Groth–sahai proofs revisited. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 177–192. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13013-7_11

    Chapter  Google Scholar 

  22. Jutla, C.S., Roy, A.: Improved structure preserving signatures under standard bilinear assumptions. In: Fehr, S. (ed.) PKC 2017. LNCS, vol. 10175, pp. 183–209. Springer, Heidelberg (2017). https://doi.org/10.1007/978-3-662-54388-7_7

    Chapter  Google Scholar 

  23. Kiltz, E., Pan, J., Wee, H.: Structure-preserving signatures from standard assumptions, revisited. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 275–295. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48000-7_14

    Chapter  Google Scholar 

  24. Libert, B., Peters, T., Yung, M.: Short group signatures via structure-preserving signatures: standard model security from simple assumptions. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 296–316. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48000-7_15

    Chapter  Google Scholar 

  25. Paillier, P., Vergnaud, D.: Discrete-log-based signatures may not be equivalent to discrete log. In: Roy, B. (ed.) ASIACRYPT 2005. LNCS, vol. 3788, pp. 1–20. Springer, Heidelberg (2005). https://doi.org/10.1007/11593447_1

    Chapter  Google Scholar 

  26. Waters, B.: Efficient identity-based encryption without random oracles. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 114–127. Springer, Heidelberg (2005). https://doi.org/10.1007/11426639_7

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Secure Platform Laboratories, NTT Corporation, Tokyo, Japan

    Masayuki Abe & Mehdi Tibouchi

  2. IMDEA Software Institute & Universidad Politécnica de Madrid, Madrid, Spain

    Miguel Ambrona

  3. Security Fundamentals Lab, CSRI, NICT, Tokyo, Japan

    Miyako Ohkubo

Authors
  1. Masayuki Abe
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Miguel Ambrona
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Miyako Ohkubo
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Mehdi Tibouchi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Masayuki Abe .

Editor information

Editors and Affiliations

  1. University of Catania, Catania, Italy

    Dario Catalano

  2. University of Salerno, Fisciano, Italy

    Roberto De Prisco

Rights and permissions

Reprints and permissions

Copyright information

© 2018 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Abe, M., Ambrona, M., Ohkubo, M., Tibouchi, M. (2018). Lower Bounds on Structure-Preserving Signatures for Bilateral Messages. In: Catalano, D., De Prisco, R. (eds) Security and Cryptography for Networks. SCN 2018. Lecture Notes in Computer Science(), vol 11035. Springer, Cham. https://doi.org/10.1007/978-3-319-98113-0_1

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-98113-0_1

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-98112-3

  • Online ISBN: 978-3-319-98113-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation