The DOI matches its Crossref record; 27 of the 27 references it cites were found in a registry or an index.
On the (In)security of the Fiat-Shamir paradigm
Abstract
In 1986, Fiat and Shamir proposed a general method for transforming secure 3-round public-coin identification schemes into digital signature schemes. The idea of the transformation was to replace the random message of the verifier in the identification scheme, with the value of some deterministic hash function evaluated on various quantities in the protocol and on the message to be signed. The Fiat-Shamir methodology for producing digital signature schemes quickly gained popularity as it yields efficient and easy to implement digital signature schemes. The most important question however remained open: are the digital signatures produced by the Fiat-Shamir methodology secure? We answer this question negatively. We show that there exist secure 3-round public-coin identification schemes for which the Fiat-Shamir transformation yields insecure digital signature schemes for any hash function used by the transformation. This is in contrast to the work of Pointcheval and Stern which proved that the Fiat-Shamir methodology always produces digital signatures secure against chosen message attack in the "Random Oracle Model" - when the hash function is modeled by a random oracle. Among other things, we make new usage of Barak's technique for taking advantage of nonblack-box access to a program, this time in the context of digital signatures.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
Identity-Based Encryption from the Weil Pairing
Boneh, D., & Franklin, M. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44647-8_13 · Cited by 7,060
Random oracles are practical: a paradigm for designing efficient protocols
Bellare, M., & Rogaway, P. (1993) · Proceedings of the 1st ACM conference on Computer and communications security - CCS '93 · doi:10.1145/168588.168596 · Cited by 4,712
How To Prove Yourself: Practical Solutions to Identification and Signature Problems
Fiat, A., & Shamir, A. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-47721-7_12 · Cited by 3,943
The MD5 Message-Digest Algorithm
Rivest (1992) · Medical Entomology and Zoology · Cited by 2,853
A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks
Goldwasser, S., Micali, S., & Rivest, R. L. (1988) · SIAM Journal on Computing · doi:10.1137/0217017 · Cited by 2,804
Self-citationEfficient signature generation by smart cards
Schnorr, C. P. (1991) · Journal of Cryptology · doi:10.1007/bf00196725 · Cited by 2,787
Goldreich, O. (2001) · Cambridge University Press eBooks · doi:10.1017/cbo9780511546891 · Cited by 2,181
How 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-citationThe MD5 Message-Digest Algorithm
Rivest, R. (1992) · doi:10.17487/rfc1321 · Cited by 1,976
Cited by
Signature Schemes and Anonymous Credentials from Bilinear Maps
Camenisch, J., & Lysyanskaya, A. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-28628-8_4 · Cited by 982
Delegating computation: interactive proofs for muggles
Goldwasser, S., Kalai, Y. T., & Rothblum, G. N. (2008) · Proceedings of the fortieth annual ACM symposium on Theory of computing · doi:10.1145/1374376.1374396 · Cited by 484
Self-citationAttribute-Based Encryption With Verifiable Outsourced Decryption
Lai, J., Deng, R. H., Guan, C., & Weng, J. (2013) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2013.2271848 · Cited by 466
Short Pairing-Based Non-interactive Zero-Knowledge Arguments
Groth, J. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-17373-8_19 · Cited by 440
Improved Delegation of Computation Using Fully Homomorphic Encryption
Chung, K.-M., Kalai, Y., & Vadhan, S. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-14623-7_26 · Cited by 403
Self-citation
Metadata
- Authors
- Goldwasser, S., & Kalai, Y. T.
- Venue
- 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings.
- Publisher
- IEEE Computer. Soc
- Published
- 2004-03-01
- Pages
- 102-113
- ISSN
- 0272-5428 (ISSN-L)
- OpenAlex
- W2120154759
- Cited by
- 311
- References
- 27
- FWCI
- 12.14
- Type
- conference paper
- 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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: On the (In)security of the Fiat-Shamir paradigm. https://app.cochat.ai/papers/10.1109/sfcs.2003.1238185
- The paper
- Goldwasser, S., & Kalai, Y. T. (2004). On the (In)security of the Fiat-Shamir paradigm. 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. https://doi.org/10.1109/sfcs.2003.1238185
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.