Top

Published in:

2018 | OriginalPaper | Chapter

A Variant of BLS Signature Scheme with Tight Security Reduction

Authors : Tiong-Sik Ng, Syh-Yuan Tan, Ji-Jian Chin

Published in: Mobile Networks and Management

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In 2001, Boneh, Lynn and Shacham designed a signature scheme using the properties of bilinear pairing from elliptic curve, and based its security under the Computational Diffie-Hellman (CDH) assumption. However, the security reduction is not tight as there is a loss of roughly \(q_s\), the number of sign queries. In this paper, we propose a variant of the BLS signature with tight security reduction based on the co-CDH assumption. Besides upgraded to the notion of strong existential unforgeability under chosen message attack, the variant is backward-compatible with the original BLS signature.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Designing Anomaly Detection System for Cloud Servers by Frequency Domain Features of System Call Identifiers and Machine Learning

next chapter Quantum Authentication Scheme Based on Fingerprint-Encoded Graph States

The co-CDH assumption was first proposed by Boneh et al. in [4]. Our scheme lean towards the modified co-CDH (co-CDH\(^*\)) assumption proposed by Chatterjee et al. in [10]. However, we use the co-CDH assumption throughout this paper for simplicity, as the co-CDH and co-CDH\(^*\) assumptions are equivalent [10].

We propose the usage of a single bit similar to Katz-Wang’s technique in [21] to optimize the signature length. However, the security proof for an integer instead of a bit r works just as well as the RSA-PFDH [11]. The security of PRBG to randomize the signature is not an issue, as proposed and used by Katz-Wang [21] and Koblitz-Menezes [19].

To avoid having a state where two signatures for a message exist at once where the value of the bit r may be either 0 or 1, the signer may enclose the bit r alongside \(\sigma \) to avoid further confusion during verification.

The value of r cannot be changed as once the signature is generated, the value of \(\delta \) in the signature would be corrupted if the value of r is of a different value.

Different from Katz-Wang’s work in [21], \(\mathcal {A}\) is not allowed to query the value of r, since it is not part of the hash inputs.

In this case, \(\mathcal {A}\) falls under the category of an euf-cma Adversary, whose \(m^*\) in the forgery must not be signed before.

In this case, \(\mathcal {A}\) falls under the category of a seuf-cma Adversary, whose \(m^*\) in the forgery must be signed before.

Boneh, D., Boyen, X.: Short signatures without random oracles. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 56–73. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24676-3_4CrossRef

Bao, F., Deng, R.H., Zhu, H.F.: Variations of Diffie-Hellman problem. In: Qing, S., Gollmann, D., Zhou, J. (eds.) ICICS 2003. LNCS, vol. 2836, pp. 301–312. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-39927-8_28CrossRef

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). https://doi.org/10.1007/3-540-44647-8_13CrossRef

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. 416–432. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-39200-9_26CrossRef

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). https://doi.org/10.1007/3-540-45682-1_30CrossRef

Bellare, M., Namprempre, C., Neven, G.: Unrestricted aggregate signatures. In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 411–422. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-73420-8_37CrossRef

Bellare, M., Rogaway. P.: Random oracles are practical: a paradigm for designing efficient protocols. In: Proceedings of 1st ACM Conference on Computer and Communications Security – ACM CCS 1993, pp. 62–73. ACM (1993)

Bellare, M., Rogaway, P.: The exact security of digital signatures-how to sign with RSA and Rabin. In: Maurer, U. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 399–416. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-68339-9_34CrossRef

Choon, J.C., Hee Cheon, J.: An identity-based signature from gap Diffie-Hellman groups. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 18–30. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-36288-6_2CrossRef

10.

Chatterjee, S., Hankerson, D., Knapp, E., Menezes, A.: Comparing two pairing-based aggregate signature schemes. Des. Codes Cryptogr. 55(2), 141–167 (2010). SpringerMathSciNetCrossRef

11.

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_18CrossRef

12.

Coron, J.S.: A variant of Boneh-Franklin IBE with a tight reduction in the random oracle model. Des. Codes Cryptogr. 50(1), 115–133 (2009)MathSciNetCrossRef

13.

