A Secure Blind Signature Scheme for Computation Limited Users

This manuscript presents a fast blind signature scheme with extremely low computation for users. Only several modular additions and multiplications are required for a user to obtain and verify a signature in the proposed scheme. Comparing with the existing ones in the literature, the scheme greatly reduces the computations for users.

Authors:

• Chun-I Fan
• Ming-Te Chen

Keywords:

• Blind signatures
• Untraceable electronic cash
• Security & privacy
• Electronic commerce

References:

[1] J. Camenisch, J. Piveteau, and M. Stadler, "Blind signatures based on the
discrete logarithm problem," Advances in Cryptology-EUROCRYPT-94,
LNCS 950, Springer-Verlag, 1995, pp. 428-432.
[2] D. Chaum, "Blind signatures for untraceable payments," Advances in
Cryptology-CRYPTO-82, Plenum, 1983, pp. 199-203.
[3] D. Chaum, A. Fiat, and M. Naor, "Untraceable electronic cash," Advances
in Cryptology-CRYPTO-88, LNCS 403, Springer-Verlag, 1990, pp. 319-
327.
[4] C. Chen, C. Chang, and W. Yang, "Hybrid method for modular exponentiation
with precomputation," IEE Electronics Letters, vol. 32, no. 6,
1996, pp. 540-541.
[5] J. Coron, D. Naccache, and J. Stern, "On the security of RSA padding,"
Advances in Cryptology-CRYPTO-99, LNCS 1666, Springer-Verlag,
1999, pp. 1-18.
[6] V. Dimitrov and T. Cooklev, "Two algorithms for modular exponentiation
using nonstandard arithmetics," IEICE Transactions on Fundamentals of
Electronics, Communications and Computer Sciences, vol. E78-A, no. 1,
1995, pp. 82-87.
[7] C. Fan and C. Lei, "A multi-recastable ticket scheme for electronic elections,"
Advances in Cryptology-ASIACRYPT-96, LNCS 1163, Springer-
Verlag, 1996, pp. 116-124.
[8] C. Fan and C. Lei, "User efficient blind signatures," IEE Electronics
Letters, vol. 34, no. 6, 1998, pp. 544-546.
[9] C. Fan, W. Chen, and Y. Yeh, "Randomization enhanced Chaum-s blind
signature scheme," Advances in Research and Application of Network
Security, Computer Communications, vol. 23, no. 17, 2000, pp. 1677-
1680.
[10] C. Fan and C. Lei, "Cryptanalysis on Improved User Efficient Blind
Signatures," IEE Electronics Letters, vol. 37, no. 10, 2001, pp. 630-631.
[11] N. Ferguson, "Single term off-line coins," Advances in Cryptology-
EUROCRYPT-93, LNCS 765, Springer-Verlag, 1994, pp. 318-328.
[12] S. Goldwasser, S. Micali, and R. Rivest, "A digital signature scheme
secure against adaptive chosen-message attacks," Technical Report, MIT
Lab., Computer Science, Cambridge, Mass. March, 1995.
[13] L. Guillou and J. Quisquater, "A practical zero-knowledge protocol fitted
to security microprocessor minimizing both transmission and memory,"
Advances in Cryptology-EUROCRYPT-88, LNCS 330, Springer-Verlag,
1988, pp. 123-128,.
[14] A. Menezes, P. van Oorschot, and S. Vanstone, Handbook of applied
cryptography, CRC Press LLC, 1997.
[15] NIST FIPS PUB XX, Digital Signature Standard (DSS), National
Institute of Standards and Technology, U.S. Department of Commerce,
DRAFT, 1993.
[16] K. Nyberg and R. Rueppel, "A new signature scheme based on the
DSA giving message recovery schemes," The first ACM Conference on
Computer and Communications Security, Fairfax, Virginia, 1994.
[17] T. Okamoto, "Provably secure and practical identification schemes and
corresponding signature schemes," Advances in Cryptology-CRYPTO-92,
LNCS 740, Springer-Verlag, 1992, pp. 31-53.
[18] R. Peralta, "A simple and fast probabilistic algorithm for computing
square roots modulo a prime number," IEEE Transactions on Information
Theory, vol. 32, no. 6, 1986, pp. 846-847.
[19] S. Pohlig and M. Hellman, "An improved algorithm for computing logarithms
over GF(p) and its cryptographic significance," IEEE Transactions
on Information Theory, vol. 24, 1978, pp. 106-110.
[20] D. Pointcheval and J. Stern, "Provably secure blind signature schemes,"
Advances in Cryptology-ASIACRYPT-96, LNCS 1163, Springer-Verlag,
1996, pp. 252-265.
[21] D. Pointcheval and J. Stern, "New blind signatures equivalent to factorization,"
Proceedings of the 4th ACM Conference on Computer and
Communication Security, 1997, pp. 92-99.
[22] M. Rabin, "Digitalized signatures and public-key functions as intractable
as factorization," Technical Report, MIT/LCS/TR212, MIT Lab., Computer
Science, Cambridge, Mass. Jan. 1979.
[23] R. Rivest, A. Shamir, and L. Adleman, "A method for obtaining digital
signatures and public key cryptosystems," Communications of the ACM,
vol. 21, no. 2, 1978, pp. 120-126.
[24] C. Schnorr, "Efficient identification and signatures for smart cards,"
Advances in Cryptology-CRYPTO-89, Springer-Verlag, LNCS 435, 1990,
pp. 235-251.
[25] A. Shamir and C. Schnorr, "Cryptanalysis of certain variants of Rabin-s
signature scheme," Information Processing Letters, vol. 19, 1984, pp.
113-115.
[26] Z. Shao, "Improved user efficient blind signatures," IEE Electronics
Letters, vol. 36, no. 16, 2000, pp. 1372-1374.
[27] G. Simmons, Contemporary Cryptology: The Science of Information
Integrity, IEEE Press, N.Y., 1992.
[28] H. Williams, "A modification of the RSA public-key encryption procedure,"
IEEE Transactions on Information Theory, vol. 26, no. 6, 1980,
pp. 726-729.