access icon free Strongly-optimal structure preserving signatures from Type II pairings: synthesis and lower bounds

Recent work on structure-preserving signatures (SPS) studies optimality of these schemes in terms of the number of group elements needed in the verification key and the signature, and the number of pairing-product equations in the verification algorithm. While these measures are crucial for many applications, another important aspect to consider for performance is verification time, which for these schemes is dominated by pairings computation. Although prior work considers optimality in terms of number of pairing-product equations, this measure does not capture the exact number of pairings needed in verification. To fill this gap, we study the minimal number of pairings needed in verification of SPS. First, we prove lower bounds for schemes in the Type~II setting secure under chosen message attacks in the generic group model. We show that three pairings are necessary and at most one of these pairings can be precomputed. Second, we build an automated tool to search for schemes matching our lower bounds. Using this tool, we find a new randomisable SPS in the Type~II setting that is optimal with respect to our lower bound on the number of pairings, and minimal in terms of group operations to be computed during verification.

Inspec keywords: digital signatures; private key cryptography

Other keywords: randomisable SPS scheme; generic group model; synthesis bounds; verification key; type-II pairings; group elements; random message attacks; lower bounds; strongly-optimal structure preserving signatures; bounded security analysis; pairing-product equations; group operations; key size; SPS verification

Subjects: Data security

