article

Free access

A digital multisignature scheme using bijective public-key cryptosystems

Editor: Anita K. Jones Author:

Tatsuaki OkamotoAuthors Info & Claims

ACM Transactions on Computer Systems (TOCS), Volume 6, Issue 4

Pages 432 - 441

https://doi.org/10.1145/48012.48246

Published: 01 November 1988 Publication History

PDF eReader

Abstract

A new digital multisignature scheme using bijective public-key cryptosystems that overcomes the problems of previous signature schemes used for multisignatures is proposed. The principal features of this scheme are (1) the length of a multisignature message is nearly equivalent to that for a singlesignature message; (2) by using a one-way hash function, multisignature generation and verification are processed in an efficient manner; (3) the order of signing is not restricted; and (4) this scheme can be constructed on any bijective public-key cryptosystem as well as the RSA scheme. In addition, it is shown that the new scheme is considered as safe as the public-key cryptosystem used in this new scheme. Some variations based on the scheme are also presented.

References

[1]

COPPERSMITH, D. Another birthday attack. In Proceedings of the CR YPTO '85, Lecture Notes in Computer Science, 218, Springer-Verlag, New York, 1985, 14-17.

Crossref

Google Scholar

[2]

DAVIES, D.W. Applying the RSA digital signature to electric mail. IEEE Computer (Feb. 1983), 55-62.

Google Scholar

[3]

DENNING, D.E. Digital signatures with RSA and other public-key cryptosystem. Commun. ACM 27, 4 (Apr. 1984), 388-392.

Crossref

Google Scholar

[4]

DIFFIE, W., AND HELLMAN, M. New directions in cryptography. IEEE Trans. In{. Theor. IT- 22, 6 (Nov. 1976), 644-654.

Google Scholar

[5]

GAREY, M. R., AND JOHNSON, D.S. Computers and Intractability--A Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco, 1979.

Crossref

Google Scholar

[6]

ITAKURA, K., AND NAKAMURA, K. A public-key cryptosystem suitable for digital multisignatures. NEC J. Res. Dev. 71 (Oct. 1983).

Google Scholar

[7]

LEIBERHERR, K. Uniform complexity and digital signatures. In Lecture Notes in Computer Science, 115, Springer-Verlag, New York, 1981, 530-543.

Crossref

Google Scholar

[8]

MATYAS, S.M. Digital signatures--an overview. Comput. Netw. 3, 2 (Apr. 1979), 87-94.

Google Scholar

[9]

OKAMOTO, T., AND SHIRAISHI, A. A fast signature scheme based on quadratic inequalities. In Proceedings of the IEEE Symposium on Security and Privacy (Oakland, Calif., Apr. 1985). IEEE, New York, 1985, 123-132.

Google Scholar

[10]

RAVIN, M. O. Digitalized signatures and public-key functions as intractable as factorization. Tech. Rep. MIT/LCS/TR-212, MIT, Cambridge, Mass., 1979.

Crossref

Google Scholar

[11]

RIVEST, R. V., SHAMIR, A., AND ADLEMAN, L. A method for obtair/ing digital signatures and public-key cryptosystems. Commun. ACM 21, 2 (1978), 120-126.

Crossref

Google Scholar

Cited By

View all

Liang XWang XZhang QYuan SGuan Z(2023)A Lattice-Based Multisignature Scheme for Blockchain-Enabled SystemsEmerging Networking Architecture and Technologies10.1007/978-981-19-9697-9_27(336-346)Online publication date: 1-Feb-2023
https://doi.org/10.1007/978-981-19-9697-9_27
Tessaro SZhu C(2023)Threshold and Multi-signature Schemes from Linear Hash FunctionsAdvances in Cryptology – EUROCRYPT 202310.1007/978-3-031-30589-4_22(628-658)Online publication date: 23-Apr-2023
https://dl.acm.org/doi/10.1007/978-3-031-30589-4_22
Kang DRyu HWon D(2022)Implementation on Partially Verifiable Multi-signature Scheme in Electronic Contract Systems2022 16th International Conference on Ubiquitous Information Management and Communication (IMCOM)10.1109/IMCOM53663.2022.9721802(1-4)Online publication date: 3-Jan-2022
https://doi.org/10.1109/IMCOM53663.2022.9721802
Show More Cited By

Index Terms

A digital multisignature scheme using bijective public-key cryptosystems
1. Security and privacy
  1. Cryptography
    1. Public key (asymmetric) techniques
      1. Public key encryption

Recommendations

Securely combining public-key cryptosystems
CCS '01: Proceedings of the 8th ACM conference on Computer and Communications Security

It is a maxim of sound computer-security practice that a cryptographic key should have only a single use. For example, an RSA key pair should be used only for public-key encryption or only for digital signatures, and not for both.In this paper we show ...
Chosen ciphertext secure keyed-homomorphic public-key cryptosystems

In homomorphic encryption schemes, anyone can perform homomorphic operations, and therefore, it is difficult to manage when, where and by whom they are performed. In addition, the property that anyone can "freely" perform the operation inevitably means ...
Immunizing public key cryptosystems against chosen ciphertext attacks

Three methods for strengthening public key cryptosystems in such a way that they become secure against adaptively chosen ciphertext attacks are presented. In an adaptively chosen ciphertext attack, an attacker can query the deciphering algorithm with ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Computer Systems

ACM Transactions on Computer Systems Volume 6, Issue 4

Nov. 1988

101 pages

ISSN:0734-2071

EISSN:1557-7333

DOI:10.1145/48012

Editor:
Anita K. Jones

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 November 1988

Published in TOCS Volume 6, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

122
Total Citations
View Citations
1,370
Total Downloads

Downloads (Last 12 months)196
Downloads (Last 6 weeks)26

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Liang XWang XZhang QYuan SGuan Z(2023)A Lattice-Based Multisignature Scheme for Blockchain-Enabled SystemsEmerging Networking Architecture and Technologies10.1007/978-981-19-9697-9_27(336-346)Online publication date: 1-Feb-2023
https://doi.org/10.1007/978-981-19-9697-9_27
Tessaro SZhu C(2023)Threshold and Multi-signature Schemes from Linear Hash FunctionsAdvances in Cryptology – EUROCRYPT 202310.1007/978-3-031-30589-4_22(628-658)Online publication date: 23-Apr-2023
https://dl.acm.org/doi/10.1007/978-3-031-30589-4_22
Kang DRyu HWon D(2022)Implementation on Partially Verifiable Multi-signature Scheme in Electronic Contract Systems2022 16th International Conference on Ubiquitous Information Management and Communication (IMCOM)10.1109/IMCOM53663.2022.9721802(1-4)Online publication date: 3-Jan-2022
https://doi.org/10.1109/IMCOM53663.2022.9721802
Goyal RVaikuntanathan V(2022)Locally Verifiable Signature and Key AggregationAdvances in Cryptology – CRYPTO 202210.1007/978-3-031-15979-4_26(761-791)Online publication date: 15-Aug-2022
https://dl.acm.org/doi/10.1007/978-3-031-15979-4_26
Kojima RYamamoto DShimoyama TYasaki KNimura K(2021)A New Schnorr Multi-Signatures to Support Both Multiple Messages Signing and Key AggregationJournal of Information Processing10.2197/ipsjjip.29.52529(525-536)Online publication date: 2021
https://doi.org/10.2197/ipsjjip.29.525
Chen QHan JLi JChen LLi S(2021)A Privacy-Preserving Logistics Information System with TraceabilityCyberspace Safety and Security10.1007/978-3-030-94029-4_11(145-163)Online publication date: 9-Nov-2021
https://dl.acm.org/doi/10.1007/978-3-030-94029-4_11
Erwig AFaust SHostáková KMaitra MRiahi S(2021)Two-Party Adaptor Signatures from Identification SchemesPublic-Key Cryptography – PKC 202110.1007/978-3-030-75245-3_17(451-480)Online publication date: 1-May-2021
https://doi.org/10.1007/978-3-030-75245-3_17
BENTAJER AHEDABOU MENNAAMA FELFEZAZİ S(2020)Development of Design for Enhancing Trust in Cloud’s SPI StackInternational Journal of Computational and Experimental Science and Engineering10.22399/ijcesen.3708736:1(13-18)Online publication date: 31-Mar-2020
https://doi.org/10.22399/ijcesen.370873
Lou XWang YLong HYang YLi J(2020)Sequential Quantum Multiparty Signature Based on Quantum Fourier Transform and Chaotic SystemIEEE Access10.1109/ACCESS.2020.29662558(13218-13227)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.2966255
Kojima RYamamoto DShimoyama TYasaki KNimura K(2020)A Novel Scheme of Schnorr Multi-signatures for Multiple Messages with Key AggregationAdvances on Broad-Band Wireless Computing, Communication and Applications10.1007/978-3-030-61108-8_28(284-295)Online publication date: 8-Oct-2020
https://doi.org/10.1007/978-3-030-61108-8_28
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Securely combining public-key cryptosystems

Chosen ciphertext secure keyed-homomorphic public-key cryptosystems

Immunizing public key cryptosystems against chosen ciphertext attacks

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Share

Share this Publication link

Share on social media

Affiliations