Diffie, W., Hellman, M.: New directions in cryptography. IEEE Trans. Inf. Theory 22, 644–654 (1976)MathSciNetCrossRef

14.

Kerry, C.F., Director, C.R.: FIPS PUB 186-4 Federal Information Processing Standards Publication Digital Signature Standard (DSS), FIPS Publication (2013)

15.

ElGamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. In: Blakley, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 10–18. Springer, Heidelberg (1985). https://doi.org/10.1007/3-540-39568-7_2CrossRef

16.

Goh, E.-J., Jarecki, S.: A signature scheme as secure as the Diffie-Hellman problem. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 401–415. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-39200-9_25CrossRef

17.

Goldwasser, S., Micali, S.: Probabilistic encryption. J. Comput. Syst. Sci. 28(2), 270–299 (1984). Springer, HeidelbergMathSciNetCrossRef

18.

Koblitz, N., Menezes, A.: Another look at “Provable Security”. II. In: Barua, R., Lange, T. (eds.) INDOCRYPT 2006. LNCS, vol. 4329, pp. 148–175. Springer, Heidelberg (2006). https://doi.org/10.1007/11941378_12CrossRef

19.

Koblitz, N., Menezes, A.J.: The random oracle model: a twenty-year retrospective. Des. Codes Cryptogr. 77(2–3), 587–610 (2015)MathSciNetCrossRef

20.

Kiltz, E., Masny, D., Pan, J.: Optimal security proofs for signatures from identification schemes. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9815, pp. 33–61. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53008-5_2CrossRef

21.

Katz, J., Wang, N.: Efficiency improvements for signature schemes with tight security reductions. In: ACM – CCS 2003, pp. 155–164 (2003)

22.

Lacharité, M.S.: Security of BLS and BGLS signatures in a multi-user setting. In: Advances in Cryptology 2016 – ARCTICCRYPT 2016, vol. 2, pp. 244–261. Springer, Heidelberg (2016)

23.

Lu, S., Ostrovsky, R., Sahai, A., Shacham, H., Waters, B.: Sequential aggregate signatures and multisignatures without random oracles. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 465–485. Springer, Heidelberg (2006). https://doi.org/10.1007/11761679_28CrossRef

24.

Liu, C., Ranjan, R., Zhang, X., Yang, C., Georgakopoulos, D., Chen, J.: Public auditing for big data storage in cloud computing-a survey. In: 2013 IEEE 16th International Conference on Computational Science and Engineering (CSE), pp. 1128–1135 (2013)

25.

Moody, D., Peralta, R., Perlner, R., Regenscheid, A., Roginsky, A., Chen, L.: Report on pairing-based cryptography. J. Res. Nat. Inst. Stand. Technol. 120, 11–27 (2015)CrossRef

26.

Barker, E., Barker, W., Burr, W., Polk, W., Smid, M.: Recommendation for key management-part 1: general (revised.) In: NIST Special Publication (2006)

27.

Pereira, G.C., Simplício, M.A., Naehrig, M., Barreto, P.S.: A family of implementation-friendly BN elliptic curves. J. Syst. Softw. 84(8), 1319–1326 (2011)CrossRef

28.

Rivest, R.L., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120–126 (1978). ACMMathSciNetCrossRef

29.

Schnorr, C.P.: Efficient identification and signatures for smart cards. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 239–252. Springer, New York (1990). https://doi.org/10.1007/0-387-34805-0_22CrossRef

30.

Wang, Q., Wang, C., Li, J., Ren, K., Lou, W.: Enabling public verifiability and data dynamics for storage security in cloud computing. In: Backes, M., Ning, P. (eds.) ESORICS 2009. LNCS, vol. 5789, pp. 355–370. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-04444-1_22CrossRef

31.

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). https://doi.org/10.1007/978-3-540-24632-9_20CrossRef

Title: A Variant of BLS Signature Scheme with Tight Security Reduction
Authors: Tiong-Sik Ng
Syh-Yuan Tan
Ji-Jian Chin
Publisher: Springer International Publishing
Book: Mobile Networks and Management
Print ISBN: 978-3-319-90774-1

Electronic ISBN: 978-3-319-90775-8

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-319-90775-8_13

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner