Abstract
We propose a robust proactive threshold signature scheme, a multisignature scheme and a blind signature scheme which work in any Gap Diffie-Hellman (GDH) group (where the Computational Diffie- Hellman problem is hard but the Decisional Diffie-Hellman problem is easy). Our constructions are based on the recently proposed GDH signature scheme of Boneh et al. [8]. Due to the instrumental structure of GDH groups and of the base scheme, it turns out that most of our constructions are simpler, more efficient and have more useful properties than similar existing constructions. We support all the proposed schemes with proofs under the appropriate computational assumptions, using the corresponding notions of security.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
M. Bellare and P. Rogaway, Random oracles are practical: a paradigm for designing efficient protocols. First ACM Conference on Computer and Communications Security, ACM, 1993.
M. Bellare, C. Namprempre, D. Pointcheval and M. Semanko, “The One-More-RSA-Inversion Problems and the security of Chaum’s Blind Signature Scheme,” Financial Cryptography 01, Lecture Notes in Computer Science, 2001. 36 35, 43
M. Bellare, J. Garay and T. Rabin, “Fast batch verification for modular exponentiation and digital signatures,” Eurocrypt 98, 1998.. 40
E. Berlekamp and L. Welch, “Error correction of algebraic block codes,” US Patent 4,633,470. 33
A. Boldyreva “Threshold signatures, multisignatures and blind signatures based on the Gap-Diffie-Hellman-group signature scheme,” Full version of this paper. Available at http://www-cse.ucsd.edu/users/aboldyre/. 35, 36, 39, 42, 44
D. Boneh and M. Franklin. “Identity-based encryption from the Weil Pairing,” Crypto 01, 2001.
D. Boneh, C. Gentry, B. Lynn and H. Shacham, “Aggregate signatures from bilinear maps,” Manuscript. 34
D. Boneh, B. Lynn and H. Shacham, “Short signatures from theWeil pairing,” Asiacrypt 01, 2001. 31, 32, 36, 37, 40, 42
C. Boyd, “Digital multisignatures,” Cryptography and Coding, 198632
J. Camenisch and M. Stadler, “Efficient group signatures for large groups,” Crypto 97, 1997. 34
D. Chaum, “Blind signatures for untreaceable payments,” Crypto 82, 1982. 35, 43
D. Chaum and E. van Heyst, “Group signatures,” Eurocrypt 91, 1991.
R. Canetti and A. Herzberg, “Maintaining security in the presence of transient faults,” Crypto 94, 1994. 32, 34
Y. Desmedt, “Society and group oriented cryptography,” Crypto 87, 1987. 32
Y. Desmedt, “Threshold cryptography,”, European Transactions on Telecommunications, 5(4), 1994. 32
Y. Desmedt and Y. Frankel, “Threshold cryptosystems,” Crypto 89, 1989. 32, 33
Y. Desmedt and Y. Frankel, “Shared generation of authenticators and signatures,” Crypto 91, 1991. 33
P. Feldman “Ap ractical scheme for non-interactive verifiable secret sharing,” FOCS 87, 1987. 38
Y. Frankel, P. Gemmal, P. Mac Kenzie and M. Yung, “Proactive RSA,” Crypto 97, 1997. 33
S. Galbraith, J. Malone-Lee, N.P. Smart, “Public key signatures in the multi-user setting”, Information Processing Letters, Vol. 83, Issue 5, 2002.
R. Gennaro, S. Jarecki, H. Krawczyk and T. Rabin, “Robust threshold DSS signatures,” Eurocrypt 96, 1996. 33, 38
R. Gennaro, S. Jarecki, H. Krawczyk and T. Rabin, “Secure distributed key generation for discrete-log based cryptosystems”, Eurocrypt 99, 1999. 38
S. Goldwasser, S. Micali and R. Rivest, “Ad igital signature secure against adaptive chosen-message attacks”, SIAM Journal on Computing, 17(2):281–308, 1988. 36, 42
L. Harn, “Group-oriented (t,n) threshold digital signature scheme and digital multisignature,” IEE Proc. Computers and Digital Techniques, 141(5), 1994. 33, 34
A. Herzberg, M. Jakobsson, S. Jarecki, H. Krawczyk and M. Yung, “Proactive public key and signature systems,” ACM Conference on Computers and Communication Security, 1997. 22:612–613, (1979). 33, 39
A. Herzberg, S. Jarecki, H. Krawczyk and M. Yung, “Proactive secret sharing, or: How to cope with perpetual leakage,”, Crypto 95, 1995. 33, 39
P. Horster, M. Michels and H. Petersen, “Meta-multisignatures schemes based on the discrete logarithm problem,” IFIP/Sec1995. 34
K. Itakura and K. Nakamura, “Apublic key cryptosystem suitable for digital multisignatures,” NEC Research & Development, 71:1–8, 1983. 34
A. Joux, “Aon e-round protocol for tripartite Diffie-Hellman,” ANTS-IV conference, vol. 1838. 31, 36
A. Joux and K. Nguyen, “Separating Decision Diffie-Hellman from Diffie-Hellman in cryptographic groups,” e-print archive, report #2001/03. 31, 36
C. Li, T. Hwang and N. Lee, “Threshold-multisignature schemes where suspected forgery implies traceability of adversarial shareholders,” Eurocrypt 94, 1994. 34
A. Lysyanskaya, “Unique signatures and verifiiable random functions from the DH-DDH separation”, Crypto 02, 2002. 31
S. Micali, K. Ohta and L. Reyzin, “Accountable-subgroup multisignatures,” ACM Conference on Computer and Communications Security, 2001. 34, 35, 40, 41, 44
T. Okamoto, “Adigital multisignature schema using bijective public-key cryptosystems,” ACM Transaction on Computer Systems, 6(4): 432–441, 1988. 34
K. Ohta and T. Okamoto, “Adigital multisignature scheme based on the Fiat-Shamir scheme”, Asiacrypt 91, 1991. 34
K. Ohta and T. Okamoto, “Multi-signature scheme secure against active insider attacks”, IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences, E82-A(1):21–31, 1999. 34
R. Ostrovsky and M. Yung, “How to withstand mobile virus attacks,” PODC, 1991. 32
T. Pedersen, “Non-interactive and information-theoretic secure verifiable secret sharing,” Eurocrypt 91, 1991. 38
D. Pointcheval and J. Stern, “Provably secure blind signature schemes,” Asiacrypt 96, 1996. 42
D. Pointcheval and J. Stern, “Security arguments for digital signatures and blind signatures,” Journal of Cryptology, 13(3):361–396, 2000. 42
T. Rabin, “Asim plified approach to threshold and proactive RSA,” Crypto 98, 1998. 33
R. Rivest, A. Shamir and Y. Tauman, “How to leak a secret”, Asiacrypt 01, 2001. 34
A. Shamir, “How to share a secret,” Communications of the ACM, 22:612–613, (1979). 32, 38
V. Shoup, “Practical threshold signatures”, Eurocrypt 00, 2000.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Boldyreva, A. (2003). Threshold Signatures, Multisignatures and Blind Signatures Based on the Gap-Diffie-Hellman-Group Signature Scheme. In: Desmedt, Y.G. (eds) Public Key Cryptography — PKC 2003. PKC 2003. Lecture Notes in Computer Science, vol 2567. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36288-6_3
Download citation
DOI: https://doi.org/10.1007/3-540-36288-6_3
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00324-3
Online ISBN: 978-3-540-36288-3
eBook Packages: Springer Book Archive