Layering Quantum-Resistance into Classical Digital Signature Algorithms

‍It is proven that asymmetric key cryptographic systems that rely on Integer Factorization or Discrete Logarithm as the underlying hard problem are vulnerable to quantum computers. Using Shor’s algorithm on a large-enough quantum computer, an attacker can cryptanalyze the public key to obtain the private key in O(logN) time complexity. For systems that use the classical Digital Signature Algorithm (DSA), Rivest-Shamir-Adleman (RSA) algorithm, or Elliptic-Curve Digital Signature Algorithm (ECDSA), it means that authentication, data integrity, and non-repudiation between the communicating parties cannot be assured in the post-quantum era.

In this paper, we present a novel approach using zero-knowledge proofs on the pre-image of the private signing key to layer in quantum resistance into digital signature deployments that require longer-term post-quantum protection while maintaining backward compatibility with existing implementations. We show that this approach can extend the cryptographic protection of data beyond the post-quantum era and is also easy to migrate to. An implementation of this approach applying a ZKBoo zero-knowledge proof on ECDSA signatures is realized using an RFC3161-compatible timestamp server with OpenSSL and an Adobe Acrobat Reader DC.

This paper is published at ISC 2021 https://link.springer.com/chapter/10.1007/978-3-030-91356-4_2

‍You can access the pre-print of the paper here: https://github.com/tanteikg/pqECDSA/blob/main/Layering_Quantum_Resistance_into_Digital_Signature_Algorithms%20pre-print.pdf