A Pairing-based Blind Signature Scheme with Message Recovery
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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:57752", author = "Song Han and Elizabeth Chang", title = "A Pairing-based Blind Signature Scheme with Message Recovery", 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", volume = "1", number = "8", pages = "2513-6", }
