The DOI matches its Crossref record; 30 of the 30 references it cites were found in a registry or an index.
A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks
Abstract
We present a digital signature scheme based on the computational difficulty of integer factorization. The scheme possesses the novel property of being robust against an adaptive chosen-message attack: an adversary who receives signatures for messages of his choice (where each message may be chosen in a way that depends on the signatures of previously chosen messages) cannot later forge the signature of even a single additional message. This may be somewhat surprising, since in the folklore the properties of having forgery being equivalent to factoring and being invulnerable to an adaptive chosen-message attack were considered to be contradictory. More generally, we show how to construct a signature scheme with such properties based on the existence of a “claw-free” pair of permutations—a potentially weaker assumption than the intractibility of integer factorization. The new scheme is potentially practical: signing and verifying signatures are reasonably fast, and signatures are compact.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
New directions in cryptography
Diffie, W., & Hellman, M. (1976) · IEEE Transactions on Information Theory · doi:10.1109/tit.1976.1055638 · Cited by 14,713
A method for obtaining digital signatures and public-key cryptosystems
Rivest, R. L., Shamir, A., & Adleman, L. (1978) · Communications of the ACM · doi:10.1145/359340.359342 · Cited by 13,462
Self-citationA method for obtaining digital signatures and public-key cryptosystems
Rivest, R. L., Shamir, A., & Adleman, L. (1983) · Communications of the ACM · doi:10.1145/357980.358017 · Cited by 13,012
Self-citationA public key cryptosystem and a signature scheme based on discrete logarithms
Elgamal, T. (1985) · IEEE Transactions on Information Theory · doi:10.1109/tit.1985.1057074 · Cited by 8,059
Blind Signatures for Untraceable Payments
Chaum, D. (1983) · Advances in Cryptology · doi:10.1007/978-1-4757-0602-4_18 · Cited by 3,260
Goldwasser, S., & Micali, S. (1984) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(84)90070-9 · Cited by 2,603
Self-citationHow to construct random functions
Goldreich, O., Goldwasser, S., & Micali, S. (1986) · Journal of the ACM · doi:10.1145/6490.6503 · Cited by 2,115
Self-citationCryptography and data security
Denning, D. E. (1982) · Calhoun: The Naval Postgraduate School Institutional Archive (Naval Postgraduate School) · Cited by 1,904
A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms
ElGamal, T. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-39568-7_2 · Cited by 1,604
A Randomized Protocol for Signing Contracts
Even, S., Goldreich, O., & Lempel, A. (1983) · Advances in Cryptology · doi:10.1007/978-1-4757-0602-4_19 · Cited by 1,450
Cited by
Items 101–132 of 132
Shim, K.-A. (2012) · IEEE Transactions on Vehicular Technology · doi:10.1109/tvt.2012.2186992 · Cited by 337
1-out-of-n Signatures from a Variety of Keys
Abe, M., Ohkubo, M., & Suzuki, K. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-36178-2_26 · Cited by 337
Efficient and provably secure aggregation of encrypted data in wireless sensor networks
Castelluccia, C., Chan, A. C.-F., Mykletun, E., & Tsudik, G. (2009) · ACM Transactions on Sensor Networks · doi:10.1145/1525856.1525858 · Cited by 331
How to share a function securely
De Santis, A., Desmedt, Y., Frankel, Y., & Yung, M. (1994) · Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 · doi:10.1145/195058.195405 · Cited by 328
Signature schemes based on the strong RSA assumption
Cramer, R., & Shoup, V. (2000) · ACM Transactions on Information and System Security · doi:10.1145/357830.357847 · Cited by 325
Dynamic Audit Services for Outsourced Storages in Clouds
Zhu, Y., Ahn, G.-J., Hu, H., Yau, S. S., An, H. G., & Hu, C.-J. (2013) · IEEE Transactions on Services Computing · doi:10.1109/tsc.2011.51 · Cited by 319
On-line/off-line digital signatures
Even, S., Goldreich, O., & Micali, S. (1996) · Journal of Cryptology · doi:10.1007/bf02254791 · Cited by 318
Self-citationIncremental Cryptography: The Case of Hashing and Signing
Bellare, M., Goldreich, O., & Goldwasser, S. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-48658-5_22 · Cited by 312
Self-citationXMSS - A Practical Forward Secure Signature Scheme Based on Minimal Security Assumptions
Buchmann, J., Dahmen, E., & Hülsing, A. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-25405-5_8 · Cited by 312
Privacy-preserving smart metering
Rial, A., & Danezis, G. (2011) · Proceedings of the 10th annual ACM workshop on Privacy in the electronic society · doi:10.1145/2046556.2046564 · Cited by 312
Sequential Aggregate Signatures from Trapdoor Permutations
Lysyanskaya, A., Micali, S., Reyzin, L., & Shacham, H. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-24676-3_5 · Cited by 311
Self-citationOn the (In)security of the Fiat-Shamir paradigm
Goldwasser, S., & Kalai, Y. T. (2004) · 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. · doi:10.1109/sfcs.2003.1238185 · Cited by 311
Self-citationPointcheval, D., & Sanders, O. (2016) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-29485-8_7 · Cited by 310
Lo, N.-W., & Tsai, J.-L. (2016) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2015.2502322 · Cited by 307
The SPHINCS + Signature Framework
Bernstein, D. J., Hülsing, A., Kölbl, S., Niederhagen, R., Rijneveld, J., & Schwabe, P. (2019) · Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/3319535.3363229 · Cited by 306
Bonsai Trees, or How to Delegate a Lattice Basis
Cash, D., Hofheinz, D., Kiltz, E., & Peikert, C. (2012) · Journal of Cryptology · doi:10.1007/s00145-011-9105-2 · Cited by 297
Better than BiBa: Short One-Time Signatures with Fast Signing and Verifying
Reyzin, L., & Reyzin, N. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-45450-0_11 · Cited by 295
Desmedt, Y. G. (1994) · European Transactions on Telecommunications · doi:10.1002/ett.4460050407 · Cited by 292
A fair protocol for signing contracts
Ben-Or, M., Goldreich, O., Micali, S., & Rivest, R. L. (1990) · IEEE Transactions on Information Theory · doi:10.1109/18.50372 · Cited by 287
Self-citationEfficiency improvements for signature schemes with tight security reductions
Katz, J., & Wang, N. (2003) · Proceedings of the 10th ACM conference on Computer and communications security · doi:10.1145/948109.948132 · Cited by 285
Improved Efficiency for CCA-Secure Cryptosystems Built Using Identity-Based Encryption
Boneh, D., & Katz, J. (2005) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-30574-3_8 · Cited by 283
Algorand: A secure and efficient distributed ledger
Chen, J., & Micali, S. (2019) · Theoretical Computer Science · doi:10.1016/j.tcs.2019.02.001 · Cited by 281
Self-citationRandomizable Proofs and Delegatable Anonymous Credentials
Belenkiy, M., Camenisch, J., Chase, M., Kohlweiss, M., Lysyanskaya, A., & Shacham, H. (2009) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-03356-8_7 · Cited by 269
Modern Cryptography, Probabilistic Proofs and Pseudorandomness
Goldreich, O. (1999) · Algorithms and Combinatorics · doi:10.1007/978-3-662-12521-2 · Cited by 265
Signature Schemes with Bounded Leakage Resilience
Katz, J., & Vaikuntanathan, V. (2009) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-10366-7_41 · Cited by 257
XOR MACs: New Methods for Message Authentication Using Finite Pseudorandom Functions
Bellare, M., Guérin, R., & Rogaway, P. (1995) · Lecture Notes in Computer Science · doi:10.1007/3-540-44750-4_2 · Cited by 255
Proactive public key and signature systems
Herzberg, A., Jakobsson, M., Jarecki, S., Krawczyk, H., & Yung, M. (1997) · Proceedings of the 4th ACM conference on Computer and communications security · doi:10.1145/266420.266442 · Cited by 253
Chase, M., & Lysyanskaya, A. (2006) · Lecture Notes in Computer Science · doi:10.1007/11818175_5 · Cited by 253
Quantum cryptanalysis of hash and claw-free functions: Invited paper
Brassard, G., HØyer, P., & Tapp, A. (1998) · Lecture Notes in Computer Science · doi:10.1007/bfb0054319 · Cited by 251
An evaluation of a multiple interface design solution for bloated software
McGrenere, J., Baecker, R. M., & Booth, K. S. (2002) · Proceedings of the SIGCHI Conference on Human Factors in Computing Systems · doi:10.1145/503376.503406 · Cited by 169
Lightweight Privacy and Security Computing for Blockchained Federated Learning in IoT
Fan, M., Ji, K., Zhang, Z., Yu, H., & Sun, G. (2023) · IEEE Internet of Things Journal · doi:10.1109/jiot.2023.3267112 · Cited by 37
Balloon: A Forward-Secure Append-Only Persistent Authenticated Data Structure
Pulls, T., & Peeters, R. (2015) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-24177-7_31 · Cited by 30
Metadata
- Authors
- Goldwasser, S., Micali, S., & Rivest, R. L.
- Venue
- SIAM Journal on Computing
- Published
- 1988-04
- Volume
- 17
- Issue
- 2
- Pages
- 281-308
- ISSN
- 0097-5397 (ISSN-L)
- 1095-7111
- OpenAlex
- W2151413173
- Cited by
- 2,804
- References
- 30
- FWCI
- 18.64
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.