References

    1. 1)
      • 6. Libert, B., Peters, T., Joye, M., et al: ‘Linearly homomorphic structure-preserving signatures and their applications’. Advances in Cryptology – CRYPTO 2013, Part II, August 2013 (LNCS, 8043), pp. 289307.
    2. 2)
      • 7. Camenisch, J., Dubovitskaya, M., Enderlein, R.R., et al: ‘Oblivious transfer with hidden access control from attribute-based encryption’. Eighth Int. Conf. on Security in Communication Networks – SCN 12, September 2012 (LNCS, 7485), pp. 559579.
    3. 3)
      • 22. Abe, M., David, B., Kohlweiss, M., et al: ‘Tagged one-time signatures: tight security and optimal tag size’. Sixteenth Int. Conf. on Theory and Practice of Public Key Cryptography – PKC 2013, February/March 2013 (LNCS, 7778), pp. 312331.
    4. 4)
      • 1. Abe, M., Fuchsbauer, G., Groth, J., et al: ‘Structure-preserving signatures and commitments to group elements’. Advances in Cryptology – CRYPTO 2010, August 2010 (LNCS, 6223), pp. 209236.
    5. 5)
      • 2. Groth, J., Sahai, A.: ‘Efficient non-interactive proof systems for bilinear groups’. Advances in Cryptology – EUROCRYPT 2008, April 2008 (LNCS, 4965), pp. 415432.
    6. 6)
      • 30. Barthe, G., Fagerholm, E., Fiore, D., et al: ‘Strongly-optimal structure preserving signatures from type ii pairings: synthesis and lower bounds’. Public-Key Cryptography – PKC 2015, 2015 (LNCS, 9020) pp. 355376.
    7. 7)
      • 8. Green, M., Hohenberger, S.: ‘Universally composable adaptive oblivious transfer’. Advances in Cryptology – ASIACRYPT 2008, December 2008 (LNCS, 5350), pp. 179197.
    8. 8)
      • 26. Malozemoff, A.J., Katz, J., Green, M.D.: ‘Automated analysis and synthesis of block-cipher modes of operation’. Computer Security Foundations Symp. – CSF 2014, 2014.
    9. 9)
      • 33. Zippel, R.: ‘Probabilistic algorithms for sparse polynomials’. EUROSM'79, 1979 (LNCS, 72), pp. 216226.
    10. 10)
      • 21. Abe, M., Groth, J., Ohkubo, M.: ‘Separating short structure-preserving signatures from non-interactive assumptions’. Advances in Cryptology – ASIACRYPT 2011), December 2011 (LNCS, 7073), pp. 628646.
    11. 11)
      • 4. Libert, B., Peters, T., Yung, M.: ‘Group signatures with almost-for-free revocation’. Advances in Cryptology – CRYPTO 2012, August 2012 (LNCS, 7417), pp. 571589.
    12. 12)
      • 31. DeMillo, R.A., Lipton, R.J.: ‘A probabilistic remark on algebraic program testing’, Inf. Process. Lett., 1978, 7, (4), pp. 193195.
    13. 13)
      • 23. Chatterjee, S., Menezes, A.: ‘Type 2 structure-preserving signature schemes revisited’. Cryptology ePrint Archive, Report 2014/635, 2014, http://eprint.iacr.org/2014/635.
    14. 14)
      • 18. Camenisch, J., Haralambiev, K., Kohlweiss, M., et al: ‘Structure preserving CCA secure encryption and applications’. Advances in Cryptology – ASIACRYPT 2011, December 2011 (LNCS, 7073), pp. 89106.
    15. 15)
      • 17. Barthe, G., Fagerholm, E., Fiore, D., et al: ‘Automated analysis of cryptographic assumptions in generic group models’. Advances in Cryptology – CRYPTO 2014, Part I, August 2014 (LNCS, 8616), pp. 95112.
    16. 16)
      • 13. Galbraith, S.D., Paterson, K.G., Smart, N.P.: ‘Pairings for cryptographers’, Discrete Appl. Math., 2008, 156, (16), pp. 31133121.
    17. 17)
      • 15. Abe, M., Groth, J., Ohkubo, M., et al: ‘Unified, minimal and selectively randomizable structure-preserving signatures’. Eleventh Theory of Cryptography Conf. – TCC 2014, February 2014 (LNCS, 8349) pp. 688712.
    18. 18)
      • 19. Groth, J.: ‘Simulation-sound NIZK proofs for a practical language and constant size group signatures’. Advances in Cryptology – ASIACRYPT 2006, December 2006 (LNCS, 4284), pp. 444459.
    19. 19)
      • 28. Abe, M., Groth, J., Ohkubo, M., et al: ‘Converting cryptographic schemes from symmetric to asymmetric bilinear groups’. Advances in Cryptology – CRYPTO 2014, Part I, August 2014 (LNCS, 8616), pp. 241260.
    20. 20)
      • 16. Abe, M., Groth, J., Ohkubo, M., et al: ‘Structure-preserving signatures from type II pairings’. Advances in Cryptology – CRYPTO 2014, Part I, August 2014 (LNCS, 8616), pp. 390407.
    21. 21)
      • 27. Akinyele, J.A., Green, M., Hohenberger, S.: ‘Using SMT solvers to automate design tasks for encryption and signature schemes’. Twentieth Conf. on Computer and Communications Security – ACM CCS 13, November 2013, pp. 399410.
    22. 22)
      • 29. de Ruiter, J.: ‘Automated algebraic analysis of structure-preserving signature schemes’. Cryptology ePrint Archive, Report 2014/590, 2014, http://eprint.iacr.org/2014/590.
    23. 23)
      • 25. Barthe, G., Crespo, J.M., Grégoire, B., et al: ‘Fully automated analysis of padding-based encryption in the computational model’, in Sadeghi, A.-R., Gligor, V.D., Yung, M. (Eds.): ‘ACM CCS 13: 20th Conference on Computer and Communications security’ (ACM Press, 2013), pp. 12471260.
    24. 24)
      • 10. Hofheinz, D., Jager, T.: ‘Tightly secure signatures and public-key encryption’. Advances in Cryptology – CRYPTO 2012, August 2012 (LNCS, 7417) pp. 590607.
    25. 25)
      • 11. Fuchsbauer, G., Hanser, C., Slamanig, D.: ‘Practical round-optimal blind signatures in the standard model’. Cryptology ePrint Archive, Report 2015/626, 2015, http://eprint.iacr.org/2015/626.
    26. 26)
      • 32. Schwartz, J.T.: ‘Fast probabilistic algorithms for verification of polynomial identities’, J. ACM, 1980, 27, pp. 701717.
    27. 27)
      • 5. Attrapadung, N., Libert, B., Peters, T.: ‘Efficient completely context-hiding quotable and linearly homomorphic signatures’. 16th Int. Conf. on Theory and Practice of Public Key Cryptography – PKC 2013, February/March 2013 (LNCS, 7778), pp. 386404.
    28. 28)
      • 9. Abe, M., Chase, M., David, B., et al: ‘Constant-size structure-preserving signatures: generic constructions and simple assumptions’. Advances in Cryptology – ASIACRYPT 2012, December 2012 (LNCS, 7658), pp. 424.
    29. 29)
      • 14. Abe, M., Groth, J., Haralambiev, K., et al: ‘Optimal structure-preserving signatures in asymmetric bilinear groups’. Advances in Cryptology – CRYPTO 2011, August 2011 (LNCS, 6841), pp. 649666.
    30. 30)
      • 3. Fuchsbauer, G., Vergnaud, D.: ‘Fair blind signatures without random oracles’. Third Int. Conf. on Cryptology in Africa – AFRICACRYPT 10, May 2010 (LNCS, 6055), pp. 1633.
    31. 31)
      • 12. Hanser, C., Slamanig, D.: ‘Structure-preserving signatures on equivalence classes and their application to anonymous credentials’. Advances in Cryptology – ASIACRYPT 2014, Part I, December 2014 (LNCS, 8873), pp. 491511.
    32. 32)
      • 24. Chatterjee, S., Menezes, A.: ‘On cryptographic protocols employing asymmetric pairings – the role of Ψ revisited’, Discrete Appl. Math., 2011, 159, (13), pp. 13111322.
    33. 33)
      • 20. Cathalo, J., Libert, B., Yung, M.: ‘Group encryption: Non-interactive realization in the standard model’. Advances in Cryptology – ASIACRYPT 2009, December 2009 (LNCS, 5912), pp. 179196.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-ifs.2015.0429
Loading

Related content

content/journals/10.1049/iet-ifs.2015.0429
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading