A Pairing-based Blind Signature Scheme with Message Recovery

Authors: Song Han, Elizabeth Chang

Abstract:

Blind signatures enable users to obtain valid signatures for a message without revealing its content to the signer. This paper presents a new blind signature scheme, i.e. identity-based blind signature scheme with message recovery. Due to the message recovery property, the new scheme requires less bandwidth than the identitybased blind signatures with similar constructions. The scheme is based on modified Weil/Tate pairings over elliptic curves, and thus requires smaller key sizes for the same level of security compared to previous approaches not utilizing bilinear pairings. Security and efficiency analysis for the scheme is provided in this paper.

Keywords: Blind Signature, Message Recovery, Pairings, Elliptic Curves, Blindness

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1071338

References:

[1] M.Abe & E.Fujisaki, How to date blind signatures. Advances in Cryptology-Asiacrypt 1996, LNCS 1163, pp.244-251. 1996.
[2] G. Ateniese & B. de Medeiros, Efficient group signatures without trapdoors. 246-268 Advances in Cryptology-Asiacrypt 2003, LNCS 2894, pp.246-268, 2003.
[3] G. Ateniese & B. de Medeiros, A provably secure Nybery-Rueppel siganture variant with applications. Cryptology ePrint Archive, Report 2004/093.
[4] A. Boldyreva, Efficient threshold signature, multisignature and blind signature schemes based on the Gap-Diffie-Hellman-group signature scheme. Practice and Theory in Public Key Cryptography- PKC-2003, LNCS 2567, Springer-Verlag, Pp.31-46, 2003.
[5] D. Boneh & X. Boyen, Short signatures without random oracles. Proceedings of EUROCRYPT 2004, LNCS 3027, pp.56-73, 2004.
[6] D.Boneh & M.Franklin, Identity-based encryption from the Weil pairing, Proceedings of CRYPTO 2001, Springer-verlag, LNCS 2139, 213- 229, 2001.
[7] S.L.Barreto & Y.Kim, Fast hashing onto elliptic curves over fields of characteristic-3, Cryptology ePrint Archive, Report 2001/098.
[8] P.S.L.M. Barreto, H.Y. Kim, B. Lynn & M. Scott, Efficient algorithms for pairing-based cryptosystems. Advances in Cryptology-Crypto 2002, Springer-Verlag, LNCS 2442, pp.354-368, 2002.
[9] D.Chaum, Blind signatures for untraceable payments. Advances in Cryptology-Crypto 1982, Plenum, NY, pp.199-203, 1983.
[10] K.Eisentraeger, K.Lauter & P.L.Montgomery, An efficient procedure to double and add points on an elliptic curve, Cryptology ePrint Archive, Report 2002/112.
[11] G. Frey, M. M¨uller, & H. R¨uck, The Tate pairing and the Discrete Logarithm applied to elliptic curve cryptosystems, IEEE Transactions on Information Theory 45(5), 1717-1719, 1999.
[12] P. Horster, M. Michels & H. Petersen, Meta-message recovery and meta-blind signature schemes based on the discrete logarithm problem and their applications. Advances in Cryptology- Asiacrypt 1994, Springer-Verlag, LNCS 917, pp.224-237, 1995.
[13] S. D. Galbraith, K. Harrison, & D. Soldera, Implementing the Tate pairing, Algorithmic Number Theory Symposium-ANTS-V, Springer- Verlag, LNCS 2369, 324-337, 2002.
[14] S. Han & Liu, W.Q., 2004, Committal Deniable Signatures over Elliptic Curves. Proceedings of the 23rd IEEE International Performance Computing and Communication Conference, pp. 833-840, Phoenix, Arizona, USA, IEEE Press, 2004.
[15] S. Han, Yeung, K.Y. & Wang, J. 2003, Identity-based Confirmer Signatures from Pairings over Elliptic Curves. Proceedings of ACM Electronics Commerce 2003, pp. 262-263, 2003.
[16] F.Hess, Efficient identity based signature schemes based on pairings, K. Nyberg and H. Heys(Eds.), Selected Areas in Cryptography, SAC 2002, Springer-Verlag, 310-324, 2003.
[17] Standard speciafications for public key cryptography. IEEE P1363- 2000, 2000.
[18] A.Joux, A one-round protocol for tripartite Diffie-Hellman, Algorithm Number Theory Symposium - ANTS-IV, Springer-Verlag, LNCS 1838, 385-394, 2000.
[19] A.Juels, M.Luby, R.Ostrovsky, Security of blind digital signatures (Extended Abstract). Advances in Cryptology-Crypto 1997, Springer- Verlag, LNCS 1294, pp.150-164, 1997.
[20] B. Libert & Jean-Jacques Quisquater, New identity based signcryption schemes from pairings, Proceedings of IEEE Information Theory Workshop 2003, 2003.
[21] B.Libert & Jean-Jacques Quisquater, Identity based undeniable signatures. Topics in Cryptology- CT-RSA 2004, LNCS 2964, pp.112-125, 2004.
[22] K. Nyberg & Rainer A. Rueppel, A new signature scheme based on the DSA giving message recovery. Proceedings of ACM Conference on Computer and Communications Security 1993, ACM Press, pp.58-61, 1993.
[23] D. Pointcheval & J.Stern, Security arguments for digital signatures and blind signatures. Journal of Cryptology 13(3), pp.361-396, 2000.
[24] D. Pointcheval & J.Stern, Provably secure blind signature schemes. Advances in Cryptology-Asiacrypt 1992, Springer-Verlag, LNCS 1163, pp.252-265, 1992.
[25] A.Shamir, Identity-based cryptosystems and signatures. Proceedings of CRYPTO 1984, Springer-verlag, LNCS 196, 47-53, 1985.
[26] N.P.Smart & E.J.Westwood, Point multiplication on ordinary elliptic curves over fields of characteristic three, Applicable Algebra in Engineering, Communication and Computing, Vol 13, 485-497, 2003.
[27] Eric R. Verheul, Self-blindable credential certificates from the Weil pairing. Advances in Cryptology - Asiacrypt 2001, Springer-verlag, LNCS 2248, pp.533-551, 2001.