Michele Mosca

Amelia Holcomb, Geovandro C. C. F. Pereira, Bhargav Das et al.

Hyperledger Fabric is a prominent and flexible solution for building permissioned distributed ledger platforms. Access control and identity management relies on a Membership Service Provider (MSP) whose cryptographic interface only handles standard PKI methods for authentication: RSA and ECDSA classical signatures. Also, MSP-issued credentials may use only one signature scheme, tying the credential-related functions to classical single-signature primitives. RSA and ECDSA are vulnerable to quantum attacks, with an ongoing post-quantum standardization process to identify quantum-safe drop-in replacements. In this paper, we propose a redesign of Fabric's credential-management procedures and related specifications in order to incorporate hybrid digital signatures, protecting against both classical and quantum attacks using one classical and one quantum-safe signature. We create PQFabric, an implementation of Fabric with hybrid signatures that integrates with the Open Quantum Safe (OQS) library. Our implementation offers complete crypto-agility, with the ability to perform live migration to a hybrid quantum-safe blockchain and select any existing OQS signature algorithm for each node. We perform comparative benchmarks of PQFabric with each of the NIST candidates and alternates, revealing that long public keys and signatures lead to an increase in hashing time that is sometimes comparable to the time spent signing or verifying messages itself. This is a new and potentially significant issue in the migration of blockchains to post-quantum signatures.

Michele Mosca, João Marcos Vensi Basso, Sebastian R. Verschoor

There have been several efforts to apply quantum SAT solving methods to factor large integers. While these methods may provide insight into quantum SAT solving, to date they have not led to a convincing path to integer factorization that is competitive with the best known classical method, the Number Field Sieve. Many of the techniques tried involved directly encoding multiplication to SAT or an equivalent NP-hard problem and looking for satisfying assignments of the variables representing the prime factors. The main challenge in these cases is that, to compete with the Number Field Sieve, the quantum SAT solver would need to be superpolynomially faster than classical SAT solvers. In this paper the use of SAT solvers is restricted to a smaller task related to factoring: finding smooth numbers, which is an essential step of the Number Field Sieve. We present a SAT circuit that can be given to quantum SAT solvers such as annealers in order to perform this step of factoring. If quantum SAT solvers achieve any speedup over classical brute-force search, then our factoring algorithm is faster than the classical NFS.

Michele Mosca, Sebastian R. Verschoor

The assumed computationally difficulty of factoring large integers forms the basis of security for RSA public-key cryptography, which specifically relies on products of two large primes or semi-primes. The best-known factoring algorithms for classical computers run in sub-exponential time. Since integer factorization is in NP, one can reduce this problem to any NP-hard problem, such as Boolean Satisfiability (SAT). While reducing factoring to SAT has proved to be useful for studying SAT solvers, attempting to factor large integers via such a reduction has not been found to be successful. Shor's quantum factoring algorithm factors any integer in polynomial time, although large-scale fault-tolerant quantum computers capable of implementing Shor's algorithm are not yet available, so relevant benchmarking experiments for factoring via Shor's algorithm are not yet possible. In recent years, however, several authors have attempted factorizations with the help of quantum processors via reductions to NP-hard problems. While this approach may shed some light on some algorithmic approaches for quantum solutions to NP-hard problems, in this paper we study and question the practical effectiveness of this approach for factoring large numbers. We find no evidence that this is a viable path toward factoring large numbers, even for scalable fault-tolerant quantum computers, as well as for various quantum annealing or other special purpose quantum hardware.