Discrete Logarithm Based Digital Signature

Tweet

Identification Schemes

Identification schemes are extremely important as building block for digital signature scheme. An identification scheme is a protocol that is running in the public key setting. There are two parties: prover and verifier.

Prover	Generates a pair of public and private keys. Publicize their public keys.
Verifier	Obtain authentic copy of the prover’s public key.

---

---

The goal of an identification scheme is to allow the prover to convince the verifier that the prover is who he claims he is. In a particular form, they are going to work in 3 rounds of interaction:

1. Prover has private key sk, and public key pk. He sends a message A to verifier.
2. Verifier has public key pk, she chooses its challenge message c from some space Ω.
3. Prover, after receiving the challenge c, based on the message A, it is own private key sk, computes a response s.
4. Verifier will be able to:
   • run some local verification procedure involving the public key pk, along with challenge c and the response s.
   • check whether the computation will yields the message A, i.e. V(pk, c, s) = A ?

Security

The security is a relatively weak notion that it is only against passive eavesdropping attacks. The idea of this security notion is that the attackers, even after eavesdropping on multiple honest executions, should not be able to turn around, and convince a verifier falsely that the attacker is the prover.

For technical reason, we need to assume “non-degenerate schemes”, which means the first message A has negligible probability of repeating. This will be satisfied by almost any natural protocol fitting into this three-round paradigm.

Limited Applications

A prototypical application is in-peson identification. For example: someone uses a smart card to gain access to some room. The private key is stored in the smart card. In this case smart card is a prover, and the card reader connected to the door is the verifier.

However, the identification protocols as described, are not suitable for remote authentication, i.e. authentication over the internet. The reason is subtle: there is nothing binds the execution of the ID protocol to any subsequent communication. So it turns out the identification protocols are not super useful for things over the internet.

We are most interested in the application of identification schemes to construct digital signatures. The idea is to have the prover to sign a message, by running the identification scheme by itself, with a hash function to generate the challenge c. This transformation from identification schemes to signatures is known as the Fiat-Shamir transform.

Fiat-Shamir Transform

How does it work?

1. Signer (Prover) has private key sk, along with some message m that they wish to sign. Signer will run the identification protocol by itself:
   • Generate a message A.
   • Generate a challenge message c = Hash(A, m).
   • Generate the last message s.
2. The signature on the message m will consist of c and s, i.e. σ = (c, s). Both message m , σ, and public key pk are sent to verifier.
3. Verifier then run the verification procedure, using pk, c, and s, to get output value A’, i.e. A' = V(pk, c, s).
4. Verifier check whether A’ = A, by checking Hash(A', m) = c ?

Theorem: this signature scheme is secure if:

1. the original identification scheme is secure against passive attacks.
2. H is modeled as a random function.

Schnorr Identification Scheme

Recall the settings for cryptographic schemes based on the discrete logarithm problem. A group generation algorithm ? outputs cyclic group G of prime order q with generator g. The length of q is n bits, where n is the security parameter as usual. The discrete logarithm assumption says: given a uniform value h ∈ G, it is hard to compute loggh.

Prover will generate his public key (G, q, g, h) and private key x. An execution of the protocol works in the following way:

1. Prover chooses a random exponent r, and set A = gr, and send A to verifier.
2. Verifier chooses a random challenge in c ← Z_q, and send c to the prover.
3. Prover then respond with the s = [c ∙ x + r mod q].
4. Finally verifier checks whether gs ∙ h-c = A ? If so, it accepts; if not, it rejects.
   gs ∙ h-c = gc∙x + r ∙ h-c = (gx)c ∙ gr ∙ h-c = gr = A

---

---

Security

An attacker, who only sees the public key (without eavesdropping), can not impersonate the prover, without solving the discrete logarithm problem. Why? The attacker can begin by sending some initial message A. If the attacker is going to be successful with high probability, they should be able to respond correctly at least two different challenges from the verifier: c and c', say s and s'.

For both of the challenges, the verification conditions must be equal, a little bit of arithmetic allows you to compute the discrete logarithm of h with respect to g.

gs ∙ h-c = gs' ∙ h-c' = A
⟹ gs-s' = hc-c'
⟹ loggh = [s-s'/c-c' mod q]

More interestingly, eavesdropping won’t give attackers any more advantage. It is possible to simulate a valid-looking execution of the protocol, based on the public key (G, q, g, h) and without knowledge of private key x,

Honest execution	Valid-looking execution
1. Set A = gr 2. Choose c 3. Set s = c ∙ x + r 4. Verify gs ∙ h-c = A	1. Choose c 2. Choose s 3. Compute A = gs ∙ h-c

In the case of valid-looking execution, the 3 values A, c, s are identically distributed to the 3 values in the case of honest execution.

1. c is uniformly distributed in Z_q.
2. s is uniformly distributed.
3. A is unique value.

The attacker can generate simulated transcript with the identical distribution, so passively eavesdropping honest executions of the protocol is of no use to the attacker.

This idea of being able to simulate an honest execution of a protocol is a very powerful one. The same core idea is used in Zero-Knowledge Proofs.

Theorem: If the discrete logarithm assumption holds, the Schnorr Identification Scheme is secure against passive attacks.

Corollary: If the discrete logarithm assumption holds, and H is modeled as a random function, the signature scheme we derived from Schnorr Identification protocol by applying the Fiat-Shamir Transform is a secure signature scheme.

Unfortunately, the Schnorr signature scheme is not very widely used in practice.

Digital Signature Standard (DSS)

DSS signature scheme is widely used, and standardized by NIST. The standard incorporates two different schemes:

1. DSA (Digital Signature Algorithm)
   • Based on discrete-logarithm problem in subgroup of Z^*_p.
2. ECDSA (Elliptic-Curve Digital Signature Algorithm)
   • Based on elliptic-curve groups.

DSS is another signature scheme which can be viewed as being derived from an identification scheme, using an unproven variant of the Fiat-Shamir Transform.

---

---

My Certificate

For more on Discrete Logarithm Based Digital Signature, please refer to the wonderful course here https://www.coursera.org/learn/cryptography

My #90 course certificate from Coursera

---

Related Quick Recap

Digital Signature

---

I am Kesler Zhu, thank you for visiting my website. Check out more course reviews at https://KZHU.ai

Don't forget to sign up newsletter, don't miss any chance to learn.

Or share what you've learned with friends!

Tweet