Digital Signature Schemes: Cryptography and Factorization
This paper examines digital signature schemes in cryptography, focusing on schemes based on factorization and discrete logarithm problems. Beginning with the foundational concept of public key cryptography, the paper traces the development of digital signatures from Diffie and Hellman's original proposal through subsequent refinements. It outlines the core components of a signature scheme, including key generation, signing, and verification algorithms, then surveys the major categories of attacks such schemes must resist. The paper reviews several historical signature schemes—including RSA, Rabin, and Goldwasser-Micali-Yao—and discusses newer approaches designed to overcome their weaknesses, including forward-secure schemes and dual-hard-problem designs that require an adversary to solve both factorization and discrete logarithm problems simultaneously.
- Introduction to Digital Signatures and Public Key Cryptography: Defines digital signatures and public key cryptography basics
- New Forms of Computer Cryptography and Security: Covers hash functions, ZK protocols, and forward-secure schemes
- Components of a Digital Signature Scheme: Lists six technical components of a signature scheme
- Types of Attacks on Signature Schemes: Introduces key-only and message attack categories
- Four Types of Message Attacks: Details known, generic, directed, and adaptive chosen-message attacks
- Previous Digital Signature Schemes: Reviews historical schemes and their security vulnerabilities
- Summary and Conclusion: Synthesizes findings and notes ongoing research directions
✍️ How to write this paper — guide, tools & examples ▾
What makes this paper effective
- The paper synthesizes multiple scholarly sources to build a coherent survey of digital signature development, giving readers both historical context and technical detail.
- Numbered lists are used effectively to break down abstract technical concepts—such as scheme components and attack types—into digestible, parallel structures.
- The progression from foundational definitions to specific attack taxonomies to historical scheme evaluations gives the paper a logical, building-block structure that suits a technical audience.
Key academic technique demonstrated
The paper demonstrates effective use of comparative analysis across multiple cryptographic schemes. Rather than describing each scheme in isolation, the author consistently evaluates each against a shared framework of attack resistance—key-only attacks, chosen-message attacks, and adaptive attacks—allowing readers to assess relative security strengths and weaknesses across schemes.
Structure breakdown
The paper opens with a conceptual introduction to digital signatures and public key cryptography, then moves into a section on emerging cryptographic approaches. The technical core covers scheme components (Section II) and attack typologies (Sections III–IV). Section V surveys historical schemes evaluated against those attack types. A brief conclusion synthesizes the findings. The structure mirrors a standard literature review format appropriate for an undergraduate computer science or security course.
Introduction to Digital Signatures and Public Key Cryptography
Digital signatures are described as "an analog of handwritten signatures," which are based on "the physically idiosyncratic way of signing one's name. But they can be easily forged" (Grabbe, 1998). The digital signature is "a mathematical method of attaching one's identity to a message" and is held to be more difficult to forge than a handwritten signature (Grabbe, 1998). Public key cryptography is used for digital signatures and employs two keys: (1) an ordinary plain-text message is taken and one of the keys is applied to it in an encryption process, producing a scrambled or "encrypted" (or, in the current context, "signed") message; and (2) the other key is applied to the scrambled message in a decryption process, recovering the original plain-text message (Grabbe, 1998).
One of the two keys is a public key and the other is a private key. Goldwasser, Micali, and Rivest (1988) report that the idea of "a digital signature first appeared in Diffie and Hellman's seminal paper 'New Directions in Cryptography,'" in which it was proposed that each user publish a "public key" to be used for signature validation while "keeping a secret key (used for producing signatures)" (Goldwasser, Micali, and Rivest, 1988).
The idea of a digital signature was proposed as a replacement for handwritten signatures. Several problems of a technical nature arise when digital signatures are implemented through the use of what are known as trap-door functions. However, these complications were addressed and a solution reported. It is stated that GMY83 demonstrated how arbitrary or sparse message sets could be handled, and how it could be ensured that should a perpetrator view previous signatures, that perpetrator would not be assisted in forging new ones (Goldwasser, Micali, and Rivest, 1988).
Lin, Gun, and Chen (2009) report that since the first proposal of a digital signature, there have been schemes based on discrete logarithms and the factoring problem. Most of those proposed thus far have been shown to lack adequate security. One example is that Harn, in 1995, demonstrated that the He-Kiesler scheme can be broken if the individual has the capacity to solve the factorization problem (Lin, Gun, and Chen, 2009). In addition, Lin and Hwang demonstrated that if an individual has the capacity to solve the discrete logarithm problem, the He-Kiesler scheme can likewise be broken.
New Forms of Computer Cryptography and Security
Al-Saidi (2011), in "Signature Identification Scheme Based on Iterated Function Systems," reports that secure identification is a critical aspect of security. The use of a hash function can be employed in the construction of a secure digital signature, which is equally complex as the identification scheme. The digital signature scheme can be used in building communication tools that are effective in nature as well as in ensuring privacy. Al-Saidi (2011) reports that the first proposed method for public key exchange was the zero-knowledge (ZK) protocol in digital cash protection on smart cards, which is considered to be just as time-consuming as other methods of authentication; however, it is also "harder to crack" (Al-Saidi, 2011).
According to Abdalla and Reyzin (2000), a key-evolving signature scheme is one in which operation is partitioned into periods, with a different secret key for each period. Each secret key is used for signing messages only during a specific period and for computing a new secret key when that period has ended. Abdalla and Reyzin (2000) report that "the verification algorithm checks not only that a signature is valid, but also that it was generated during a specific time period." This type of scheme is reported as "forward-secure" if it is not feasible for an "adaptive chosen-message adversary to forge signatures for past time periods, even if it discovers the secret key for the current time period." An implication is that past secret keys are unrecoverable from the current one; however, in a forward-secure signature scheme, should the current secret key be compromised, the signatures from past time periods can still be trusted.
Components of a Digital Signature Scheme
A signature scheme is reported to contain the following components (Goldwasser, Micali, and Rivest, 1988):
(1) A security parameter k, which is chosen by the user when creating public and secret keys. The parameter k determines a number of quantities, including the length of signatures, the length of signable messages, the running time of the signing algorithm, and overall security.
(2) A message space, which is the set of messages to which the signature algorithm may be applied. Without loss of generality, all messages are assumed to be represented as binary strings — that is, {0, 1}*. To ensure that the entire signing process is polynomial in the security parameter, the length of messages to be signed is assumed to be bounded by kc, for some constant c > 0.
(3) A signature bound B, which is an integer bounding the total number of signatures that can be produced with an instance of the signature scheme. This value is typically bounded above by a low-degree polynomial in k, but may be infinite.
(4) A key generation algorithm G, which any user A can use on input 1k (i.e., k in unary) to generate in polynomial time a pair (PA, SA) of matching public and secret keys. The secret key is sometimes called the trap-door information.
(5) A signature algorithm σ, which produces a signature σ(M, SA) for a message M using the secret key SA. The signing algorithm may receive other inputs as well. For example, in the scheme proposed first by the authors, σ has an additional input representing the number of previously signed messages.
(6) A verification algorithm V, which tests whether a given value is a valid signature for message M using the public key PA — that is, V(S, M, PA) is true if and only if the signature is valid. Any of the above algorithms may be randomized algorithms that make use of auxiliary random bit stream inputs. G must be a randomized algorithm, since part of its output is the secret key, which must be unpredictable to an adversary. The signing algorithm σ may also be randomized; in particular, the signing algorithm described by Goldwasser, Micali, and Rivest is randomized and capable of producing many different signatures for the same message. In general, the verification algorithm need not be randomized.
Create your account
Always verify citation format against your institution’s current style guide requirements.