http://iet.metastore.ingenta.com
1887

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

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

For access to this article, please select a purchase option:

Buy article PDF
£12.50
(plus tax if applicable)
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IET Information Security — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

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.

References

    1. 1)
      • 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.
    2. 2)
      • 2. Groth, J., Sahai, A.: ‘Efficient non-interactive proof systems for bilinear groups’. Advances in Cryptology – EUROCRYPT 2008, April 2008 (LNCS, 4965), pp. 415432.
    3. 3)
      • 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.
    4. 4)
      • 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.
    5. 5)
      • 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.
    6. 6)
      • 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.
    7. 7)
      • 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.
    8. 8)
      • 8. Green, M., Hohenberger, S.: ‘Universally composable adaptive oblivious transfer’. Advances in Cryptology – ASIACRYPT 2008, December 2008 (LNCS, 5350), pp. 179197.
    9. 9)
      • 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.
    10. 10)
      • 10. Hofheinz, D., Jager, T.: ‘Tightly secure signatures and public-key encryption’. Advances in Cryptology – CRYPTO 2012, August 2012 (LNCS, 7417) pp. 590607.
    11. 11)
      • 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.
    12. 12)
      • 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.
    13. 13)
      • 13. Galbraith, S.D., Paterson, K.G., Smart, N.P.: ‘Pairings for cryptographers’, Discrete Appl. Math., 2008, 156, (16), pp. 31133121.
    14. 14)
      • 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.
    15. 15)
      • 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.
    16. 16)
      • 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.
    17. 17)
      • 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.
    18. 18)
      • 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.
    19. 19)
      • 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.
    20. 20)
      • 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.
    21. 21)
      • 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.
    22. 22)
      • 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.
    23. 23)
      • 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.
    24. 24)
      • 24. Chatterjee, S., Menezes, A.: ‘On cryptographic protocols employing asymmetric pairings – the role of Ψ revisited’, Discrete Appl. Math., 2011, 159, (13), pp. 13111322.
    25. 25)
      • 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.
    26. 26)
      • 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.
    27. 27)
      • 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.
    28. 28)
      • 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.
    29. 29)
      • 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.
    30. 30)
      • 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.
    31. 31)
      • 31. DeMillo, R.A., Lipton, R.J.: ‘A probabilistic remark on algebraic program testing’, Inf. Process. Lett., 1978, 7, (4), pp. 193195.
    32. 32)
      • 32. Schwartz, J.T.: ‘Fast probabilistic algorithms for verification of polynomial identities’, J. ACM, 1980, 27, pp. 701717.
    33. 33)
      • 33. Zippel, R.: ‘Probabilistic algorithms for sparse polynomials’. EUROSM'79, 1979 (LNCS, 72), pp. 216226.
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
This is a required field
Please enter a valid email address