The Risks of Schnorr Signatures

This document examines the vulnerability of Schnorr signatures to quantum attacks, demonstrating that their dependence on scalar multiplication \( kG \) makes them susceptible to algorithms like Shor's.

The analysis highlights why Schnorr signatures are not quantum-resistant and the critical need for transitioning to quantum-safe cryptographic schemes.

1. Overview of Schnorr Signatures

Schnorr signatures are widely regarded for their simplicity and efficiency. The signing process involves the following steps:

Key Generation:

The modulus used in the \( kG \) calculation process of ECDSA, as adopted by Bitcoin and others, is \( 2^{256} - 2^{32} - 977 \).
This becomes the prime number of the finite field.

Signature Generation:

Select a random nonce:
\( r \) and compute \( R = rG \).
Compute the hash: \( e = H(m \| R) \), where \( m \) is the message.
Compute the signature: \( s = r + ek \mod N \). where \( N \) is the order of the elliptic curve.
In this case, the \( N \) used in ECDSA, as adopted by Bitcoin and others, is \( 115792089237316195423570985008687907852837564279074904382605163141518161494337 \).

Signature Verification:

Recompute \( R' = sG - eP \)
Verify that \( H(m \| R') = e \)

2. Quantum Attack on Schnorr Signatures

The primary vulnerability of Schnorr signatures arises from their reliance on scalar multiplication and the elliptic curve discrete logarithm problem (ECDLP).

Step 1: Exploiting Public Key \( P \)

The public key is defined as:
\begin{equation} P = kG, \end{equation}

where \( k \) is the private key. Using Shor's algorithm, a quantum computer can efficiently solve the discrete logarithm problem and recover \( k \) from \( P \).

Step 2: Exploiting Nonce \( r \)

During the signing process, the random nonce \( r \) is used to compute \( R = rG \). If \( R \) and the corresponding hash \( e \) are observed, a quantum computer can also solve the discrete logarithm problem for \( r \): \begin{equation} R = rG \implies r = \text{ECDLP}(R, G) \end{equation}

About \( ECDLP(R, G) \)

(1) Initialization of Superposition

Prepare a superposition of all possible \( r \) values:

\begin{equation} |\psi_{\text{initial}}\rangle = \frac{1}{\sqrt{N}} \sum_{r=0}^{N-1} |r\rangle |rG\rangle, \end{equation} where \( N \) is the order of the elliptic curve.

(2) Phase Oracle Application

Apply a phase shift to the state corresponding to the observed \( R = rG \): \begin{equation} |\psi_{\phi}\rangle = \frac{1}{\sqrt{N}} \sum_{r=0}^{N-1} e^{i\phi_r} |r\rangle |rG\rangle, \quad \text{where } \phi_r = \begin{cases} \pi & \text{if } rG = R, \\ 0 & \text{otherwise}. \end{cases} \end{equation}

(3) Quantum Fourier Transform (QFT)

Apply the Quantum Fourier Transform to the superposition to extract the periodicity: \begin{equation} |\psi_{\text{QFT}}\rangle = \text{QFT}\Bigg(\frac{1}{\sqrt{N}} \sum_{r=0}^{N-1} e^{i\phi_r} |r\rangle\Bigg) \end{equation}

(4) Measurement and Derivation of \( r \)

Measure the quantum state to extract the phase information and compute \( r \): \begin{equation} r = \frac{\phi_r \cdot N}{2\pi} \mod N \end{equation}

Step 3: Recovering the Private Key \( k \)

Given \( s = r + ek \mod N \), once \( r \) and \( e \) are known, the private key \( k \) can be derived as: \begin{equation} k = \frac{s - r}{e} \mod N \end{equation}

3. Why Schnorr Signatures Are Not Quantum-Resistant

Schnorr signatures inherit the vulnerabilities of ECDSA since both depend on scalar multiplication and the elliptic curve discrete logarithm problem.

Scalar Multiplication:
Vulnerable to Shor's algorithm.

Nonce Dependence:
If multiple signatures reuse a nonce \( r \), even classical attacks can compromise the scheme.

Public Key Exposure:
Quantum computers can derive private keys from public keys.

4. Transition to Quantum-Resistant Schemes

Given the vulnerability of Schnorr signatures, it is critical to transition to quantum-resistant cryptographic schemes, such as:
Hash-Based Signatures (e.g., SPHINCS+)
Lattice-Based Cryptography (e.g., Kyber, Dilithium)
Code-Based Cryptography (e.g., McEliece)

5. Conclusion

Schnorr signatures, while efficient and secure against classical attacks, are fundamentally vulnerable to quantum attacks due to their reliance on the elliptic curve discrete logarithm problem. As quantum computing advances, adopting quantum-resistant cryptographic systems is imperative to ensure long-term security.