by Teik Guan Tan and Jianying Zhou
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 a RFC3161-compatible time-stamp 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